| 類型 | 時間複雜度（平均） | 時間複雜度（最壞） | 時間複雜度（最好） | 空間複雜度 | 穩定性 |
|---|---|---|---|---|---|
| 插入排序 | O（n2） | O（n2） | O（n） | O（1） | 穩定 |
| 歸并排序 | O（nlogn） | O（nlogn） | O（nlogn） | O（n） | 穩定 |
| 快速排序 | O（nlogn） | O（n2） | O（n） | O（nlogn） | 不穩定 |
| 堆排序 | O（nlogn） | （nlogn） | （nlogn） | O（1） | 不穩定 |
| 選擇排序 | O（n2） | （n2） | （n2） | O（1） | 不穩定 |
| 冒泡排序 | O（n2） | （n2） | （n2） | O（1） | 穩定 |
| 計數排序 | O（n+k） | O（n+k） |
1.插入排序
可以聯想成打撲克時手裡拿牌的一個過程，手裡的牌總是有序的，摸的牌依次比較，放入正确的位置。
#include<iostream>
#include<vector>
using namespace std;
void insertsort(vector<int> &arr)
{
for(int i=;i<arr.size();i++)//i與之前的進行比較
{
int j=i-;
int temp=arr[i];
while(j>= && arr[j]>arr[i] )
{
arr[j+]=arr[j];
j--;
}
arr[j+]=temp;
}
}
int main()
{
vector<int> arr;
arr.push_back();
arr.push_back();
arr.push_back();
arr.push_back();
arr.push_back();
arr.push_back();
insertsort(arr);
for(int i=;i<arr.size();i++)
{
cout<<arr[i]<<endl;
}
}
2.歸并排序
聯想成桌面有兩組牌，依舊比較牌面最上面的牌最小的排好序。
void merge(vector<int> &arr,int p,int q,int r)
{
vector<int> L;
vector<int> R;
for(int i=p;i<=q;i++)
{
L.push_back(arr[i]);
};
L.push_back(INT_MAX);
for(int i=q+;i<=r;i++)
{
R.push_back(arr[i]);
}
int i=,j=;
R.push_back(INT_MAX);
for(int k=p;k<=r;k++)
{
if(L[i]<=R[j])
{
arr[k]=L[i];
i++;
}
else if(R[j]<=L[i])
{
arr[k]=R[j];
j++;
}
}
}
void mergesort(vector<int> &arr,int p, int r)
{
if (p<r)
{
int q = (p+r)/;
mergesort(arr, p, q);
mergesort(arr, q+, r);
merge(arr, p, q, r);
}
}
3.快速排序
快排主要在于一趟快排的過，即從後向前依次尋找比x小的數，找到了交換，同時i增加。使得x的左邊小于x，右邊大于x。
int partition(vector<int> &A,int p,int r)
{
int i=p-;
int x=A[r];
for(int j=p;j<r;j++)
{
if(A[j]<x)
{
i++;
swap(A[i],A[j]);
}
}
swap(A[i+],A[r]);
return i+;
}
void quicksort(vector<int> &A,int p,int r)
{
if(p<r)
{
int q=partition(A,p,r);
quicksort(A,p,q-);
quicksort(A,q+,r);
}
}
4.堆排序
建立最大堆，聯想建立堆首先要想到維護堆的過程，維護堆則需要比較節點i的左右孩子是否大于i，如果大于則交換，同時繼續向下維護。
建立堆則是除去葉子節點，對其他節點依次進行維護。
現在堆頂元素是最大的元素，交換堆頂與arr[n],堆的大小減1，則去掉堆頂，最剩餘元素進行維護。
void heapify(vector<int> &arr,int heap_size,int i)
{
int left=*i+;
int right=*i+;
int largest;
if(left<heap_size &&arr[left]>arr[i])
largest=left;
else
largest=i;
if(right<heap_size &&arr[right]>arr[largest])
largest=right;
if(largest!=i)
{
swap(arr[i],arr[largest]);
heapify(arr,heap_size,largest);
}
}
void build_heap(vector<int> &arr)
{
//除去葉子節點，進行維護
for(int i=(arr.size()-)/;i>=;i--)
heapify(arr,arr.size(),i);
}
void heap_sort(vector<int> &arr)
{
//先建堆
build_heap(arr);
int heap_size=arr.size();
//再維護,A[0]現在是最大的元素，與A[i]交換，再維護
for(int i=arr.size()-;i>;i--)
{
swap(arr[],arr[i]);
heap_size=heap_size-;
heapify(arr,heap_size,);
}
}
5.選擇排序
這個比較簡單，其實就是依次比較出最小的數。
void SelectionSort(vector<int> &arr)
{
for(int i=;i<arr.size();i++)
for(int j=i+;j<arr.size();j++)
{
if(arr[j]<arr[i])
swap(arr[j],arr[i]);
}
}
6.冒泡排序
聯想魚吐泡泡的樣子，大的泡泡總是在上面，是以需要将相鄰的兩個數進行比較，将後面的較大數先比較出來
void BubbleSort(vector<int> &arr)
{
for(int i=;i<arr.size();i++)
for(int j=;j<arr.size()-i-;j++)
{
if(arr[j]>arr[j+])
{
swap(arr[j],arr[j+]);
}
}
}
7.計數排序
聯想哈希表，計數排序從名字上記憶就是比x小的有m個，則x應該在m位（數組從0開始）
vector<int> CountingSort(vector<int> arr,int k)//k是arr數組元素的範圍，0-k
{
int len=arr.size();
vector<int> temp(k+,);
vector<int> res(len,);
for(int i=;i<len;i++)
{
temp[arr[i]]=temp[arr[i]]+;
}
for(int i=;i<=k;i++)
{
temp[i]=temp[i-]+temp[i];
}
for(int i=len-;i>=;i--)
{
res[temp[arr[i]]-]=arr[i];
temp[arr[i]]=temp[arr[i]]-;
}
return res;
}
8.基數排序