1 冒泡排序
1.1 算法思想
- 比较相邻的元素。如果第一个比第二个大,就交换他们两个。
- 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。
- 针对所有的元素重复以上的步骤,除了最后一个。
- 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。
1.2 C语言实现
/** * bubble_sort - ascendly bubble sort the array * * @param array the array to be sorted * @param length the length of the array */ extern void bubble_sort(int array[], int length) { int i, j; for (i = length; i > 0; i--){ for (j = 0; j < i-1; j++){ if (array[j] > array[j+1]) swap(&array[j], &array[j+1]); } } }
1.3 性质
- 时间复杂度:O(n2)
- 原地(不申请多余的空间):是
- 稳定:是
2 选择排序
2.1 算法思想
- 在未排序序列中找到最小(大)元素,交换到排序序列的起始位置
- 从剩余未排序元素中继续寻找最小(大)元素,然后交换到已排序序列的末尾
- 以此类推,直到所有元素均排序完毕
2.2 C语言实现
/** * selection_sort - ascendly selection sort the array * * @param array the array to be sorted * @param length the length of the array * */ extern void selection_sort(int array[], int length){ int i, j, min; for (i = 0; i < length; i++) { min = i; for (j = i; j < length; j++) { /* search for the minimum value */ if (array[min] > array[j]) { min = j; } } if (min != i) { /* swap array[j] and min */ swap(&array[i], &array[min]); } } return; }
2.3 性质
选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上,则它不会被移动。选择排序每次交换一对元素,它们当中至少有一个将被移到其最终位置上,因此对n个元素的表进行排序总共进行至多n-1次交换。在所有的完全依靠交换去移动元素的排序方法中,选择排序属于非常好的一种。
- 时间复杂度:O(n2)
- 原地:是
- 稳定:否
3 插入排序
3.1 算法思想
插入排序(Insertion Sort)算法类似于玩扑克时抓牌的过程,玩家每拿到一张牌都要插入到手中已有的牌里,使之从小到大排好序。
开始时,我们的左手为空,并且桌子上的牌面向下。然后,我们每次从桌子上拿走一张牌并将它插入左手中正确的位置。为了找到一张牌的正确位置,我们从右到左将它与已在手中的每张牌进行比较。拿在左手上的牌总是排序好的,原来这些牌是桌子上牌堆中顶部的牌。
插入排序算法与这个过程类似,但和插入扑克牌有一点不同:不可能在两个相邻的存储单元之间再插入一个单元,因此要将插入点之后的数据依次往后移动一个单元。排序算法如下:
- 从第一个元素开始,该元素可以认为已经被排序;
- 取出下一个元素,在已经排序的元素序列中从后向前扫描;
- 从已排序序列最后往前换换换,如果该元素(已排序)大于新元素,将该元素移到下一位置;
- 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置;
- 将新元素插入到该位置后;
- 重复步骤2~5。
3.2 C语言实现
/** * insertion_sort - ascendly insertion sort the array * @param array the array to be sorted * @param length the length of the array * * Sorting the array ascendly by using the insertion sort algorithms. * */ extern void insertion_sort(int array[], int length){ int i, j, key; for (i = 1; i < length; j++){ key = array[i]; for (j = i - 1; j >= 0 && array[j] > key; j--){ array[j+1] = array[j]; } array[j+1] = key; } return; }
3.3 性质
- 算法复杂度:O(n2) 。当 n 比较小时(e.g. n≤30),使用插入排序比较适合;当 n 比较大时,插入排序就显得很慢了。
- 原址:是
- 稳定:是
3.4 改进版本
- 希尔排序:带步长的采样数据,从而将元素分成若干组进行插入排序。然后再改用更小的步长(最后一次排序前就不必换,可以直接插了)。
- 二叉查找树排序:利用二叉查找树,快速确定元素的插入位置,从而改进插入排序的效率。
- 图书馆排序:排列图书时,如果在每本书之间留一定的空隙,那么在进行插入时就有可能会少移动一些书。说白了就是在插入排序的基础上,给书与书之间留一定的空隙,这个空隙越大,需要移动的书就越少,这是它的思路——用空间换时间。
- 耐心排序:先将元素入桶,最后用插入排序。
4 希尔排序
4.1 算法思想
希尔排序(Shell Sort)算法是 D.L. Shell 于1959年发明的,它是插入排序的一种高速而稳定的改进版本。
希尔排序通过将比较的全部元素分为若干组来提升插入排序的性能。这样可以让一个元素可以一次性地朝最终位置前进一大步。然后算法再取越来越小的步长进行排序,算法的最后一步就是普通的插入排序,但是到了这步,需排序的数据几乎是已排好的了。
一个更好理解的希尔排序实现:将数组列在一个表中并对列排序(用插入排序)。重复这过程,不过每次用更长的列来进行。最后整个表就只有一列了。将数组转换至表是为了更好地理解这算法,算法本身仅仅对原数组进行排序。
4.2 过程演示
例如,假设有这样一组数[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ],如果我们以步长为5开始进行排序,我们可以通过将这列表放在有5列的表中来更好地描述算法,这样他们就应该看起来是这样:
13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10
然后我们对每列进行排序:
10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45
将上述四行数字,依序接在一起时我们得到:[ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ].这时10已经移至正确位置了,然后再以3为步长进行排序:
10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45
排序之后变为:
10 14 13 25 23 33 27 25 59 39 65 73 45 94 82 94
4.3 C语言实现
下面的函数是对整型数组进行排序的Shell排序算法。步长使用了 n/2 并且对步长取半直到步长达到 1。
/** * shell_sort - ascendly shell sort the array * @param array the array to be sorted * @param length the length of the array * * * Sorting the array ascendly by using the shell sort algorithms. * */ void shell_sort(int array[], int length){ int gap, i, j, key; for (gap = length/2; gap > 0; gap /= 2) for (i = gap; i < length; i++) for (j=i-gap; j>=0 && array[j]>array[j+gap]; j-=gap) { // swap the two elements key = array[j]; array[j] = array[j+gap]; array[j+gap] = key; } return; }
4.4 性质
- 时间复杂度:O(nlgn)
- 原址:是
- 稳定:否
5 归并排序
5.1 算法思想
归并排序(Merge Sort)算法完全遵循分治模式,直观上其操作如下:
- 分解:把长度为n的输入序列分成两个长度为n/2的子序列。
- 解决:对这两个子序列分别采用归并排序。
- 合并:将两个 排序好 的子序列合并成一个最终的排序序列(左一个右一个)。
在描述归并排序的步骤时又调用了归并排序本身,可见这是一个递归的过程。
归并排序算法的一个核心操作是合并步骤中两个已排序序列的合并。回到我们玩扑克牌的例子,假设桌上有两堆牌,每堆都已排序,最小的牌在顶上。我们希望把这两堆牌合并成单一的排好序的输出堆。我们的基本步骤包括在两堆牌的顶上的两张牌中选取较小的一张并将该牌放置到输出堆。重复这个步骤,直到一个输入堆为空,这时,我们只是拿起剩余的输出堆并牌面朝下的将该堆放置到输出堆。
5.2 C语言实现
/** * merge - merge array * @param array the array to be merge * @param start the start of the array * @param mid the end of the left array * @param end the end of the whole array * * A key subroutine of merge sort. * */ static void merge(int array[], int start, int mid, int end){ // Logically divide the array into two and treat them respectively int n1 = mid - start + 1; int n2 = end - mid; int left[n1], right[n2]; int i, j, k; for (i = 0; i < n1; i++) // left holds array[start...mid] left[i] = array[start + i]; for (j = 0; j < n2; j++) // right holds array[mid+1..end] right[j] = array[mid + 1 + j]; i = j = 0; k = start; while (i < n1 && j < n2){ if (left[i] < right[j]) array[k++] = left[i++]; else array[k++] = right[j++]; } // append the rest to the array while (i < n1) // left[] is not exhausted array[k++] = left[i++]; while (j < n2) array[k++] = right[j++]; return; } /** * msort - ascendly merge sort the array * @param array the array to be sorted * @param start the start of the array * @param end the end of the array * * Sorting the array ascendly by using the merge sort algorithms. * The core of merge sort. * */ static void msort(int array[], int start, int end){ int mid; if (start < end){ mid = (start + end) / 2; msort(array, start, mid); msort(array, mid + 1, end); merge(array, start, mid, end); } return; } /** * merge_sort - ascendly merge sort the array * @param array the array to be sorted * @param length the length of the array * * The interface of merge sort. * @returns 0 after sorting. * */ extern void merge_sort(int array[], int length){ msort(array, 0, length-1); return; }
5.3 性质
- 时间复杂度:O(nlgn)
- 原址:否
- 稳定:是
6 堆排序
堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构,并同时满足堆的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。
6.1 算法思想
6.1.1 堆节点的访问
通常堆是通过一维数组来实现的(完全二叉树)。在起始数组为 0 的情形中:
- 父节点i的左子节点在位置 (2*i+1);
- 父节点i的右子节点在位置 (2*i+2);
- 子节点i的父节点在位置 floor((i-1)/2);
6.1.2 堆排序
堆排序是一种利用堆这种数据结构,进行原地排序的排序算法,只和数据规模有关。
堆排序算法是一种很漂亮的算法,这里需要用到三个函数:MaxHeapify、BuildMaxHeap 和 HeapSort。
- 最大堆调整(MaxHeapify):将堆的末端子节点作调整,使得子节点永远小于父节点,保证该结构为最大堆。
- 创建最大堆(BuildMaxHeap):将堆所有数据重新排序。具有线性时间复杂度。
- 堆排序(HeapSort):移除位在第一个数据的根节点,并做最大堆调整的递归运算。取出的节点即可插入已排序队列
6.2 过程演示
6.2.1 MaxHeapify
在程序的每一步中,从 A[i]、A[LEFT(i)] 和 A[RIGHT(i)] 中挑选出最大的,并将其下标存储在变量 largest 中。如果 A[i] 是最大的,那么以 i 为根结点的子树已经是最大堆,程序结束。否则,最大元素是 i 的某个孩子结点,则交换 A[i] 和 A[largest] 的值。从而使 i 及其孩子都满足最大堆的性质。在交换后,下标为 largest 的结点的值是原来的 A[i],于是以该结点为根的子树又有可能会违反最大堆的性质。因此,需要对该子树递归调用 MaxHeapify 。
6.2.2 BuildMaxHeap
BuildMaxHeap中从叶子结点开始自下而上的调用MaxHeapify来改造数组,建立最大堆。因为MaxHeapify能够保证下标i的结点之后结点都满足最大堆的性质,所以自下而上的调用MaxHeapify能够在改造过程中保持这一性质。
如果最大堆的数量元素是n,那么BuildMaxHeap从n结点的父结点开始,往上依次调用MaxHeapify。
这基于一个定理:如果最大堆有n个元素,那么从PARENT(n)+1,PARENT(n)+2…n都是叶子结点。
6.2.3 HeapSort
HeapSort是堆排序的接口算法,接受数组和元素个数两个参数。
HeapSort先调用BuildMaxHeap将数组改造为最大堆,然后将堆顶和堆底元素交换,之后将堆底提前一位,最后重新调用MaxHeapify保持最大堆性质。
由于堆顶元素必然是堆中最大的元素,所以一次操作之后,堆中存在的最大元素被分离出堆。
重复n-1次之后,数组排列完毕。
6.3 性质
- 时间复杂度:O(nlgn)
- 原地:是
- 稳定:否
7 快速排序
在平均状况下,排序 n 个项目要 O(nlgn) 次比较。在最坏状况下则需要 O(n2) 次比较,但这种状况并不常见。事实上,快速排序通常明显比其他 O(nlgn)算法更快,因为它的内部循环(inner loop)可以在大部分的架构上很有效率地被实现出来。
7.1 算法思想
快速排序使用分治法策略来把一个串行(list)分为两个子串行(sub-lists)。
- 分解:从数列中挑出一个元素,称为 “主元”(pivot),并以此将数列分成两个子数列(partition):所有元素比主元值小的摆放在主元前面,所有元素比主元值大的摆在主元的后面(相同的数可以到任一边),该主元处于数列的中间位置。
- 排序:递归地把小于主元值元素的子数列和大于主元值元素的子数列排序。
- 合并:合并子数列。
可见,归并排序做的是是递归地“合并”,而快速排序做的是递归地“分区”。
7.2 C语言实现
不依赖标准库的实现
/** * sway - swap two integers * * @param a the first integer * @param b the second integer * */ static void swap(int *a, int *b){ int temp = *a; *a = *b; *b = temp; return; } /** * partition - divide the array into two parts by using a pivot * @param array the array to be divided * @param start the start of the array * @param end the end of the array * * * A key subroutine of quick sort. * */ static int partition(int array[], int start, int end){ int pivot = array[end]; int mid = start; int i; for (i = start; i < end; i++) { if(array[i] <= pivot){ swap(&array[i], &array[mid]); mid++; } } swap(&array[end], &array[mid]); return mid; } /** * msort - ascendly quick sort the array * @param array the array to be sorted * @param start the start of the array * @param end the end of the array * * Sorting the array ascendly by using the quick sort algorithms. * The core of quick sort. * */ static int q_sort(int array[], int start, int end){ int mid; if (end > start) { mid = partition(array, start, end); q_sort(array, start, mid-1); q_sort(array, mid+1, end); } } /** * quick_sort - ascendly quick sort the array * @param array the array to be sorted * @param length the length of the array * * The interface of quick sort. * */ extern void quick_sort(int array[], int length){ q_sort(array, 0, length-1); return; }
直接调用标准库函数
#include <stdio.h> #include <stdlib.h> #include "dbg.h" int array[8] = {2, 8, 7, 1, 3, 5, 6, 4}; int cmp_int ( const void *a , const void *b ){ return *(int *)a - *(int *)b; } int main(void){ qsort(&array[0], 8, sizeof(int), cmp_int); int i; for (i = 0; i < 8; i++){ printf("%d ", array[i]); } printf("\n"); return 0; }
7.3 性质
- 算法复杂度:
- 最坏情况下(当数据是已排序的时候),快速排序的时间复杂度是 O(n2) ;
- 大多数情况下,快速排序的时间复杂度是 O(nlgn)。
- 原址:是
- 稳定:否
在排序前先将数列随机化,或者采用随机选择主元的方式可以将快速排序的时间复杂度始终限制在 O(nlgn)。在实践中,快速排序往往能够比归并排序快三倍。
8 线性时间排序
计数排序
8.1 算法思想
计数排序是一个类似于桶排序的排序算法,其优势是对已知数量范围的数组进行排序。它创建一个长度为这个数据范围的数组C,C中每个元素记录要排序数组中对应记录的出现个数。这个算法于1954年由 Harold H. Seward 提出。
- 确定数据范围,以该范围创建数组C
- 扫描原数组A,统计每种数据出现的次数并存入数组C
- 将数组C展开到结果数组
8.2 C语言实现
/** * Sort - Counting sort * * @param A the array to be sorted * @param k the range of data * */ public static void Sort(int[] A, int k){ Debug.Assert(k > 0);//断言k>0 Debug.Assert(A != null); int[] C = new int[k + 1]; for (int j = 0; j < A.Length; j++) { C[A[j]]++; } int z = 0; for (int i = 0; i <= k; i++) { while (C[i]-- > 0) { A[z++] = i; } } }
8.3 性质
- 算法复杂度: Θ(k+n) 。在实际工作中,当 k=O(n) 时,我们一般会采用计数排序,这时的运行时间为 Θ(n)。
- 原址:否
- 稳定:是
基数排序
8.4 算法思想
将整数按位数切割成不同的数字,然后按每个位数分别比较。由于整数也可以表达字符串(比如名字或日期)和特定格式的浮点数,所以基数排序也不是只能使用于整数。
基数排序的方式可以采用LSD(Least significant digital)或MSD(Most significant digital),LSD的排序方式由最低位开始,而MSD则相反,由键值的最高位开始。现在的基数排序通常使用更加高效的LSD的方案。
8.5 性质
- 算法复杂度: Θ(d(k+n))
- 原址:否
- 稳定:是
9 桶排序
9.1 算法思想
桶排序 (Bucket sort)或所谓的箱排序,是一个排序算法,工作的原理是将阵列分到 有限数量 的桶子里。每个桶子再个别排序(有可能再使用别的排序算法或是以递回方式继续使用桶排序进行排序)。桶排序是鸽巢排序的一种归纳结果。当要被排序的阵列内的数值是均匀分配的时候,桶排序使用线性时间(Θ(n))。但桶排序并不是 比较排序,他不受到 O(n log n) 下限的影响。当然,以上复杂度的计算是基于输入的n个数字是平均分布这个假设的。这个假设是很强的,实际应用中效果并没有这么好。如果所有的数字都落在同一个桶中,那就退化成一般的排序了。