排序算法，咕咕咕
1.选择排序
void selectsort(vector<int>& v)
{
for(int i=0;i<v.size()-1;i++)
{int mini=i;for(int j=i+1;j<v.size();j++){if(v[i]>v[j]){mini=j;}}if(mini!=i)swap(v[i],v[mini]);
}
}2.堆排序
void adjustdown(vector<int>& v,int root,int size)
{
int largest=root;
int left=2*root+1;
int right=2*root+2;
if(left<size&&v[left]>v[largest]) largest=left;
if(right<size&&v[right]>v[largest]) largest=right;
if(largest!=root)
{swap(v[root],v[largest]);adjustdown(v,largest,size);
}}
void heapsort(vector<int>& v)
{
int n=v.size();
for(int i=n/2-1;i>=0;i--) 非叶子结点
{adjustdown(v,i,n);
}
for(int i=n-1;i>0;i--) 大堆只是父结点大于子节点，相邻子节点不一定大于
{
swap(v[i],v[0]);
adjustdown(v,0,n);
}
}3.插入排序
void insertsort(vector<int>& v)
{int n=v.size();for(int i=1;i<n;i++){int key=v[i];int j=i-1;while(j>=0&&v[j]>key){v[j+1]=v[j];j--;}v[j+1]=key;}
}4.希尔排序
void shellsort(vector<int>& v)
{int n=v.size();int gap=1;while(gap<n/3){gap=gap*3+1;}for(;gap>0;gap=(gap-1)/3){for(int i=gap;i<n;i++){int key=v[i];int j=i-gap;while(j>=0&&v[j]>key){v[j+gap]=v[j];j-=gap;}v[j+gap]=key;}}
}5.冒泡排序
void bubblesort(vector<int>& arr)
{for(int i=0;i<arr.size()-1;i++){for(int j=0;j<arr.size()-1-i;j++){if(arr[j]>arr[j+1]){swap(arr[j],arr[j+1]);}}}
}6.快速排序
//快速排序 hoare法
int findkeyi(vector<int>& arr,int left,int right)
{
int pivot=arr[left];
int i=left-1;
int j=right+1;
while(true)
{do{i++;}while(arr[i]<pivot);do{j++;}while(arr[j]>pivot);if(i>=j) return j;swap(arr[i],arr[j]);
}
}
void quicksort(vector<int>& arr,int left,int right)
{
if(left<right)
{int gugu=findkeyi(arr,left,right);quicksort(arr,left,gugu);quicksort(arr,gugu+1,right);
}
}
//挖坑法
int findkeyi(vector<int>& arr,int left,int right)
{int pivot=arr[left];int hole=left;while(left<right){while(left<right&&arr[right]>=pivot) right--;arr[hole]=arr[right];hole=right;while(left<right&&arr[left]<=pivot) left++;arr[hole]=arr[left];hole=left;}arr[hole]=pivot;return hole;
}
void quicksort(vector<int>& arr,int left,int right)
{if(left<right){int gugu=findkeyi(arr,left,right);quicksort(arr,left,gugu-1);quicksort(arr,gugu+1,right);}
}
//lomuto
int findkeyigugu(vector<int>& arr,int left,int right)
{int pivot=arr[right];int i=left-1;for(int j=left;j<right;j++){if(arr[j]<pivot){i++;swap(arr[i],arr[j]);}}swap(arr[i+1],arr[right]);return i+1;
}
void quicksort(vector<int>& arr,int left,int right)
{if(left<right){int gugu=findkeyi(arr,left,right);quicksort(arr,left,gugu-1);quicksort(arr,gugu+1,right);}
}
//非递归双指针
void quicksort(vector<int>& arr,int left,int right)
{stack<pair<int,int>> st;st.push({left,right});while(!st.empty()){auto [l,r]=st.top();st.pop();if(l>=r) continue;int gugu=findkeyigugu(arr,l,r);st.push({gugu+1,r});st.push({l,gugu-1});}
}7.归并排序
void merge(vector<int>& arr,int left,int mid,int right)
{int n1=mid-left+1;int n2=right-mid;vector<int> gu(n1),gugu(n2);for(int i=0;i<n1;i++){gu[i]=arr[left+i];}for(int j=0;j<n2;j++){gugu[j]=arr[mid+1+j];}int i=0;int j=0;int k=left;while(i<n1&&j<n2){if(gu[i]<gugu[j]){arr[k]=gu[i];i++;}else{arr[k]=gugu[j];j++;}k++;}while(i<n1){arr[k]=gu[i];i++;k++;}while(j<n2){arr[k]=gugu[j];k++;j++;}
}
void mergesort(vector<int>& arr,int left,int right)
{if(left<right){int mid=left+(right-left)/2;mergesort(arr,left,mid);mergesort(arr,mid+1,right);merge(arr,left,mid,right);}
}8.计数排序
void countingsort(vector<int>& arr)
{if(arr.empty()) return;int min=*min_element(arr.begin(),arr.end());int max=*max_element(arr.begin(),arr.end());int l=max-min+1;vector<int> result(l,0);for(int num:arr){result[num-min]++; 每个数出现了几次，哈希的思想}int index=0;for(int i=0;i<l;i++){int num=i+min;while(result[i]>0){arr[index]=num;result[i]--;index++;}}
}9.总结
- 选择排序：简单直观，每次选最小元素交换，时间复杂度 O (n²)，不稳定。
- 堆排序：利用堆的特性，时间复杂度 O (n log n)，空间复杂度 O (1)，不稳定。
- 插入排序：适合近乎有序的数据，时间复杂度 O (n²)，稳定。
- 希尔排序：插入排序的优化版，通过增量分组减少移动次数，时间复杂度与增量有关，不稳定。
- 冒泡排序：通过相邻元素交换 “浮” 出最大元素，时间复杂度 O (n²)，稳定（可优化）。
- 快速排序：分治法的典型应用，平均时间复杂度 O (n log n)，最坏 O (n²)，不稳定，有多种分区实现（hoare、挖坑、lomuto 等）。
- 归并排序：分治法，时间复杂度 O (n log n)，空间复杂度 O (n)，稳定。
- 计数排序：非比较排序，适合范围小的整数，时间复杂度 O (n + k)，稳定（标准实现）。