排序算法分析维度
执行效率
最好情况, 最坏情况, 平均情况时间复杂度
时间复杂度系数, 常数, 低阶
比较次数和交换 (或移动) 次数
内存消耗
是否是原地排序算法(空间复杂度 O(1))
稳定性
相等元素之间原有的先后顺序是否改变
冒泡排序(Bubble Sort)
思想: 每次比较相邻两个数据, 不满足大小关系要求则交换. 一次冒泡至少会让一个元素移动到它应该在的位置.
是否原地排序: 是, 只涉及相邻数据交换, 只需常量级临时空间, 空间复杂度 O(1)
是否稳定: 是, 相邻两元素大小相等时不做交换
时间复杂度: 最好情况冒泡一次, O(n). 最坏情况冒泡 n 次, O(n2). 元素交换次数是原始数据逆序度
有序元素对: a[i] <= a[j], 如果 i <j
逆序元素对: a[i]> a[j], 如果 i <j
完全有序的数组的有序度称为满有序度(n* (n - 1)/2)
逆序度 = 满有序度 - 有序度
分析平均情况下时间复杂度可结合 "有序度" 和 "逆序度" 概念, 最坏情况需进行 n* (n - 1)/2 次交换, 即平均情况大致需进行 n* (n - 1)/4 次交换, 时间复杂度 O(n2)
插入排序(Insertion Sort)
思想: 分为已排序区间和未排序区间, 从尾到头遍历已排序区间的数据, 找到数据应该插入的位置将其插入
是否原地排序: 是, 不需要额外存储空间, 空间复杂度 O(1)
是否稳定: 是
时间复杂度: 最好情况 O(n), 最坏情况 O(n2), 平均情况(即数组插入数据的平均时间复杂度)O(n2). 元素移动次数是原始数据逆序度
选择排序(Selection Sort)
思想: 分为已排序区间和未排序区间, 每次从未排序区间找到最小元素, 同未排序区间第一个元素交换, 将其放到已排序区间末尾.
是否原地排序: 是, 空间复杂度 O(1)
是否稳定: 否, 因元素交换破坏稳定性
时间复杂度: 最好情况, 最坏情况和平均情况时间复杂度都为 O(n2)
虽然冒泡和插排的时间复杂度都是 O(n2), 都是原地排序, 但从代码实现上看, 冒泡需 3 个赋值操作, 插入只需 1 个, 且插排的算法思路有很大优化空间
归并排序(Merge Sort)
思想: 要排序一个数组, 先把数组从中间分成前后两部分, 然后对前后两部分分别排序, 再将排序好的两部分合并在一起. 运用分治思想(一般都用递归来实现).
实现思路: 递推公式 merge_sort(p...r) = merge(merge_sort(p...q), merge_sort(q+1...r)); 终止条件 q>= r 不用再继续分解(q=(p+r)/2)
代码示例:
- void merge_sort_recursive(int[] arr, int[] reg, int start, int end) {
- if (start>= end)
- return;
- int len = end - start, mid = (len>> 1) + start;
- int start1 = start, end1 = mid;
- int start2 = mid + 1, end2 = end;
- // 递归到子序列只有一个数的时候, 开始逐个返回
- merge_sort_recursive(arr, reg, start1, end1);
- merge_sort_recursive(arr, reg, start2, end2);
- //------- 合并操作, 必须在递归之后(子序列有序的基础上)----
- int k = start;
- while (start1 <= end1 && start2 <= end2)
- reg[k++] = arr[start1] <arr[start2] ? arr[start1++] : arr[start2++];
- while (start1 <= end1)
- reg[k++] = arr[start1++];
- while (start2 <= end2)
- reg[k++] = arr[start2++];
- // 借用 reg 数组做合并, 然后把数据存回 arr 中
- for (k = start; k <= end; k++)
- arr[k] = reg[k];
- }
哨兵简化技巧 在划分后的两个数组最后都加上 INT_MAX, 减少两次越界判断
因为不可能大于 INT_MAX, 所以只需比较值即可判断是否越界, 不需再用下标判断
是否原地排序: 否, 空间复杂度 O(n)(任意时刻, CPU 只会有一个函数在执行, 也就只会有一个临时内存空间在使用, 所以最大不会超过 n 个数据的大小)
是否稳定: 是, 合并时按下标优先.
时间复杂度: O(nlogn)(T(1) = C,n=1; T(n) = 2*T(n/2) + n,n>1; 推导而来)
快速排序(Quick Sort)
思想: 排序 p 到 r 的一组数据, 择一分区点 pivot, 将小于 pivot 的放在左边, 大于 pivot 的放在右边, 依次递归. 核心思想就是分治和分区.
实现思路: 递推公式 quick_sort(p...r) = quick_sort(p...q-1) + quick_sort(q+1, r); 终止条件 p>= r
代码示例:
- public static void quickSort(int[]arr,int low,int high){
- if (low <high) {
- int middle = getMiddle(arr, low, high);
- quickSort(arr, low, middle - 1);
- quickSort(arr, middle + 1, high);
- }
- }
- public static int getMiddle(int[] list, int low, int high) {
- int tmp = list[low];
- while (low < high) {
- while (low < high && list[high]>= tmp) {
- high--;
- }
- list[low] = list[high];
- while (low <high && list[low] <= tmp) {
- low++;
- }
- list[high] = list[low];
- }
- list[low] = tmp;
- return low;
- }
利用游标原地分区, 节省空间, 开一个空间存储临时变量(pivot), 左右两头的游标不断缩紧, 下标对应的数据跟 pivot 值对比并交换到正确位置.
是否稳定: 否, 涉及交换, 顺序无法保证
是否原地排序: 是, 关键看分区函数怎么写, 利用游标原地分区空间复杂度为 O(1)
时间复杂度: O(nlogn)(T(1) = C,n=1; T(n) = 2*T(n/2) + n,n>1; 推导而来), 极端情况会退化为 O(n2)
线性排序
桶排序(Bucket Sort)
思想: 将要排序的数据分到几个有序的桶里, 每个桶里的数据再单独进行排序, 最后把每个桶的数据依次取出, 组成有序序列.
代码示例:
- public class BucketSort {
- /**
- * 对 arr 进行桶排序, 排序结果仍放在 arr 中
- */
- public static void bucketSort(double arr[]){
- //-------------- 分桶 -----------------
- int n = arr.length;
- // 存放桶的链表
- ArrayList bucketList[] = new ArrayList [n];
- // 每个桶是一个 list, 存放此桶的元素
- for(int i =0;i<n;i++){
- // 下取等
- int temp = (int) Math.floor(n*arr[i]);
- // 若不存在该桶, 就新建一个桶并加入到桶链表中
- if(null==bucketList[temp])
- bucketList[temp] = new ArrayList();
- // 把当前元素加入到对应桶中
- bucketList[temp].add(arr[i]);
- }
- //------------ 桶内排序 ------------
- // 对每个桶中的数进行插入排序
- for(int i = 0;i<n;i++){
- if(null!=bucketList[i])
- insert(bucketList[i]);
- }
- //---------------- 合并桶内数据 -------------
- // 把各个桶的排序结果合并
- int count = 0;
- for(int i = 0;i<n;i++){
- if(null!=bucketList[i]){
- Iterator iter = bucketList[i].iterator();
- while(iter.hasNext()){
- Double d = (Double)iter.next();
- arr[count] = d;
- count++;
- }
- }
- }
- }
- /**
- * 用插入排序对每个桶进行排序(用快排时间复杂度降低)
- * 从小到大排序
- */
- public static void insert(ArrayList list){
- if(list.size()>1){
- for(int i =1;i<list.size();i++){
- if((Double)list.get(i)<(Double)list.get(i-1)){
- double temp = (Double) list.get(i);
- int j = i-1;
- for(;j>=0&&((Double)list.get(j)>(Double)list.get(j+1));j--)
- list.set(j+1, list.get(j)); // 后移
- list.set(j+1, temp);
- }
- }
- }
- }
- }
时间复杂度: O(n), 将 n 个数据划分到 m 个桶里, 每个桶有 k=n/m 个元素, 桶内用快排则每个桶时间复杂度为 O(klogk),m 个桶为 O(mklogk),k=n/m 代入, 整个桶时间复杂度为 O(nlog(n/m)), 当 m 接近 n 时接近 O(n).
适用条件: 首先, 要排序的数据需要很容易就能划分成 m 个桶; 其次, 数据在各个桶之间的分布是比较均匀的. 分布不均的极端情况, 时间复杂对退化为 O(nlogn)(数据都划分到一个桶里)
适用场景: 如外部排序, 大量数据, 存储在外部磁盘中, 分桶后每个桶的数据一次放入内存中快排排序, 若一次分桶后数据量依然较大的文件可继续划分, 直到所有文件都能读入内存.
计数排序(Counting Sort)
思想: n 个数据所处范围的最大值为 k, 分为 k 个桶, 每个桶内数值相同, 省掉桶内排序的时间, 是桶排序的一种特殊情况.
实现思路: 拿考生查分举例 (原始数列如 A[8]={2,5,3,0,2,3,0,3}), 一分一个桶, 并对数组顺序求和(即数组 C[k] 里存储小于等于分数 k 的考生个数)得到的数列如 C[6]={2,2,4,7,7,8}; 从后向前一次扫描数组 A, 扫描到 3 时从数组 C 中找到下标为 3 的计数 7, 说明这个 3 是排序后的有序数组 (R[]) 中第 7 位, 当 3 放入数组 R 后相应 C[3]减 1, 变成 6.
代码示例:
- // 计数排序, a 是数组, n 是数组大小. 假设数组中存储的都是非负整数.
- public void countingSort(int[]a, int n) {
- if (n <= 1) return;
- // 查找数组中数据的范围
- int max = a[0];
- for (int i = 1; i <n; ++i) {
- if (max < a[i]) {
- max = a[i];
- }
- }
- int[] c = new int[max + 1];// 申请一个计数数组 c, 下标大小 [0,max]
- for (int i = 0; i <= max; ++i){
- c[i] = 0;
- }
- // 计算每个元素的个数, 放入 c 中
- for (int i = 0; i < n; ++i) {
- c[a[i]]++;
- }
- // 依次累加
- for (int i = 1; i <= max; ++i){
- c[i] = c[i-1] + c[i];
- }
- // 临时数组 r, 存储排序之后的结果
- int[] r = new int[n];
- // 计算排序的关键步骤, 有点难理解
- for (int i = n - 1; i>= 0; --i) {
- int index = c[a[i]]-1;
- r[index] = a[i];
- c[a[i]]--;
- }
- // 将结果拷贝给 a 数组
- for (int i = 0; i < n; ++i) {
- a[i] = r[i];
- }
- }
适用场景: 数据范围不大(k 比 n 小), 只能给非负整数排序或转化为非负整数.
基数排序(Radix Sort)
思想: 将整数按位数切割成不同的数字, 然后按每个位数分别比较.
时间复杂度: O(n), 数据有 k 位, 每次排序 O(n),k 次 O(kn)*,k 不大时近似 O(n)
是否原地排序: 是.
适用场景: 需要可以分割出独立的 "位" 来比较, 且位之间有递进关系(高低位), 且每一位数据范围不能太大要可以用线性排序算法完成.
数据不等长的情况可补位, 如单词排序可补 "0", 字母的 ASCII 值都大于 "0", 不影响原顺序.
参考:《数据结构与算法之美》王争
来源: http://www.jianshu.com/p/4c000ad5171c