排序算法分析维度
-
执行效率
最好情况，最坏情况，平均情况时间复杂度
时间复杂度系数，常数，低阶
比较次数和交换（或移动）次数 -
内存消耗
是否是原地排序算法（空间复杂度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”，不影响原顺序。
参考：《数据结构与算法之美》王争
网友评论