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 (n2)，不穩定。
• 堆排序：利用堆的特性，時間復雜度 O (n log n)，空間復雜度 O (1)，不穩定。
• 插入排序：適合近乎有序的數據，時間復雜度 O (n2)，穩定。
• 希爾排序：插入排序的優化版，通過增量分組減少移動次數，時間復雜度與增量有關，不穩定。
• 冒泡排序：通過相鄰元素交換 “浮” 出最大元素，時間復雜度 O (n2)，穩定（可優化）。
• 快速排序：分治法的典型應用，平均時間復雜度 O (n log n)，最壞 O (n2)，不穩定，有多種分區實現（hoare、挖坑、lomuto 等）。
• 歸并排序：分治法，時間復雜度 O (n log n)，空間復雜度 O (n)，穩定。
• 計數排序：非比較排序，適合范圍小的整數，時間復雜度 O (n + k)，穩定（標準實現）。