作者：周子逸
ID：初雪_Matt
學校：長沙市芙蓉區(qū)育才小學， 四年級
博客地址：https://www./blog/magic-matt/pai-xu-suan-fa-jiu-zhao-wo

排序算法

排序名稱	時間復雜度	額外空間復雜度
冒泡排序(bubble sort)	最差、平均都是，最好是
插入排序(insertion sort)	最差、平均都是，最好是
歸并排序(merge sort)	最差、平均、最好都是
選擇排序(Selection sort)

一. 冒泡排序

1 冒泡排序流程

排序是指將一個無序序列按照某個規(guī)則進行有序排列，而冒泡排序是排序算法中最基礎的一種?，F(xiàn)給出一個序列，其中元素的個數(shù)為，要求將他們從小到大的順序排序。

冒泡排序的本質(zhì)就是交換，即每次通過交換的方法把當前剩余元素的最大值移動到一端，而當剩余元素減少到為0時，排序結束。為了讓排序的過程更加清楚，舉個例子

現(xiàn)在有個數(shù)組，其中有個元素，分別為，, , ,

演示

第一輪：

第二輪：

5已確認位置

第三輪：

5,4已確認位置

全已排好！

冒泡排序是一種穩(wěn)定排序！

Q：啥是穩(wěn)定排序？

A: 穩(wěn)定排序是指在原數(shù)組中相等的兩個元素在排完序后，其相對位置不發(fā)生改變，這種排序就被稱之為穩(wěn)定排序。

2 冒泡排序的實現(xiàn)

??使用雙重循環(huán)，內(nèi)層變量為， 外層為，在內(nèi)層循環(huán)中不斷的比較相鄰的兩個值的大小，如果的值大于的值，交換兩者位置，每循環(huán)一次，外層的增加，等到等于的時候，結束循環(huán)。

3 程序實現(xiàn)

#include<bits/stdc++.h>
using namespace std;
int n, a[10005], ans;
int main(){
   cin>>n;//幾個數(shù)字
   for(int i=0; i<n; i++){
       cin>>a[i];//讀入
   }
   for(int i=0; i<n-1; i++){ //依次確定從n到2這些位置的數(shù) 
       for(int j=0; j<n-i-1; j++){ //枚舉相鄰兩個元素
       if(a[j] > a[j+1]){  
               swap(a[j],a[j+1]);//交換兩數(shù)
               ans++;
           }
    }
   }
   for(int i=1;i<=n;i++) cout<<a[i]<<' ';//輸出整理后數(shù)組

   return 0;
}

4 優(yōu)秀好題

P1116   車廂重組(洛谷)

思路：

這道題完全是個板子題，重組時的反轉其實跟前面敘述的兩數(shù)交換是一樣的，完全可以用冒泡排序做，但要注意最后輸出的是需要的次數(shù)，不是換完以后的數(shù)組，在循環(huán)里面弄個就行了

:

#include<bits/stdc++.h>
using namespace std;
int n, a[10005], ans;
int main(){
   cin>>n;
   for(int i=0; i<n; i++){
       cin>>a[i];
   }
   for(int i=0; i<n-1; i++){  
       for(int j=0; j<n-i-1; j++){ 
           if(a[j] > a[j+1]){  
               swap(a[j],a[j+1]);
               ans++;//每執(zhí)行一次交換ans++
           }
 }
   }
   cout<<ans;//輸出統(tǒng)計次數(shù) 
   return 0;//結束撒花！
}

P1716   雙調(diào)序列(洛谷)

思路：

這道題十分的簡單，題面已經(jīng)介紹的很清楚了，至于代碼編寫過程，有兩個坑，第一個是冒泡排序后的輸出該怎么弄，其實可以用的雙變量循環(huán)，這樣就可以兩頭同時查找并輸出，注意換行，第二個坑是要判斷當兩個變量碰到一起的時候要輸出最中間的，由于中的除號自帶整除效果，所以要將所有的都加再才行。

#include<bits/stdc++.h>
using namespace std;
int n,i,j;//注意雙變量需提前設置
int a[1050];//數(shù)組開大點
int main(){
   cin>>n;
   for(int i=1;i<=n;i++)
      cin>>a[i];
   for(int i=n-1;i>=1;i--){
      for(int j=1;j<=i;j++){
         if(a[j]<a[j+1])
            swap(a[j],a[j+1]);
      }
   }//可愛的冒泡排序
   for(i=1,j=n;i<j;i++,j--)//雙變量循環(huán)格式需牢記
      cout<<a[i]<<endl<<a[j]<<endl;
   if(i==j)//特判遇到一起的情況
      cout<<a[(n+1)/2];
   return 0;
}

