排序算法一览
总览
| 排序算法 | 时间复杂度 | 空间复杂度 | 稳定性 | 原地排序？ |
| 冒泡排序 | &preview=true) | &preview=true) | 稳定 | 是 |
| 选择排序 | | | 不稳定 | 是 |
| 插入排序 | | | 稳定 | 是 |
| 希尔排序 | &preview=true) | | 不稳定 | 是 |
| 快速排序 | | &preview=true) | 不稳定 | 是 |
| 归并排序 | | &preview=true) | 稳定 | 否 |
| 基数排序 | )&preview=true) | &preview=true) | 稳定 | 否 |
| 堆排序 | O(nlogn) | O(1) | 不稳定 | 是 |
冒泡排序
/**
* @brief 冒泡排序
* 时间复杂度 O(n^2)
* 空间复杂度 O(1)
* 原地排序 稳定
*
* @param nums
*/
void bubbleSort(vector<int>& nums){
int n=nums.size();
for(int i=0;i<n-1;++i){
for(int j=0;j<n-i-1;++j){
if(nums[j]>nums[j+1]){
int t=nums[j];
nums[j]=nums[j+1];
nums[j+1]=t;
}
}
}
}
/*优化*/
void bubbleSort(vector<int>& nums){
int n=nums.size();
for(int i=0;i<n-1;++i){
int flag=1; //标记位，为1表示已经有序，为0表示尚未有序
for(int j=0;j<n-i-1;++j){
if(nums[j]>nums[j+1]){
int t=nums[j];
nums[j]=nums[j+1];
nums[j+1]=t;
flag=0;
}
}
if(flag) break;
}
} 选择排序
/**
* @brief 选择排序
* 时间复杂度 O(n^2)
* 空间复杂度 O(1)
* 原地排序 不稳定（会将重复的后面的较小值交换到前面来）
* @param nums
*/
void selectSort(vector<int>& nums){
int n=nums.size();
for(int i=0;i<n-1;++i){
int mini=i;
for(int j=i+1;j<n;++j){
if(nums[mini]>nums[j]){
mini=j;
}
}
if(mini!=i){
int t=nums[mini];
nums[mini]=nums[i];
nums[i]=t;
}
}
} 插入排序
/**
* @brief 插入排序
* 时间复杂度 O(n^2)
* 空间复杂度 O(1);
* 原地排序 稳定
*
* @param nums
*/
void insertSort(vector<int>& nums){
int n=nums.size();
for(int i=1;i<n;++i){
if(nums[i]<nums[i-1]){
int temp=nums[i];
int j;
for(j=i;nums[j-1]>temp&&j>0;--j){
nums[j]=nums[j-1];
}
nums[j]=temp;
}
}
} 希尔排序
/**
* @brief 希尔排序
*时间复杂度 O(nlogn) 最坏 O(n^s)
*空间复杂度 O(1)
*原地排序 不稳定
* @param nums
*/
void sheelSort(vector<int> &nums){
int n=nums.size();
int gap=1,i,j;
while(gap<n/3){
gap=3*gap+1;
}
while(gap>=1){
for(i=gap;i<n;i++){
if(nums[i]<nums[i-gap]){
int temp=nums[i];
for( j=i-gap;j>=0&&nums[j]>temp;j-=gap){
nums[j+gap]=nums[j];
}
nums[j+gap]=temp;
}
}
gap=gap/3;
}
} 快速排序
/**
* @brief 快速排序
* 时间复杂度 O(nlogn); 最坏O(n^2)
* 空间复杂度 O(logn)
* 原地排序，不稳定
*/
void quickSort(vector<int>& nums,int left,int right){
if(left>=right){
return;
}
int temp=nums[left];
int i=left,j=right;
while(i!=j){
while(nums[j]>=temp&&i<j){
--j;
}
while(nums[i]<=temp&&i<j){ //i及左侧必然小于等于temp
++i;
}
if(i<j){
int t=nums[i];
nums[i]=nums[j];
nums[j]=t;
}
}
nums[left]=nums[i];
nums[i]=temp;
quickSort(nums,left,i-1);
quickSort(nums,i+1,right);
}
void quickSortP(vector<int>& nums,int left,int right){
if(left>=right){
return;
}
int temp=nums[left];
int i=left,j=right;
while(i<j){
while(nums[j]>=temp&&i<j){
--j;
}
while(nums[i]<=temp&&i<j){ //i及左侧必然小于等于temp
++i;
}
if(i<j){
int t=nums[i];
nums[i]=nums[j];
nums[j]=t;
}
}
nums[left]=nums[i];
nums[i]=temp;
quickSortP(nums,left,i-1);
quickSortP(nums,i+1,right);
} 归并排序
/**
* @brief 归并排序
* 时间复杂度 O(nlogn)
* 空间复杂度 O(n)
* 非原地排序 稳定
*
* @param nums
*/
//递归计算
void mergeSort(vector<int>& nums,int left,int right){
if(left>=right){
return;
}
int mid=(left+right)/2;
mergeSort(nums,left,mid);
mergeSort(nums,mid+1,right);
vector<int> temp(right-left+1);
int i=left,j=mid+1,k=0;
while(i<=mid||j<=right){
if(i>mid){
temp[k++]=nums[j++];
}
else if(j>right){
temp[k++]=nums[i++];
}
else{
if(nums[i]<=nums[j]){
temp[k++]=nums[i++];
}
else{
temp[k++]=nums[j++];
}
}
}
for(int t=0;t<temp.size();++t){
nums[left+t]=temp[t];
}
}
//迭代计算
void mergeSortD(vector<int>& nums){
int n=nums.size();
int left,right;
vector<int> temp(n,0);
for(int i=2;i<n;i*=2){
for(left=0;left<n-i;left+=i){
right=left+i-1;
if(right>=n) right=n-1;
int mid=(left+right)/2;
int l=left,r=mid+1,k=0;
while(l<=mid||r<=right){
if(l>mid){
temp[k++]=nums[r++];
}
else if(r>right){
temp[k++]=nums[l++];
}
else{
if(nums[l]<=nums[r]){
temp[k++]=nums[l++];
}
else{
temp[k++]=nums[r++];
}
}
}
for(k=0;k<right-left+1;++k){
nums[left+k]=temp[k];
}
}
}
return;
} 基数排序
/**
* @brief 基数排序
*
*/
void lsdSort(vector<int>& nums){
int n=nums.size();
int digit=0;
for(int i=0;i<n;++i){
while(nums[i]>(pow(10,digit))){
digit++;
}
}
int flag=1;
for(int j=1;j<=digit;++j){
vector<int> count(10);
for(int i=0;i<n;++i){
count[(nums[i]/flag)%10]++;
}
vector<int> index(10);
for(int i=1;i<10;++i){
index[i]=index[i-1]+count[i-1];
}
vector<int> temp(n);
for(int i=0;i<n;++i){
int begin=(nums[i]/flag)%10;
temp[index[begin]++]=nums[i];
}
for(int i=0;i<n;++i){
nums[i]=temp[i];
}
flag*=10;
}
} 堆排序
/**
* @brief 堆排序
*
* @param s
* @param nums
*/
void heapSort(vector<int> &nums){
int n=nums.size();
auto swap=[](int &a,int &b){
int t=a;
a=b;
b=t;
};
auto sink=[&](int s,int len){
int temp=nums[s-1];
for(int i=2*s;i<=len;i*=2){
if(i<len&&nums[i-1]<nums[i]){
i++;
}
if(temp>=nums[i-1]){
break;
}
nums[s-1]=nums[i-1];
s=i;
}
nums[s-1]=temp;
};
for(int i=n/2;i>0;i--){ //从下向上，从右向左调整
sink(i,n);
}
for(int i=n;i>1;--i){
swap(nums[0],nums[i-1]);
sink(1,i-1);
}
} 