本文共 3226 字，大约阅读时间需要 10 分钟。

排序算法

1. 常用的有：冒泡排序、插入排序、选择排序、归并排序、快速排序、计数排序、基数排序、桶排序

时间复杂度：		插入，冒泡，选择排序：O ( n^2 )		快排，归并排序：O ( nlogn )		桶，计数，基数排序：O ( n )

2. 有些排序算法，时间复杂度，和原始数据的有序度相关，并且有稳定排序和不稳定排序，即排序后，是否改变了原来相等元素间的顺序性；

举例，订单按金额排序，但要求相同金额的订单，按照创建时间排序	所以，可以先按照创建时间排序，然后选择稳定的排序算法，按照金额排序，这样就可以满足要求

冒泡排序，插入排序，选择排序

1. 冒泡排序，是原地排序算法，空间复杂度 O ( 1 )，每次循环，两两元素进行比较，将最大的元素不断下沉，直到成为数组末尾元素；

2. 冒泡是稳定排序算法，相等的元素，并不会交换次序，并且设计算法时，在一次遍历中，没有元素交换，就可以认为数据已经有序，无需下次遍历；

最坏时间复杂度：初始状态的有序度是 0，要进行 n*(n-1)/2 次交换	最好时间复杂度：初始状态的有序度是 n*(n-1)/2，一次遍历，没有元素交换，就结束排序	平均时间复杂度：使用概率论计算比较复杂，但可以通过有序度来粗略计算		取中间值 n*(n-1)/4 次交换		所以简单统计，平均时间复杂度是 O ( n^2 )

3. 插入排序，将集合分为排序区间，和未排序区间，每次都在未排序区间，选择元素，插入到排序区间中，直到未排序区间为空，保证后插入的相同元素，放在前面插入相同元素的后面，所以是稳定的排序算法；

空间复杂度是 O(1)	最好时间复杂度是 O(n)：当每次都是在排序区间最后插入元素，插入时间复杂度是 o(1)	最坏时间和平均时间复杂度是 O(n^2)：每次插入时间复杂度是 o(n)	平均时间复杂度：是每次向有序集合，插入一个元素的平均时间复杂度是 O(n),所以平均时间复杂度，是 O(n^2)

4. 选择排序，同样将集合，分排序区间，未排序区间，每次从未排序区间，选择最小元素，放在排序区间队尾；

空间复杂度 O(1)	最好，最坏，平均时间复杂度，都是 O(n^2)，每次选择时间复杂度都是 O(n)，共进行 n 次选择	不稳定的排序算法，因为每次都需要交换元素，就可能破坏了未排序区间元素的顺序性

5. 插入排序，应用更广；

相比于冒泡排序，交换元素操作更简单，冒泡排序需要三行代码执行交换，插入只需一行	相比于选择排序，插入是稳定性排序，而选择排序不是

归并排序

1. 都使用分治思想，将大问题划分为小问题来解决，都用递归来实现；

2. 归并排序，是将集合等分为两个子集合，分别进行排序后，合并两个有序子集合，然后子集合，同样进行等分，排序，合并，如此递归，直到集合剩余一个元素；

递推公式是 f(p...q) = merge(f(p...r),f(r...q))，merge，合并两个有序的数组	终止条件是 p == r 或者 q == r	是稳定排序算法，要求合并有序集合中，相同的元素，将前面集合先放入

3. 递归代码的时间复杂度，也使用递归来分析；

归并时间复杂度 T(n) = 2*T(n/2) + n，其中最后一个 n 是合并两个有序集合 n/2 的时间复杂度	截至条件 T(1) = C，C 是常量	T(n) = 2*(2*T(n/4) + n/2) + n = 4*T(n/4) + 2*n = 2^(k)*T(n/2^(k)) + kn，因为k次等分后 2^k = n	最终得到 T(n) = nlog2n + Cn	所以归并排序的时间复杂度是 O(nlogn)，并且没有最好和最坏的区分，都需要递归这么多次

