2024年4月5日 排序算法
一、稳定性的定义
排序算法的稳定性是指排序过程中，相同元素的相对位置是否会发生变化。
稳定的排序算法在排序过程中不会改变元素彼此的位置的相对次序，
而不稳定的排序算法经常会改变这个次序。
稳定性是一个特别重要的评估标准，排序算法的稳定性是一个特别重要的参数衡量指标依据。
二、各大排序算法的稳定性
| 排序算法: | 平均时间复杂度 | 辅助空间 | 是否稳定 |
|---|---|---|---|
| 冒泡排序 | O(n²) | O(1) | 是 |
| 选择排序 | O(n²) | O(1) | 否 |
| 插入排序 | O(n²) | O(1) | 是 |
| 归并排序 | O(nlog2n) | O(n) | 是 |
| 快速排序 | O(nlog2n) | O(nlog2n) | 否 |
| 堆排序 | O(nlog2n) | O(1) | 否 |
| 希尔排序 | O(nlog2n) | O(nlog2n) | 否 |
| 计数排序 | O(n+k) | O(n+k) | 是 |
| 桶排序 | O(n+k) | O(n+k) | 是 |
| 基数排序 | O(n*k) | O(n+k) | 是 |
三、排序算法分类
排序算法可以分为内部排序和外部排序，
内部排序是数据记录在内存中进行排序，
而外部排序是因排序的数据很大，
一次不能容纳全部的排序记录
，在排序过程中需要访问外存。
常见的内部排序算法有：
- 插入排序
- 希尔排序
- 选择排序
- 冒泡排序
- 归并排序
- 快速排序
- 堆排序
- 基数排序
- ……
算法竞赛中，我们主要使用的都是内部排序算法，
四、各大排序算法介绍
1.冒泡排序
冒泡排序是一种简单的排序算法。
它重复地遍历要排序的数列，
一次比较两个元素，
如果它们的顺序错误就把它们交换过来。
代码实现
void BubbleSort(vector<int>& arr){
int n = arr.size();
for(int i=0;i<n-1;i++){ // 遍历第一个元素
for(int j=0;j<n-i-1;j++){ //遍历第二个元素
if(arr[j]>arr[j+1]){ //比较两个元素
swap(arr[j],arr[j+1]); //交换
}
}
}
return;
}
2.选择排序
选择排序是一种简单直观的排序算法。
它的工作原理：首先在未排序序列中找到最小（大）元素，
存放到排序序列的起始位置，
然后，再从剩余未排序元素中继续寻找最小（大）元素，
然后放到已排序序列的末尾。
以此类推，直到所有元素均排序完毕。
代码实现
void SelectionSort(vector<int>& arr){
int n = arr.size();
for(int i=0;i<n-1;i++){ // 遍历第一个元素
int min_index = i; // 假设第一个元素是最小的
for(int j=i+1;j<n;j++){ // 遍历第二个元素
if(arr[j]<arr[min_index]){ // 比较两个元素
min_index = j; // 更新最小元素的下标
}
}
swap(arr[i],arr[min_index]); // 交换
}
return ;
}
3.插入排序
插入排序也是一种简单直观的排序算法。
它的工作原理是通过构建有序序列，
对于未排序数据，在已排序序列中从后向前扫描，
找到相应位置并插入。
代码实现
void InsertionSort(vector<int>& arr){
int n = arr.size();
for(int i=1;i<n;i++){ // 遍历第一个元素
int key = arr[i]; // 取出待排序的元素
int j = i-1; // 已排序序列的最后一个元素
while(j>=0 && arr[j]>key){ // 从后向前扫描
arr[j+1] = arr[j]; // 向后移动元素
j--; // 向前移动
}
arr[j+1] = key; // 插入元素
}
return 0;
}
4.希尔排序
希尔排序是插入排序的一种更高效的改进版本。
但希尔排序是非稳定排序算法。
希尔排序是基于增量序列的插入排序算法，
也称为递减增量排序算法。
希尔排序的效率比O(nlog2n)的排序算法低，
但比O(n²)的排序算法高。
代码实现
void ShellSort(vector<int>& arr){
int n = arr.size();
for(int gap=n/2;gap>0;gap/=2){ // 遍历增量序列
for(int i=gap;i<n;i++){ // 遍历每个元素
int key = arr[i]; // 取出待排序的元素
int j = i-gap; // 已排序序列的最后一个元素
while(j>=0 && arr[j]>key){ // 从后向前扫描
arr[j+gap] = arr[j]; // 向后移动元素
j -= gap; // 向前移动
}
arr[j+gap] = key; // 插入元素
}
}
return ;
}
5.归并排序
归并排序是建立在归并操作上的一种有效的排序算法。
该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
归并排序是一种稳定的排序方法。
将已有序的子序列合并，得到完全有序的序列；
即先使每个子序列有序，再使子序列段间有序。
若将两个有序表合并成一个有序表，称为2-路归并。
代码实现
void Merge(vector<int>& arr,int left,int mid,int right){
int i = left,j = mid+1;
vector<int> temp;
while(i<=mid && j<=right){
if(arr[i]<=arr[j]) temp.push_back(arr[i++]);
else temp.push_back(arr[j++]);
}
while(i<=mid) temp.push_back(arr[i++]);
while(j<=right) temp.push_back(arr[j++]);
for(int k=0;k<temp.size();k++){
arr[left+k] = temp[k];
}
return ;
}
void MergeSort(vector<int>& arr,int left,int right){
if(left<right){
int mid = (left+right)/2;
MergeSort(arr,left,mid);
MergeSort(arr,mid+1,right);
Merge(arr,left,mid,right);
}
return ;
}
6.堆排序
堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。
堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
代码实现
void swap(int& a,int& b){
int temp = a;
a = b;
b = temp;
return ;
}
void Max_Heapify(vector<int>& arr,int start,int end){
int dad = start;
int son = dad*2+1;
while(son<=end){
if(son+1<=end && arr[son]<arr[son+1]) son++;
if(arr[dad]>arr[son]) return ;
else{
swap(arr[dad],arr[son]);
dad = son;
son = dad*2+1;
}
}
return ;
}
void Build_Max_Heap(vector<int>& arr){
int len = arr.size();
for(int i=len/2-1;i>=0;i--) Max_Heapify(arr,i,len-1);
return ;
}
void HeapSort(vector<int>& arr){
Build_Max_Heap(arr);
for(int i=arr.size()-1;i>=1;i--){
swap(arr[0],arr[i]);
Max_Heapify(arr,0,i-1);
}
return ;
}
7.计数排序
计数排序不是基于比较的排序算法，
其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。
作为一种线性时间复杂度的排序，
计数排序要求输入的数据必须是有确定范围的整数。
代码实现
void CountingSort(vector<int>& arr){
int len = arr.size();
if(len<=1) return ;
int max = arr[0],min = arr[0];
for(int i=1;i<len;i++) max = max>arr[i]?max:arr[i];
for(int i=1;i<len;i++) min = min<arr[i]?min:arr[i];
vector<int> count(max-min+1,0);
for(int i=0;i<len;i++) count[arr[i]-min]++;
int index = 0;
for(int i=min;i<=max;i++)
while(count[i-min]--) arr[index++] = i;
return ;
}
8.桶排序
桶排序是计数排序的升级版。
它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。
代码实现
void BucketSort(vector<int>& arr){
int len = arr.size();
if(len<=1) return ;
int max = arr[0],min = arr[0];
for(int i=1;i<len;i++) max = max>arr[i]?max:arr[i];
for(int i=1;i<len;i++) min = min<arr[i]?min:arr[i];
int d = max-min;
vector<vector<int> > bucket(d+1);
for(int i=0;i<len;i++) bucket[arr[i]-min].push_back(arr[i]);
int index = 0;
for(int i=0;i<=d;i++)
sort(bucket[i].begin(),bucket[i].end());
for(int i=0;i<=d;i++)
for(int j=0;j<bucket[i].size();j++)
arr[index++] = bucket[i][j];
return ;
}
9.基数排序
基数排序是按照低位先排序，
然后收集；再按照高位排序，然后再收集；以此类推，直到最高位。
有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的结果就是一种排序方式。
代码实现
void RadixSort(vector<int>& arr){
int len = arr.size();
if(len<=1) return ;
int max = arr[0],min = arr[0];
for(int i=1;i<len;i++) max = max>arr[i]?max:arr[i];
for(int i=1;i<len;i++) min = min<arr[i]?min:arr[i];
int d = max-min;
vector<vector<int> > bucket(10);
for(int i=0;i<len;i++) bucket[(arr[i]-min)/d%10].push_back(arr[i]);
int index = 0;
for(int i=0;i<10;i++)
sort(bucket[i].begin(),bucket[i].end());
for(int i=0;i<10;i++)
for(int j=0;j<bucket[i].size();j++)
arr[index++] = bucket[i][j];
return ;
}
10.快速排序
快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，
其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，
以达到整个序列有序。
代码实现
void QuickSort(vector<int>& arr,int left,int right){
if(left>=right) return ;
int i = left,j = right,x = arr[left];
while(i<j){
while(i<j&&arr[j]>=x) j--;
if(i<j) arr[i++] = arr[j];
while(i<j&&arr[i]<=x) i++;
if(i<j) arr[j--] = arr[i];
}
arr[i] = x;
QuickSort(arr,left,i-1);
QuickSort(arr,i+1,right);
return ;
}
//快速排序优化 三数取中法
void QuickSort2 (vector<int>& nums,int left,int right){
if(left >= right) {
return;
}
int mid = left + (right - left) / 2;
int pivot = nums[mid];
int i = left, j = right;
while (i <= j) {
while (nums[i] < pivot) {
i++;
}
while (nums[j] > pivot) {
j--;
}
if (i <= j) {
swap(nums[i], nums[j]);
i++;
j--;
}
}
QuickSort2(nums, left, j);
QuickSort2(nums, i, right);
}