排序算法分析维度

• 执行效率
  最好情况，最坏情况，平均情况时间复杂度
  时间复杂度系数，常数，低阶
  比较次数和交换（或者移动）次数

• 内存消耗
  能否是原地排序算法（空间复杂度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”，不影响原顺序。

参考：《数据结构与算法之美》王争