闲着的时候看到一篇“九大排序算法在总结”，瞬间觉得之前数据结构其实都有学过，但当初大多数都只是老师随口带过，并没有仔细研究一下。遂觉：这是欠下的账，现在该还了。
排序按照空间分类：
In-place sort不占用额外内存或占用常数的内存 插入排序、选择排序、冒泡排序、堆排序、快速排序。
Out-place sort：归并排序、计数排序、基数排序、桶排序。
或者按照稳定性分类：
stable sort：插入排序、冒泡排序、归并排序、计数排序、基数排序、桶排序。
unstable sort：选择排序(5 8 5 2 9)、快速排序、堆排序。
针对以上九种算法，我都根据时空复杂性，还有实现的思路做了简要介绍。并且进行了简单的测试。希望能给同样学习排序算法的同学一点帮助。
#ifndef __INCLUDE_MY_SORT__ #define __INCLUDE_MY_SORT__ #include <iostream> #include <cstdio> #include <vector> #define INF 0x3f3f3f3f using namespace std; /* 插入排序： 时间复杂度 最坏情况(数组逆序): O(n*n) 最好情况（数组有序）: O(n) 空间复杂度 线性空间 */ namespace Insert_sort{ template<class T> void sort(T *a, int len){ int i, j; for( i = 0; i < len; i++){ j = i - 1; T key = a[i]; while(j >= 0 && a[j] > key){ a[j + 1] = a[j]; j --; } a[j + 1] = key; } } } /* 冒泡排序： 时间复杂度 最坏情况 O(n*n) 最好情况 O(n*n) 空间复杂度 线性空间 思路：每次将待排序的值(0 : len - i - 1)按照大小尽可能放到最右边 第一个循环是冒泡的轮数，第二个循环是冒泡的范围区域(未有序的区域)因为经过一次循环最大的一定在最右边，2次循环次大的一定在倒数第二个以此类推。 这样就保证了，下一次只需要在未有序的范围内进行冒泡，算法是完备并且正确的。 */ namespace Bubble_sort{ template<class T> void sort(T *a, int len) { int i, j; for(i = 0; i < len; i ++) { for(j = 0; j < len - 1 - i; j ++){ if(a[j] > a[j + 1]) swap(a[j],a[j + 1]); } } } } /* 选择排序： 时间复杂度 最坏情况 O(n*n) 最好情况 O(n*n) 空间复杂度 线性空间 思路： 每次选出最小的放到当前最走边 */ namespace Selection_sort{ template <class T> void sort(T *a, int len) { int i , j, min_val = a[0], min_pos = 0; for(i = 0; i < len; i ++) { min_val = a[i], min_pos = i; for(j = i; j < len; j ++) { if(min_val > a[j]){ min_val = a[j]; min_pos = j; } } swap(a[i],a[min_pos]); } } } /* 归并排序： 时间复杂度 最坏情况 O(nlgn) 最好情况 O(nlgn) 空间复杂度 线性空间 思路 ：分治的思想 Divide(划分子问题)、Conquer(子问题求解)、Combine(将子解合并成原问题的解)。 不断递推分解，将大区间每次从中分段,直到左右区间只剩下一个元素，进行求解并合并左右两个子区间，使其有序。 不断递推返回，直到合并到最大的区间。 */ namespace Merge_sort{ template<class T> void merge(T *a, int p, int m, int q) { //printf("Merge: p = %d, m = %d, q = %d ",p,m,q); int l = m - p + 1, r = q - m; T *L = (T*)malloc((l + 1) * sizeof(T)); T *R = (T*)malloc((r + 1) * sizeof(T)); memcpy(L, a + p, l * sizeof(T));//这里很重要：左侧包含了下标为 m 的元素 memcpy(R, a + m + 1,r * sizeof(T)); L[l] = INF; R[r] = INF; int i = 0,j = 0, k; for(k = p; k <= q; k ++) { if(L[i] < R[j]){ a[k] = L[i]; i ++; } else{ a[k] = R[j]; j ++; } } free(L); free(R); } template<class T> void divide(T *a, int p, int q) { if(p < q) { int m = (p + q) >>1; //cout<<" p = "<<p<<" m = "<<m<<" q = "<<q<<endl; divide(a, p, m); divide(a, m + 1, q); merge(a, p, m, q); } } template<class T> void sort(T *a, int len) { divide(a, 0, len - 1); } } /* 快速排序： 时间复杂度 最坏情况(数组有序，每次Partition都划分成1 | n - 1，一共需要划分n次，每个partition的复杂度也是o(n)) : O(n*n) 最好情况 : O(nlgn) 空间复杂度 线性空间 思路 ：分治的思想 Divide(划分子问题)、Conquer(子问题求解)、Combine(将子解合并成原问题的解)。 不断以r = partition的位置换分小区间，这样让r左边区间都小于r,r右边区间都大于r。 */ namespace Quick_sort{ template <class T> int partition(T *a, int p, int q) { int rand_index = rand() % (q - p + 1) + p;//随机选择key值避免退化n*n复杂度 if(rand_index < p || rand_index > q) rand_index = p; swap(a[p], a[rand_index]) ; int i = p,j = q,pVal = a[p]; while(i < j){ while(i < j && a[j] >= pVal) j --; swap(a[j], a[i]); while(i < j && a[i] <= pVal) i ++; swap(a[i], a[j]); } return i; } template <class T> void recursive_qsort(T *a, int p, int q) { if(p < q){ int r = partition(a, p, q); recursive_qsort(a, p, r); recursive_qsort(a, r+1, q); } } template <class T> void sort(T *a, int len) { recursive_qsort(a, 0, len - 1); } } /* 堆排序： 时间复杂度 最坏情况 O(nlgn) 最好情况 O(nlgn) 空间复杂度 线性空间 算法动态示意图: https://en.wikipedia.org/wiki/Heapsort 思路 ：step 1 建立大顶堆（同一父节点的两个孩子之间的大小关系，不用纠结，只需要保证parent > max(lchild, rchild)） step 2 排序，将大顶堆的第一个元素(最大)与最后一个元素(最小 or 次小 or 次次小 ...)交换位置，再次调整heap,使maximum到堆顶。 repeat step 1. */ namespace Heap_sort{ template <class T> void heap_adjust(T *a, int i, int len) { T tmp = a[i]; int lchild = i * 2 + 1, rchild = i * 2 + 2, largest = i; if(rchild < len){ if(a[largest] < a[rchild]) largest = rchild; } if(lchild < len){ if(a[largest] < a[lchild]) largest = lchild; } if(largest != i){ swap(a[largest], a[i]); heap_adjust(a, largest, len); } } template <class T> void build_max_heap(T *a, int len) { for(int i = len / 2 - 1; i >= 0; i --) { heap_adjust(a, i, len); } } template <class T> void sort(T *a, int len) { build_max_heap(a, len); int heap_num = len; for(int i = len - 1; i >= 1; i --) { swap(a[0],a[i]); heap_num --;//已经有序的元素不在参与堆排序 heap_adjust(a, 0, heap_num); } } } /* 计数排序： 时间复杂度 最坏情况 O(n+k) 最好情况 O(n+k) 空间复杂度 线性空间 思路 ：非比较排序，用空间换时间，适用于固定范围的且元素较小的数组排序。 对于val ai, 比它小的元素有cnt[ai]个，那么ai一定放在cnt[ai] - 1 (下标从0开始)这个位置。 */ namespace Counting_sort{ const int Max_val= 10000, Max_len = 10000; template <class T> void sort(T *a, int len) { int i, j, cnt[Max_val + 1]; T *rank = (T*)malloc(len * sizeof(T)); for(i = 0; i <= Max_val; i ++) cnt[i] = 0; for(i = 0; i < len; i ++) cnt[a[i]] ++; for(i = 0; i < Max_val; i ++) cnt[i + 1] += cnt[i]; for(i = 0; i < len; i ++) { rank[ --cnt[a[i]]] = a[i];//val ai 可能有多个所以下一个 ai 的位置应该会靠前1位 } memcpy(a, rank, len * sizeof(T)); free(rank); } } /* 基数排序： 时间复杂度 O(d(n+radix)) （设待排序列为n个记录，d个关键码，关键码的取值范围为radix） 空间复杂度 线性空间 思路 ：非比较排序，用空间换时间。 按照位数进行排序，从第0位开始，使用桶辅助排序，类似计数排序的思想，数个数，就是把对应位相同的num放到一起，最后按照0 - 9的优先级从新排序数组。 一共重复最大数的位数次。 */ namespace Radix_sort{ template <class T> T get_max_val(T *a, int len) { int i; T max_val = a[0]; for(i = 0; i < len; i ++) { if(max_val < a[i]) max_val = a[i]; } return max_val; } template <class T> int compute_dig_num(T max_val) { int dig_num = 1, test_val = 9, radix = 10; while(test_val < max_val) { dig_num ++; radix *= 10; test_val = radix - 1; } return dig_num; } template <class T> void sort(T *a, int len) { if(len <= 0) return ; T max_val = get_max_val(a, len); int dig_num = compute_dig_num(max_val), i, j, k, cnt = 0; vector<T>bucket[10]; int radix = 1; for( i = 0; i < dig_num; i ++) { for( j = 0; j < 10; j ++) bucket[j].clear(); for( j = 0; j < len; j ++) { int dig = (a[j] / radix) %10; bucket[dig].push_back(a[j]); } cnt = 0; for( j = 0; j < 10; j ++) { for(k = 0; k < bucket[j].size(); k ++) { a[cnt ++] = bucket[j][k]; } } radix *= 10; } } } /* 桶排序： 时间复杂度 最优情况 O(n)) 最坏情况 O(nlgn) 空间复杂度 线性空间 思路 ：非比较排序，用空间换时间。 最坏情况运行时间：当分布不均匀时，全部元素都分到一个桶中，则O(n^2)， 这里实现的是整数排序，正常的话桶排序的数据范围是[0,1)。主要体现的是桶排序的思想。 桶内排序可以使用插入 堆 或者快速排序。这样最坏情况就是O(nlgn)。 */ namespace Bucket_sort{ const int Max_val = 91000; template <class T> void sort(T *a, int len) { int i, j ; T cnt[Max_val]; for(i = 0; i < Max_val; i ++) cnt[i] = 0; for(i = 0; i < len; i ++) { if(a[i] > Max_val) return ; cnt[a[i]]++; } j = 0; for(i = 0; i < Max_val; i ++) { while(cnt[i]){ a[j++] = i; cnt[i] --; } } } } #endif//__INCLUDE_MY_SORT__
/* 希尔排序： 时间复杂度 最坏情况(数组逆序): O(N1.5) 最好情况（数组有序）: O(Nlog2N) 空间复杂度 O(1) 思路：每次选择增量d（d每次缩减一半，直到=1进行最后一次），进行一次插入排序； 这样一开始d比较大，元素个数较少，元素无序的概率较高，使得插入排序次数较少 后来d比较小，元素较多，但是由于进行到后期元素有序概率比较高，从而也减小了排序次数。 */ namespace Shell_sort { template<class T> void sort(T *a, int len) { int i, j, d = len / 2; //gap每次缩短一半 while (d) { //倒着枚举每一个区间 for (i = d; i < len; i ++) { int tmp = a[i]; //给插入元素挪出位置 for (j = i - d; j >= 0 && tmp < a[j]; j -= d) { a[j + d] = a[j]; }//插入 a[j + d] = tmp; } d /= 2; } } }
/* 堆排序： 最好最坏：O（n*log2n） 建堆O（n*log2n） 筛选法调整堆O（log2n） 总共循环了n-1次调整函数，所以调整堆时间复杂度为O（n*log2n） 熟悉了堆排序的过程后，可以发现堆排序不存在最佳情况，待排序序列是有序或者逆序时，并不对应于堆排序的最佳或最坏情况。且在最坏情况下时间复杂度也是O（n*log2n）。此外堆排序是不稳定的原地排序算法。 空间复杂度： O(1) 思路：先建立大顶堆， 然后每次把最有把握的最大的数（堆顶元素）放到数组尾部，确定有序，调整被扔到堆顶的无辜小一些的元素 调整整个堆，又得到最大元素。重复此步骤直到最后只剩下一个元素。 要点：1 只需要调整非叶子节点 一共 n/2个。这是因为堆是一个完全二叉树。 2 倒着调整节点，可以使下层的最大元素传递到上层去。 */ template<class T> void updateMaxHeap(T *a, int i, int n) { int left = LS(i), right = RS(i), largest; if(left > n) return ; largest = left; if(right <= n && a[right] > a[largest]){ largest = right; } if(a[i] < a[largest]){ // 孩子 大于 父节点 需要调整 swap(a[i], a[largest]); updateMaxHeap(a, largest, n); }//如果根节点最大 那么不用继续调整下去了 } template<class T> void create_max_heap(T *a, int n) { // 1...n/2 是树中所有非叶子结点 只需要调整非叶子节点即可 // 倒着调整建堆：这点很重要！ for(int i = n/2; i >= 1; i --){ updateMaxHeap(a, i, n); } } template<class T> void heap_sort(T *a, int n) { create_max_heap(a, n); cout<<"Max Heap: "<<endl; for(int i = 1; i <= n; i ++) cout<<a[i]<<" "; for(int i = n; i >= 2; i --){ swap(a[i], a[1]); updateMaxHeap(a, 1, i - 1); } cout<<"Sort: "<<endl; for(int i = 1; i <= n; i ++) cout<<a[i]<<" "; }
PS ： 优先队列使用堆实现的！不是什么树！！！！
╮(╯▽╰)╭ 论文还没看完 又开始瞎捣鼓了
注意最好的情况下算法的时间复杂度