排序算法是最基本最常用的算法,不同的排序算法在不同的场景或应用中会有不同的表现,我们需要对各种排序算法熟练才能将它们应用到实际当中,才能更好地发挥它们的优势 。今天,来总结下各种排序算法 。
下面这个表格总结了各种排序算法的复杂度与稳定性:
文章插图
各种排序算法复杂度比较.png
冒泡排序冒泡排序可谓是最经典的排序算法了,它是基于比较的排序算法,时间复杂度为O(n^2),其优点是实现简单,n较小时性能较好 。
- 算法原理
- 相邻的数据进行两两比较,小数放在前面,大数放在后面,这样一趟下来,最小的数就被排在了第一位,第二趟也是如此,如此类推,直到所有的数据排序完成
- c++代码实现
void bubble_sort(int arr[], int len){ for (int i = 0; i < len - 1; i++) { for (int j = len - 1; j > i; j--) { if (arr[j] < arr[j - 1]) { int temp = arr[j]; arr[j] = arr[j - 1]; arr[j - 1] = temp; } } }}选择排序
- 算法原理
- 先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾 。以此类推,直到所有元素均排序完毕 。
- c++代码实现
void select_sort(int arr[], int len){ for (int i = 0; i < len; i++) { int index = i; for (int j = i + 1; j < len; j++) { if (arr[j] < arr[index]) index = j; } if (index != i) { int temp = arr[i]; arr[i] = arr[index]; arr[index] = temp;} }}插入排序
- 算法原理
- 将数据分为两部分,有序部分与无序部分,一开始有序部分包含第1个元素,依次将无序的元素插入到有序部分,直到所有元素有序 。插入排序又分为直接插入排序、二分插入排序、链表插入等,这里只讨论直接插入排序 。它是稳定的排序算法,时间复杂度为O(n^2)
- c++代码实现
void insert_sort(int arr[], int len){ for (int i = 1; i < len; i ++) { int j = i - 1; int k = arr[i]; while (j > -1 && k < arr[j] ) { arr[j + 1] = arr[j]; j --; } arr[j + 1] = k; }}快速排序
- 算法原理
- 快速排序是目前在实践中非常高效的一种排序算法,它不是稳定的排序算法,平均时间复杂度为O(nlogn),最差情况下复杂度为O(n^2) 。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列 。
- c++代码实现
void quick_sort(int arr[], int left, int right){ if (left < right) { int i = left, j = right, target = arr[left]; while (i < j) { while (i < j && arr[j] > target) j--; if (i < j) arr[i++] = arr[j]; while (i < j && arr[i] < target) i++; if (i < j) arr[j] = arr[i]; } arr[i] = target; quick_sort(arr, left, i - 1); quick_sort(arr, i + 1, right); }}归并排序
- 算法原理
- 归并排序具体工作原理如下(假设序列共有n个元素):
- 将序列每相邻两个数字进行归并操作(merge),形成floor(n/2)个序列,排序后每个序列包含两个元素
- 将上述序列再次归并,形成floor(n/4)个序列,每个序列包含四个元素
- 重复步骤2,直到所有元素排序完毕
- 归并排序是稳定的排序算法,其时间复杂度为O(nlogn),如果是使用链表的实现的话,空间复杂度可以达到O(1),但如果是使用数组来存储数据的话,在归并的过程中,需要临时空间来存储归并好的数据,所以空间复杂度为O(n)
- c++代码实现
void merge(int arr[], int temp_arr[], int start_index, int mid_index, int end_index){ int i = start_index, j = mid_index + 1; int k = 0; while (i < mid_index + 1 && j < end_index + 1) { if (arr[i] > arr[j]) temp_arr[k++] = arr[j++]; else temp_arr[k++] = arr[i++]; } while (i < mid_index + 1) { temp_arr[k++] = arr[i++]; } while (j < end_index + 1) temp_arr[k++] = arr[j++]; for (i = 0, j = start_index; j < end_index + 1; i ++, j ++) arr[j] = temp_arr[i];}void merge_sort(int arr[], int temp_arr[], int start_index, int end_index){ if (start_index < end_index) { int mid_index = (start_index + end_index) / 2; merge_sort(arr, temp_arr, start_index, mid_index); merge_sort(arr, temp_arr, mid_index + 1, end_index); merge(arr, temp_arr, start_index, mid_index, end_index); }}堆排序二叉堆
二叉堆是完全二叉树或者近似完全二叉树,满足两个特性
- 父结点的键值总是大于或等于(小于或等于)任何一个子节点的键值
推荐阅读
-
-
亚马孙热带雨林|亚马逊为何会成为人类禁区?有这6种生物在,现代武器也不是对手
-
涉黑|广州警方今年打掉7个涉黑团伙!涉黑恶警情同比下降41%
-
澎湃新闻|纪录片《时代 我》:聚焦名人“下半场”的多样性
-
机械润滑脂有几种型号?四季分别使用什么型号 润滑脂分类与应用
-
-
-
区别|注意区别“上五花”和“下五花”,口感不一样买五花肉
-
流行|卫衣才是初冬的扛把子,今年流行“卫衣+直筒裤”,小个子都爱了
-
#华为#美国始料未及?中国突然宣布,任正非猜对了!
-
【时尚搭姐TB】你有种草吗,银丝边眼镜让人立马变气质?这些明星在戴的百搭单品
-
-
「李嫑嫑2」家里的AJ鞋堆成墙,手机壳都是LV的,赵辰宇“富二代”身份曝光
-
中国梦·黄河情 | 这片曾经的黄土旱塬披上了“绿装”
-
你是如何看待屈原自投汨罗江的,屈原为何要投汨罗江-
-
数码控OPPO售价1099元手机,配备128GB+5000mAh
-
-
笑笑君听讲用醋泡有效果,二话没说从网上买了五斤,笑话:宿舍兄弟脚臭
-
-
荒野乱斗|荒野乱斗:下个赛季是马戏团主题?横跨万圣节,你想要的皮肤来了