AT953 マッサージチェア(洛谷)

思路：

這道題比上一道題難一些，但還是板子，一共六個數(shù)，分為學生和座椅，不能混合在一起，需要個數(shù)組，數(shù)組不用開太大，因為只有個數(shù)，將兩個數(shù)組都冒泡排序一下，再設置一個，循環(huán)三次就行了（島國題要換行！）

#include <bits/stdc++.h>
using namespace std;
int a[5],b[5],temp,ans=0;
int main(){
   for(int i=1;i<=3;i++){
      cin>>a[i];
   }
   for(int i=1;i<=3;i++){
      cin>>b[i];
   }
   for(int i=1;i<3;i++){
      for(int j=i+1;j<=3;j++){
         if(a[i]>a[j]){
            swap(a[i],a[j]);
         }
      }
   }
   for(int i=1;i<3;i++){
      for(int j=i+1;j<=3;j++){
         if(b[i]>b[j]){
            swap(b[i],b[j]);
         }
      }
   }
   for(int i=1;i<=3;i++){
       ans=ans+abs(a[i]-b[i]);
   }  
   cout<<ans<<endl;//注意換行
   return 0;
} 

中間有行代碼很奇怪，你可能會問倒數(shù)第5行不是嗎，加個干嘛，其實要考慮比大的情況，那豈不是成了負數(shù)，為了防止這個情況，要加個絕對值

P1012 [NOIP1998 提高組] 拼數(shù)

思路：
這道題是冒泡的變形，沒什么好講的，很簡單

code：

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    string a[25];
    for(int i=1;i<=n;i++){
        cin>>a[i];
    } 
    
    for(int i=n;i>=1;i--){
        for(int j=1;j<=i;j++){
            if(a[j]+a[j+1]<a[j+1]+a[j]) swap(a[j],a[j+1]);
        }
    }
    
    for(int i=1;i<=n;i++){
        cout<<a[i];
    }
    return 0;
}

二. 選擇排序

1 選擇排序流程

選擇排序也是最簡單的排序算法之一，如下圖所示，選擇排序是指，對一個序列中的元素到,令從1到枚舉，每趟從待排序部分中選擇最小的元素，令其與待排序部分的第一個元素進行交換，這樣元素就會與當前有序區(qū)間形成新的有序區(qū)間,在趟操作后，所有元素才是有序的。

2 選擇排序實現(xiàn)

依次從到個位置，用來枚舉，每一次通過找最值將第一?。ɑ虻趇大）的數(shù)放入第二個位置，再用個來枚舉到的區(qū)間，如果的話，,由于不能改變，要提前把一個變量，然后循環(huán)完后進行兩數(shù)交換。

3 程序實現(xiàn)

#include<bits/stdc++.h>
using namespace std;
int n, a[10005], ans;
int main(){
   cin>>n;//幾個數(shù)字
   for(int i=0; i<n; i++){
       cin>>a[i];//讀入
   }
   for(int i = 1;i<=n-1;i++){//枚舉1到n-1
       int pos=i;//提前賦值
       for(int j=i+1;j<n;j++){//枚舉i+1到n的區(qū)間
          if(a[j]<a[pos]) pos=j;//相當于i=j
       }
       swap(a[i],a[pos]);//交換最終兩數(shù)
   }
   for(int i=1;i<=n;i++) cout<<a[i]<<' ';//輸出整理后數(shù)組 
   return 0;
}

4 優(yōu)秀好題

AT1313 カードと兄妹

思路：

輸入數(shù)組后將對它排序，直接用選擇排序模板先排好序，注意下標從開始，再用個循環(huán)統(tǒng)計奇數(shù)還是偶數(shù)大，每次循環(huán)弄個即可，最后輸出就好了。

