十大排序
十大排序包括插入排序, 选择排序, 冒泡排序, 归并排序, 希尔排序, 快速排序, 堆排序, 计数排序, 基数排序, 桶排序.
基本知识
基本概念:
- 稳定性: 在排序前有两个相同的关键字a和b, 若排序后仍能保证a和b的相对顺序不变(排序前a在b前, 则排序后还是a在b前), 则称为排序算法是稳定的, 否则是不稳定的.
- 时间复杂度: 对排序数据的总的操作次数. 反映当n变化时, 操作次数呈现什么规律.
- 空间复杂度: 是指算法在计算机内执行时所需存储空间的度量, 它也是数据规模n的函数.
常见的算法排序可以分为两大类:
- 比较类排序: 通过比较来决定元素间的相对次序, 由于其时间复杂度不能突破$O(nlogn)$, 因此也称为非线性时间比较类排序.
- 非比较类排序: 不通过比较来决定元素间的相对次序, 它可以突破基于比较排序的时间下界, 以线性时间运行, 因此也称为线性时间非比较类排序.
比较排序最低的时间复杂度一定是$O(n)$, 你不比较怎么排序嘛, 每个元素比较一次, 最低时间复杂度一定是线性级的.
比较排序可以分为交换排序, 插入排序, 选择排序, 归并排序四大类.
- 交换排序: 就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置.
- 冒泡排序
- 快速排序
- 插入排序: 将一个记录插入到已经排好序的有序表中, 逐渐扩大有序表的规模至整个表.
- 简单插入排序
- 希尔排序
- 选择排序: 第一次从待排序的数据元素中选出最小(或最大) 的一个元素, 存放在序列的起始位置, 然后再从剩余的未排序元素中寻找到最小(大) 元素, 然后放到已排序的序列的某个位置(取决于结构).
- 简单选择排序
- 堆排序
- 归并排序: 用分治法, 每次将已有序的子序列合并, 最后得到完全有序的序列.
插入排序
插入排序我们每个人都会, 在打扑克的时候, 顺牌的过程其实就是多次插入排序的过程. 对于未排序的序列, 在已排序的序列中找到这个关键字的相应位置并插入.
- 从第一个元素开始, 该元素可以认为已经被排序;
- 取出下一个元素, 在已经排序的元素序列中从后向前扫描;
- 如果该元素(已排序) 大于新元素, 将该元素移到下一位置;
- 重复步骤3, 直到找到已排序的元素小于或者等于新元素的位置;
- 将新元素插入到该位置后;
- 重复步骤2 ~ 5.
实现代码如下:
void insertSort(int a[], int len){
int i, j, temp;
// 认为0号元素已经有序, 从无序序列挨个选择
for(i=1; i<len; ++i){
temp = a[i];
j = i - 1; // i-1为有序序列
// 当选中的元素比有序序列中元素小的时候, 有序序列元素依次后移
while(j >= 0 && temp < a[j]){
a[j+1] = a[j];
--j;
}
// 不要忘记插入选中的元素
a[j+1] = temp;
}
} 选择排序
选择排序是非常符合人类思维直觉的一种排序方式, 从序列中选出一个最小的或最大的元素, 加入到已经有序的排序的最左端或最右端. 最后使得整个序列都有序.
- 初始状态：无序区为R[1..n], 有序区为空;
- 第i趟排序(i=1,2,3…n-1)开始时, 当前有序区和无序区分别为R[1..i-1]和R(i..n) . 该趟排序从当前无序区中-选出关键字最小的记录 R[k], 将它与无序区的第1个记录R交换, 使R[1..i]和R[i+1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区;
- n-1趟结束, 数组有序化了.
实现代码如下:
void selectSort(int a[], int len){
int i, j;
int temp;
int min;
// 遍历每个元素 当然不包括最后一个元素 因为最后选择的一定是最大的 在最右侧
for(i=0; i<len-1; ++i){
min = i;
// 找到最小元素
for(j=i+1; j<len; ++j){
if(a[j] < a[min]) min = j;
}
// 交换最小的元素和当前选中元素
temp = a[i];
a[i] = a[min];
a[min] = temp;
}
}冒泡排序
冒泡排序是实现起来最最最简单的算法, 三行实现. 它执行的过程就像鱼吐泡泡一样, 一点一点浮上来. 每趟排序都有一个元素停到它的最终位置.
- 比较相邻的元素. 如果第一个比第二个大, 就交换它们两个;
- 对每一对相邻元素作同样的工作, 从开始第一对到结尾的最后一对, 这样在最后的元素应该会是最大的数;
- 针对所有的元素重复以上的步骤, 除了最后一个;
- 重复步骤1~3, 直到排序完成.
实现代码如下:
// 三行版本
for(int i=0, temp=0, len=sizeof(a)/sizeof(a[0]); i<len-1; ++i)
for(int j=0; j<len-i-1; ++j)
for(; (temp=a[j])>a[j+1];a[j]=a[j+1], a[j+1]=temp);
// 注: 不能放在函数里! 因为放在函数里传参时sizeof(a)会是一个指针的长度
// 除非直接给len数组的长度
// 函数版本
void bubbleSort(int a[], int len){
int i, j;
int temp;
int flag; // 标识是否发生过交换
// 每次都有一个元素到最终位置, 只需要循环n-1次
for(i=0; i<len-1; ++i){
flag = 0;
// 从头开始冒泡
for(j=0; j<len-1-i; ++j){
if(a[j] > a[j+1]){
temp = a[j+1];
a[j+1] = a[j];
a[j] = temp;
flag = 1;
}
}
// 如果没发生交换说明已全部有序
if(flag == 0) return;
}
}归并排序
归并排序建立在归并操作上, 是分治法的典型应用. 将已有序的子序列合并, 得到完全有序的序列.
- 把长度为n的输入序列分成两个长度为n/2的子序列;
- 对这两个子序列分别采用归并排序;
- 将两个排序好的子序列合并成一个最终的排序序列.
实现代码如下:
// 归并操作
// 这里写出mid是因为主函数已经计算过了
void merge(int a[], int low, int mid, int high){
int i, j, k;
int n1 = mid - low + 1;
int n2 = high - mid;
int L[n1], R[n2];
// 将原序列分装进两个数组
for(i=0; i<n1; ++i){
L[i] = a[low+i];
}
for(j=0; j<n2; ++j){
R[j] = a[mid+j+1];
}
i = j = 0;
k = low;
// 开始比较归并
while(i < n1 && j < n2){
if(L[i] < R[j]) a[k++] = L[i++];
else a[k++] = R[j++];
}
// 如果还有序列没有装完
while(i < n1) a[k++] = L[i++];
while(j < n2) a[k++] = R[j++];
}
// 划分操作 把序列按递归划分为多个分组
void mergeSort(int a[], int low, int high){
if(low < high){
int mid = (low + high) / 2;
mergeSort(a, mid+1, high);
mergeSort(a, low, mid);
merge(a, low, mid, high);
}
}希尔排序
虽然希尔排序基本上不怎么考虑实现, 但不代表它不重要. 希尔排序是第一个突破$O(n^2)$的算法, 是简单插入排序的改良版. 与插入排序的不同之处在于, 它会优先比较距离较远的元素. 希尔排序又叫缩小增量排序. 先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序.
- 选择一个增量序列t1, t2, …, tk, 其中ti>tj, tk=1;
- 按增量序列个数k, 对序列进行k 趟排序;
- 每趟排序, 根据对应的增量ti, 将待排序列分割成若干长度为m 的子序列, 分别对各子表进行直接插入排序. 仅增量因子为1 时, 整个序列作为一个表来处理, 表长度即为整个序列的长度.
实现代码如下:
void shellSort(int arr[], int n){
int temp;
for(int gap=n/2; gap>0; gap/=2){ // 每趟排序gap是原来的1/2倍
for(int i=gap; i<n; ++i){ // 按照gap循环子序列
// 直接插入排序 每次都只比较j和j-gap这两个元素 与直插排序一样
temp = arr[i];
int j;
for(j=i; j >= gap && arr[j-gap] > temp; j-=gap){
arr[j] = arr[j-gap];
}
// 如果不小于了 在j处将temp元素插入
arr[j] = temp;
}
}
}快速排序
名气第一名, 所有场景都通用. 快排是必须会写的排序. 快排是冒泡排序的优化版, 它每次的交换不再像冒泡排序是交换相邻元素, 而是跳跃交换. 通过一趟排序将待排记录分隔成独立的两部分, 其中一部分记录的关键字均比另一部分的关键字小, 则可分别对这两部分记录继续进行排序, 以达到整个序列有序.
- 从数列中挑出一个元素, 称为 “基准”(pivot) ;
- 重新排序数列, 所有元素比基准值小的摆放在基准前面, 所有元素比基准值大的摆在基准的后面(相同的数可以到任一边) . 在这个分区退出之后, 该基准就处于数列的中间位置. 这个称为分区(partition) 操作;
- 递归地(recursive) 把小于基准值元素的子数列和大于基准值元素的子数列排序.
实现代码如下:
void quickSortLR(int a[], int left, int right){
int i = left, j = right;
int temp;
if(left < right){
temp = a[left];
// 无时不刻都要加上i < j的条件
// 指针相遇时应该立马停下
while(i < j){
// 从右侧找一个比基准小的元素
while(i < j && a[j] >= temp){
--j;
}
// 直接扣到左指针上
if(i < j){
a[i] = a[j];
++i;
}
// 从左侧找一个比基准大的元素
while(i < j && a[i] <= temp){
++i;
}
// 扣到右指针上
if(i < j){
a[j] = a[i];
--j;
}
}
// 二者相遇时就是最终基准位置
a[i] = temp;
quickSortLR(a, left, i-1);
quickSortLR(a, i+1, right);
}
} 上面代码实现是演示的左右交换版本, 实际上还有一种快慢指针的版本.
// 快慢指针版本 参考了豆豆的快排实现
// bilibili:BV1Ab411s7To
// 其实就是快慢指针交换比pivot小和比pivot大的过程
// 假定传进来的都是下标
int partition(int a[], int left, int right){
int i = left - 1; // 慢指针 并初始化为left左侧
int j; // 快指针
int temp;
int pivot = right; // 指定最右边的元素为基准
/*
若快指针所指元素比基准元素大
则慢指针什么都不做
若快指针所指向的元素比基准元素小
则让慢指针往前进一位 并交换快慢指针所指元素
因为只有快指针所指元素比基准元素小才让慢指针前进
所以在交换前慢指针指向的元素一定比基准元素大
*/
for(j=left; j<right; ++j){
if(a[j] < a[pivot]){
++i;
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
// 慢指针i在内的所有左侧元素都比基准元素小
// 所以交换i右侧的元素和基准元素的位置
temp = a[pivot];
a[pivot] = a[i+1];
a[i+1] = temp;
// 返回的基准元素就是未交换时的a[pivot], 即基准元素
return i+1;
}
void quickSort(int a[], int left, int right){
if(left < right){
int pivot = partition(a, left, right);
// 获取基准点 对基准的前后各使用快排
quickSort(a, left, pivot-1);
quickSort(a, pivot+1, right);
}
}堆排序
堆排序是利用堆这种数据结构所设计的一种排序算法. 因为堆是一个近似于完全二叉树的结构, 并且满足堆积的性质：即子结点的键值或索引总是小于(或者大于) 它的父节点. 在某些特殊的业务场景, 可能需要构建一个堆, 需要进行查找, 这时用堆排序就很合理.
- 将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆, 此堆为初始的无序区;
- 将堆顶元素R[1]与最后一个元素R[n]交换, 此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n];
- 由于交换后新的堆顶R[1]可能违反堆的性质, 因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆, 然后再次将R[1]与无序区最后一个元素交换, 得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn). 不断重复此过程直到有序区的元素个数为n-1, 则整个排序过程完成.
// 堆排序 选择排序 和冒泡排序非常像
// 建堆过程是一个交换的过程
// 直接采用顺序存储结构存储堆(完全二叉树)
int heap[maxSize]; // 用它来存堆(大根堆)
// 堆调整 low和high选择调整的范围 可以理解为冒泡排序中的一次冒泡
void Sift(int heap[], int low, int high){
int i=low, j = 2*i + 1; // heap[j]是i的左孩子
int temp = heap[i];
while(j <= high){
if(j < high && heap[j] < heap[j + 1]){ // 如果右孩子更大 把j指向右孩子
++j;
}
// 当temp比子孙节点中最大的都小, 交换ij, 并将ij顺着树下移一层
if(temp < heap[j]){
heap[i] = heap[j];
i = j;
j = 2*i + 1;
}
else break;
}
// 当j>high时, 将叶子节点调整为temp
heap[i] = temp;
}
// 能够看出来整个排序过程和冒泡非常像 只是添加了对堆调整的操作
void heapSort(int a[], int n){
int i;
int temp;
// 调整为大根堆
for(i=n/2-1; i>=0; --i){ // n/2-1是最后一个非叶子节点 对所有非叶子的堆依次进行调整
Sift(a, i, n-1);
}
// 将根节点和最后一个叶子节点进行交换, 删去原来的根节点, 当i=1即只剩一个节点的时候排序完成
for(i=n-1; i>0; --i){ // 其实i指代的是当前堆有几个节点
temp = a[0];
a[0] = arr[i];
a[i] = temp;
Sift(a, 0, i-1); // 每次交换后都进行堆调整 但不要最后一个节点
// 因为最后一个节点在调整\之前符合大根堆的定义
// 已经被调到了指定的位置
}
}计数排序
计数排序不是基于比较的排序算法, 它的复杂度能到线性级. 效率虽然高, 但使用场景十分受限. 它的原理规定了输入的数据必须是有确定范围的整数.
- 找出待排序的数组中最大和最小的元素;
- 统计数组中每个值为i的元素出现的次数, 存入数组C的第i项;
- 对所有的计数累加(从C中的第一个元素开始, 每一项和前一项相加) ;
- 反向填充目标数组：将每个元素i放在新数组的第C(i)项, 每放一个元素就将C(i)减去1.
基数排序
“基”这个字, 指的就是十进制的”个十百千“. 基数排序先按照个位进行排序, 然后再按照十位进行排序… 先按照低位进行排序, 然后收集到一起, 再按照高位进行排序, 以此类推, 最后就能获得一个有序的序列.
取得数组中的最大数, 并取得位数;
arr为原始数组, 从最低位开始取每个位组成radix数组;
对radix进行计数排序(利用计数排序适用于小范围数的特点) ;
桶排序
桶排序跟计数排序一样, 是一种稳定的线性时间排序算法, 这个在机器学习有相似的应用. 按照特征的取值范围对特征进行划分, 然后抽成独热向量. 这里桶排序工作的原理是将数列分到有限数量的桶里, 每个桶再个别排序. 当要被排序的数组内的数值是均匀分配的时候, 桶排序时间复杂度是线性级.
- 设置一个定量的数组当作空桶;
- 遍历输入数据, 并且把数据一个一个放到对应的桶里去;
- 对每个不是空的桶进行排序;
- 从不是空的桶里把排好序的数据拼接起来.
复杂度对比
| 排序算法 | 平均时间复杂度 | 最好情况 | 最坏情况 | 空间复杂度 | 稳定性 | 排序方式 |
|---|---|---|---|---|---|---|
| 冒泡排序 | $O(n^2)$ | $O(n)$ | $O(n^2)$ | $O(1)$ | 稳定 | In-place |
| 选择排序 | $O(n^2)$ | $O(n^2)$ | $O(n^2)$ | $O(1)$ | 不稳定 | In-place |
| 插入排序 | $O(n^2)$ | $O(n)$ | $O(n^2)$ | $O(1)$ | 稳定 | In-place |
| 希尔排序 | $O(n\log n)$ | $O(n^{1.3}$) | $O(n^2)$ | $O(1)$ | 不稳定 | In-place |
| 归并排序 | $O(n\log n)$ | $O(n\log n)$ | $O(n\log n)$ | $O(n)$ | 稳定 | Out-place |
| 快速排序 | $O(n\log n)$ | $O(n\log n)$ | $O(n^2)$ | $O(\log n)$ | 不稳定 | In-place |
| 堆排序 | $O(n\log n)$ | $O(n\log n)$ | $O(n\log n)$ | $O(1)$ | 不稳定 | In-place |
| 桶排序 | $O(n + k)$ | $O(n + k)$ | $O(n^2)$ | $O(n + k)$ | 稳定 | Out-place |
| 计数排序 | $O(n + k)$ | $O(n + k)$ | $O(n + k)$ | $O(k)$ | 稳定 | Out-place |
| 基数排序 | $O(n × m)$ | $O(n × m)$ | $O(n × m)$ | $O(n + m)$ | 稳定 | Out-place |
