排序方法動(dòng)畫講解酱塔，go語(yǔ)言實(shí)現(xiàn)，博客園大佬真滴多危虱。
https://www.cnblogs.com/onepixel/p/7674659.html
個(gè)人理解和C++代碼實(shí)現(xiàn)
//排序目標(biāo)是從小到大
冒泡排序：從前到后逐個(gè)比較相鄰兩個(gè)數(shù)字的大小羊娃，如果前大后小就交換，確保每相鄰兩個(gè)數(shù)字都是前小后大埃跷，每一次遍歷后蕊玷，保證遍歷終點(diǎn)位置的數(shù)字是遍歷過(guò)程中最大的（如果有比這個(gè)數(shù)字更大的邮利，一定會(huì)被交換到它的后面）
void BubbleSort(int (&num)[11]){
int n=11;
for(int i=0;i<n;i++){
for(int j=0;j<n-1-i;j++){
if(num[j]>num[j+1]){
int temp=num[j];
num[j]=num[j+1];
num[j+1]=temp;
}
}
}
}
雙重循環(huán)，時(shí)間復(fù)雜度為O（log（n^2)）;空間復(fù)雜度為O（1）垃帅；穩(wěn)定排序
選擇排序：每次從無(wú)序序列中選取最小的放到有序序列的末尾延届，每遍歷一次，有序序列就增加一個(gè)元素贸诚。
void SelectionSort(int (&num)[11]){
int n=11;
for(int i=0;i<n;i++){
//num[0]到num[i-1]是現(xiàn)有有序序列方庭；num[i]到num[n-1]是無(wú)序序列；
int minindex=i;
int j=i+1;
for(j=i+1;j<n;j++){
if(num[j]<num[minindex]){
minindex=j;
}
}
swap(num[i],num[minindex]);
}
}
雙重循環(huán)酱固，時(shí)間復(fù)雜度為O（log（n^2)）;空間復(fù)雜度為O（1）械念；不穩(wěn)定排序：涉及到不相鄰數(shù)字的交換
例如:(7) 2 5 9 3 4 [7] 1...當(dāng)我們利用直接選擇排序算法進(jìn)行排序時(shí)候,(7)和1調(diào)換,(7)就跑到了[7]的后面了,原來(lái)的次序改變了,這樣就不穩(wěn)定了.
插入排序：為每一個(gè)未排序元素在已排序序列中找到位置并插入，只保證已排序序列中元素滿足前后大小關(guān)系媒怯。
void InsertionSort(int (&num)[11]){
int n=11;
//默認(rèn)第一個(gè)數(shù)字是有序的
for(int i=1;i<n;i++){
int temp=num[i];
int preindex=i-1;
while(preindex>=0&&num[preindex]>temp){
num[preindex+1]=num[preindex];
preindex--;
}
num[preindex+1]=temp;
}
}
雙重循環(huán)订讼，時(shí)間復(fù)雜度為O（log（n^2)）;空間復(fù)雜度為O（1）；穩(wěn)定排序
希爾排序：分組多次進(jìn)行的直接插入排序扇苞，較插入排序有時(shí)間上的優(yōu)化欺殿，重要在于gap分組步長(zhǎng)的取值
void shellsort1(int (&num)[11]){
int i,j,gap;
int n=11;
for(gap=n/2;gap>0;gap/=2){
for(i=0;i<gap;i++){
for(j=i+gap;j<n;j+=gap){
if(num[j]<num[j-gap]){
int temp=num[j];
int current=j-gap;
while(current>=0&&num[current]>temp){
//while()條件里不能直接用num[j],因?yàn)閚um[j]也是數(shù)組
//一部分，會(huì)被改變鳖敷，要用temp存起來(lái)它的值
num[current+gap]=num[current];
current-=gap;
}
num[current+gap]=temp;
}
}
}
}
}
void shellsort2(int (&num)[11]){
int n=11;
int i,gap;
//改進(jìn)在于把三重循環(huán)改進(jìn)成兩重循環(huán)脖苏，將分組進(jìn)行的插入
//優(yōu)化成各組交替進(jìn)行的插入排序
for(gap=n/2;gap>0;gap/=2){
for(i=gap;i<n;i++){
if(num[i]<num[i-gap]){
int temp=num[i];
int current=i-gap;
while(current>=0&&num[current]>temp){
num[current+gap]=num[current];
current-=gap;
}
num[current+gap]=temp;
}
}
}
}
希爾排序的運(yùn)行時(shí)間依賴于增量序列的選擇，而證明很復(fù)雜定踱。棍潘。。崖媚。亦歉。。
平均時(shí)間復(fù)雜度按O(nlogn)計(jì)算畅哑，空間復(fù)雜度O(1),,,不穩(wěn)定排序肴楷，因?yàn)榇嬖诓煌M的插入排序。
歸并排序：遞歸的把兩個(gè)（或多個(gè)）有序的子串合并成一個(gè)有序的子串荠呐，遞歸到底就是把兩個(gè)單獨(dú)的數(shù)排序赛蔫，中心思想在于合并，分治的一種體現(xiàn)
void merge(int num[],int low,int mid,int high){
int *temp=new int[high-low+1];
int leftindex=low;
int rightindex=mid+1;
int tempk=0;
while(leftindex<=mid&&rightindex<=high){
if(num[leftindex]<num[rightindex]){
temp[tempk]=num[leftindex];
tempk++;
leftindex++;
}
else{
temp[tempk]=num[rightindex];
tempk++;
rightindex++;
}
}
while(leftindex<=mid){
temp[tempk] = num[leftindex];
tempk++;
leftindex++;
}
while(rightindex<=high){
temp[tempk] = num[rightindex];
tempk++;
rightindex++;
}
for(int i=low,tempk=0;i<=high,tempk<=high-low;i++,tempk++){
num[i]=temp[tempk];
}
delete []temp;
}
void MergeSort(int num[],int low,int high){
if(low>=high){
return ;
}
int mid=low+(high-low)/2;
MergeSort( num,low,mid);
MergeSort(num,mid+1,high);
merge(num,low,mid,high);
}
時(shí)間復(fù)雜度一直是O(nlogn)不隨輸入改變泥张，空間復(fù)雜度O(n),穩(wěn)定排序