4. 归并排序，与要排序的原始数组的有序程度无关，其最好情况、最坏情况，还是平均情况，时间复杂度都是 O( nlogn )，并且空间复杂度是 O ( n )，这是其一个缺点；

快速排序

1. 快速排序，每次从集合中，选取一个基准数，进行数据交换，保证小于基准数的值放在基准数左边，大于基准数的值放在基准值右边，如此对基准值左边集合，对基准值右边集合，进行递归，直到根据基准数划分后的子集合元素个数都为1；

// 排序A数组，从p到r的元素，等于根据基准数交换数据后，分为小于基准数的p到q的元素，和大于基准数的q到r的元素	// 然后分别进行递归快速排序 	递推公式：fastSort(A,p,r) = fastSort(A,p,q-1) + fastSort(A,q+1,r)	终止条件是：p == r	quick_sort_c(A, p, r) {
     		if p >= r then return    		// 对p到r元素进行分区，得到分区点		q = partition(A, p, r); 		quick_sort_c(A, p, q-1);  		quick_sort_c(A, q+1, r);	}

2. 根据基准值交换元素，需要不额外使用空间，选择基准数后，分为两个指针，依次从左往右和从右往左，左往右选择比基准数大的值，右往左选择比基准数小的值，两个指针都找到后，进行交换，最后左右指针相遇，将相遇元素和基准值交换；

注意，这里基准数的选择，觉得了快排效率，简单选择最左边，或者最右边，更优化是三点选取，随机选择等	基准数如果选最左边，要先从右往左进行查找，因为这样，最终左右指针相遇的点，是从左往右得到的，比基准数大，		且交换后的元素，即比基准数小，那么最后一次交换，就是正确的，反之会最后是从右往左，比基准数小，且交换后		的元素，即比基准数大，这样，是无法与最左边的基准数交换，交换后就是错误的

3. 快速排序，左右指针交换元素，会破坏相等元素的顺序关系，所以是一个不稳定的排序算法；

快速排序，每次分区时间复杂度是 O(n)	最好时间复杂度：每次都是等分，进行 log2n 次分区，所以最好时间复杂度是 O (nlogn)	最差时间复杂度：进行了 n 次分区，每次分区都是一个元素 + 剩余元素，所以最坏时间复杂度是  O(n^2)	平均时间复杂度是 O (nlogn)；

8. 快速排序的空间复杂度是 O (1)，而归并排序，空间复杂度是 O ( n )，这是快排应用广的一个原因；

快速排序引申

1. 在 O(n) 时间复杂度内，求无序数组中的第 K 大元素，跟快排思路类似，基准值左边放比基准值大的元素，那么交换元素后，如果基准值下标是 k-1，那么那么就有 k-1 个元素比其大，基准值就为第 k 大元素，所以和快排算法一致，只是左边集合放大的元素，并且终止条件是 基准下标 q = k -1；

第 k 大的元素，即集合中只有 k-1 个元素，比其大	按照快排的思路，选择基准值，进行分区后，分区点是 p，要求比 A[p] 大，放集合左部分，		所以集合中，有 p 个元素，比 A[p] 大，如果 p =k-1，那么就要 k-1 个元素比 A[p] da, A[p] 即为所求	如果 p > k-1，那么在左边集合查找	如果 p < k-1，那么在右边集合查找	如此递归，最终递归终止条件，p + 1 = k	时间复杂度：第一次分区，需扫描全部数据,第二次分区，n/2 数据，如此递归计算 n + n/2 + n/4 + ... + 1,		n(1/2)^k = 1,得到 2^k = n，等比数列求和 a(1-q^n)/1-q = n(1-(1/2)^k)/(1-1/2) = 2n(1-1/n) = 2n -2		所以时间复杂度是 O(n)

2. 如果有 10 个日志文件，每个大小约 300 m，每个文件里是按照时间从小到大排序的，希望将 10 个日志文件，合并为 1 个文件，合并后仍然按照时间戳从小到大排列，要求算法，使用空间只有 1GB，如何快速合并

典型的归并排序，只不过排序 1GB 数据后，需要写入磁盘

转载地址：http://osfin.baihongyu.com/