内容简介:排序算法也是面试中常常提及的内容,问的最多的应该是快速排序、堆排序。这些排序算法很基础,但是如果平时不怎么写代码的话,面试的时候总会出现各种bug。虽然思想都知道,但是就是写不出来。本文打算对各种排序算法进行一个汇总,包括插入排序、冒泡排序、选择排序、计数排序、归并排序,基数排序、桶排序、快速排序等。快速排序比较重要,会单独写一篇,而堆排序见本系列的二叉堆那篇文章即可。需要提到的一点就是:插入排序,冒泡排序,归并排序,计数排序都是稳定的排序,而其他排序则是不稳定的。本文完整代码在插入排序是很基本的排序,特
排序算法也是面试中常常提及的内容,问的最多的应该是快速 排序 、堆排序。这些 排序算法 很基础,但是如果平时不怎么写代码的话,面试的时候总会出现各种bug。虽然思想都知道,但是就是写不出来。本文打算对各种排序算法进行一个汇总,包括插入排序、冒泡排序、选择排序、计数排序、归并排序,基数排序、桶排序、快速排序等。快速排序比较重要,会单独写一篇,而堆排序见本系列的二叉堆那篇文章即可。
需要提到的一点就是:插入排序,冒泡排序,归并排序,计数排序都是稳定的排序,而其他排序则是不稳定的。本文完整代码在 这里 。
1 插入排序
插入排序是很基本的排序,特别是在数据基本有序的情况下,插入排序的性能很高,最好情况可以达到 O(N)
,其最坏情况和平均情况时间复杂度都是 O(N^2)
。代码如下:
/** * 插入排序 */ void insertSort(int a[], int n) { int i, j; for (i = 1; i < n; i++) { /* * 循环不变式:a[0...i-1]有序。每次迭代开始前,a[0...i-1]有序, * 循环结束后i=n,a[0...n-1]有序 * */ int key = a[i]; for (j = i; j > 0 && a[j-1] > key; j--) { a[j] = a[j-1]; } a[j] = key; } } 复制代码
2 希尔排序
希尔排序内部调用插入排序来实现,通过对 N/2,N/4...1
阶分别排序,最后得到整体的有序。
/** * 希尔排序 */ void shellSort(int a[], int n) { int gap; for (gap = n/2; gap > 0; gap /= 2) { int i; for (i = gap; i < n; i++) { int key = a[i], j; for (j = i; j >= gap && key < a[j-gap]; j -= gap) { a[j] = a[j-gap]; } a[j] = key; } } } 复制代码
3 选择排序
选择排序的思想就是第i次选取第i小的元素放在位置i。比如第1次就选择最小的元素放在位置0,第2次选择第二小的元素放在位置1。选择排序最好和最坏时间复杂度都为 O(N^2)
。代码如下:
/** * 选择排序 */ void selectSort(int a[], int n) { int i, j, min, tmp; for (i = 0; i < n-1; i++) { min = i; for (j = i+1; j < n; j++) { if (a[j] < a[min]) min = j; } if (min != i) tmp = a[i], a[i] = a[min], a[min] = tmp; //交换a[i]和a[min] } } 复制代码
循环不变式:在外层循环执行前, a[0...i-1]
包含 a
中最小的 i
个数,且有序。
-
初始时,
i=0
,a[0...-1]
为空,显然成立。 -
每次执行完成后,
a[0...i]
包含a
中最小的i+1
个数,且有序。即第一次执行完成后,a[0...0]
包含a
最小的1
个数,且有序。 -
循环结束后,
i=n-1
,则a[0...n-2]
包含a
最小的n-1
个数,且已经有序。所以整个数组有序。
4 冒泡排序
冒泡排序时间复杂度跟选择排序相同。其思想就是进行 n-1
趟排序,每次都是把最小的数上浮,像鱼冒泡一样。最坏情况为 O(N^2)
。代码如下:
/** * 冒泡排序-经典版 */ void bubbleSort(int a[], int n) { int i, j, tmp; for (i = 0; i < n; i++) { for (j = n-1; j >= i+1; j--) { if (a[j] < a[j-1]) tmp = a[j], a[j] = a[j-1], a[j-1] = tmp; } } } 复制代码
循环不变式:在循环开始迭代前,子数组 a[0...i-1]
包含了数组 a[0..n-1]
的 i-1
个最小值,且是排好序的。
对冒泡排序的一个改进就是在每趟排序时判断是否发生交换,如果一次交换都没有发生,则数组已经有序,可以不用继续剩下的趟数直接退出。改进后代码如下:
/** * 冒泡排序-优化版 */ void betterBubbleSort(int a[], int n) { int tmp, i, j; for (i = 0; i < n; i++) { int sorted = 1; for (j = n-1; j >= i+1; j--) { if (a[j] < a[j-1]) { tmp = a[j], a[j] = a[j-1], a[j-1] = tmp; sorted = 0; } } if (sorted) return ; } } 复制代码
5 计数排序
假定数组为 a[0...n-1]
,数组中存在重复数字,数组中最大数字为k,建立两个辅助数组 b[]
和 c[]
, b[]
用于存储排序后的结果, c[]
用于存储临时值。时间复杂度为 O(N)
,适用于数字范围较小的数组。
计数排序原理如上图所示,代码如下:
/** * 计数排序 */ void countingSort(int a[], int n) { int i, j; int *b = (int *)malloc(sizeof(int) * n); int k = maxOfIntArray(a, n); // 求数组最大元素 int *c = (int *)malloc(sizeof(int) * (k+1)); //辅助数组 for (i = 0; i <= k; i++) c[i] = 0; for (j = 0; j < n; j++) c[a[j]] = c[a[j]] + 1; //c[i]包含等于i的元素个数 for (i = 1; i <= k; i++) c[i] = c[i] + c[i-1]; //c[i]包含小于等于i的元素个数 for (j = n-1; j >= 0; j--) { // 赋值语句 b[c[a[j]]-1] = a[j]; //结果存在b[0...n-1]中 c[a[j]] = c[a[j]] - 1; } /*方便测试代码,这一步赋值不是必须的*/ for (i = 0; i < n; i++) { a[i] = b[i]; } free(b); free(c); } 复制代码
扩展:如果代码中的给数组 b[]
赋值语句 for (j=n-1; j>=0; j--)
改为 for(j=0; j<=n-1; j++)
,该代码仍然正确,只是排序不再稳定。
6 归并排序
归并排序通过分治算法,先排序好两个子数组,然后将两个子数组归并。时间复杂度为 O(NlgN)
。代码如下:
/* * 归并排序-递归 * */ void mergeSort(int a[], int l, int u) { if (l < u) { int m = l + (u-l)/2; mergeSort(a, l, m); mergeSort(a, m + 1, u); merge(a, l, m, u); } } /** * 归并排序合并函数 */ void merge(int a[], int l, int m, int u) { int n1 = m - l + 1; int n2 = u - m; int left[n1], right[n2]; int i, j; for (i = 0; i < n1; i++) /* left holds a[l..m] */ left[i] = a[l + i]; for (j = 0; j < n2; j++) /* right holds a[m+1..u] */ right[j] = a[m + 1 + j]; i = j = 0; int k = l; while (i < n1 && j < n2) { if (left[i] < right[j]) a[k++] = left[i++]; else a[k++] = right[j++]; } while (i < n1) /* left[] is not exhausted */ a[k++] = left[i++]; while (j < n2) /* right[] is not exhausted */ a[k++] = right[j++]; } 复制代码
扩展:归并排序的非递归实现怎么做?
归并排序的非递归实现其实是最自然的方式,先两两合并,而后再四四合并等,就是从底向上的一个过程。代码如下:
/** * 归并排序-非递归 */ void mergeSortIter(int a[], int n) { int i, s=2; while (s <= n) { i = 0; while (i+s <= n){ merge(a, i, i+s/2-1, i+s-1); i += s; } //处理末尾残余部分 merge(a, i, i+s/2-1, n-1); s*=2; } //最后再从头到尾处理一遍 merge(a, 0, s/2-1, n-1); } 复制代码
7 基数排序、桶排序
基数排序的思想是对数字每一位分别排序(注意这里必须是稳定排序,比如计数排序等,否则会导致结果错误),最后得到整体排序。假定对 N
个数字进行排序,如果数字有 d
位,每一位可能的最大值为 K
,则每一位的稳定排序需要 O(N+K)
时间,总的需要 O(d(N+K))
时间,当 d
为常数, K=O(N)
时,总的时间复杂度为O(N)。
而桶排序则是在输入符合均匀分布时,可以以线性时间运行,桶排序的思想是把区间 [0,1)
划分成 N
个相同大小的子区间,将 N
个输入均匀分布到各个桶中,然后对各个桶的链表使用插入排序,最终依次列出所有桶的元素。
这两种排序使用场景有限,代码就略过了,更详细可以参考《算法导论》的第8章。
以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网
猜你喜欢:- 算法之常见排序算法-冒泡排序、归并排序、快速排序
- 排序算法之冒泡排序改进算法
- 快速排序算法,C语言快速排序算法深入剖析
- 排序算法下——桶排序、计数排序和基数排序
- 数据结构和算法面试题系列—排序算法之快速排序
- 图形化排序算法比较:快速排序、插入排序、选择排序、冒泡排序
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。