#include <bits/stdc++.h>
using namespace std;
int n, num[1010];
int ans;
int main() {
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> num[i];
    }//輸入不多說
    for(int i;i<=n-1;i++){
     int pos=i;
     for(int j=i+1;j<n;j++){
      if(num[j]<num[pos]) pos=j;
        }
 swap(num[i],num[pos]);
    }//選擇排序模板
    for (int i = n - 1; i >= 0; i -= 2) {
        ans += num[i];
    }//統(tǒng)計ans
    cout << ans << endl;
    return 0;
}

三. 插入排序

1 插入排序流程

插入排序的過程就像插牌一樣，要有順序的將撲克牌插好，插入排序便是如此，每次確定一個元素，枚舉到比它大的時候，將它插到那個大的前面去，下面用個例子來解釋。

假設現(xiàn)在,共個元素，則次操作

通過上面例子，你應該對直接插入排序的過程有了個清晰的了解。可以看到，插入排序是將待插入元素一個個插入到初始有序部分，插入的位置遵循了使插入后依然有序的原則，一般都是從后往前枚舉有序部分來進行插入的

2 插入排序實現(xiàn)

放到代碼的注釋里了！

3 插入排序代碼

下面就不給千篇一律的主函數(shù)代碼了

void insertSort(){
   for(int i=2;i<=n;i++){//從2到n枚舉起，因為第一個一定有序
      int val=a[i];//存當前的數(shù)
      int j=i-1;//定義j，注意因為是倒著的所以是i-1
      while(j>=1&&a[j]>val){//判斷是否滿足插入條件
         a[j+1]=a[j];//如果滿足即插入
         j--;//再減1循環(huán)
      }
      a[j+1]=val;//注意存當前插入過的位置
   }
   return ;//void函數(shù)，不需要返回值
}

4 優(yōu)秀好題

插入排序與冒泡和選擇是一樣的，題目都可以做，在這里就不講了。

這里指給大家留下一道我自己創(chuàng)造的一個練習題，歡迎來看練習題(https://www./problem/U160403)

四. 歸并排序

1 歸并排序流程

歸并排序是基于“歸并”這個思想的排序方法，它的排序原理是：將序列兩兩分組,將序列歸并為 個組，組內(nèi)單獨排序；然后再將這些組兩兩歸并，生成 個組，組內(nèi)再單獨排序，依次類推，直到只剩下一個組為止，時間復雜度為。

同樣，我們再來看一個例子，要將序列{66,12,33,57,64,27,18}進行歸并排序。

① 第一趟，兩兩分組，得到四組：{66,12}，{33,57}，{64,27}，{18}，組內(nèi)單獨排序得到新序列：

② 第二趟，將四個組繼續(xù)并起來，得到兩組：，組內(nèi)單獨排序，得到新序列

③ 第三趟，將兩個組繼續(xù)并起來，得到了一組{12,33,57,66,18,27,64}，組內(nèi)單獨排序，得到新序列{12,18,27,33,57,64,66}。算法結束

整個過程如下圖4-1一樣!

2 插入排序實現(xiàn)

放到代碼的注釋里了！

3 程序實現(xiàn)

這個算法用遞歸比較簡單，只需要反復將當前區(qū)域[left,right]分成兩半，然后將該區(qū)域進行搜索，最后進行合并與排序

code：

#include <bits/stdc++.h>
using namespace std;
int a[100005],tmp[100005],n;
void mergesort(int lt,int rt){
   if(lt==rt) return ;
   int mid=(lt+rt)/2;
   mergesort(lt,mid);//排左半邊
   mergesort(mid+1,rt);//排右半邊
   int i=lt,j=mid+1,p=lt;
   while(i<=mid&&j<=rt){
      if(a[i]<a[j]) tmp[p++]=a[i++];
      else tmp[p++]=a[j++];
   }
   while(i<=mid)//如果左半邊還有數(shù)
      tmp[p++]=a[i++];
   while(j<=rt)//如果右半邊還有數(shù)
      tmp[p++]=a[j++];
   for(int k=lt;k<=rt;k++) a[k]=tmp[k];
   return ;
}
int main(){
   cin>>n;
   for(int i=1;i<=n;i++){
      cin>>a[i];
   }
   mergesort(1,n);//排序邊界
   for(int i=1;i<=n;i++){
      cout<<a[i]<<' ';
   }
   return 0;
}

4 優(yōu)秀好題

因為歸并排序代碼繁多，不如其它三種排序，me還沒有找到合適的題目，只要不卡時間盡量不用它，前面的都可以用它來做，只不過模板會改很多而已。