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

排序算法

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

一. 冒泡排序

1 冒泡排序流程

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

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

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

演示

第一輪：

第二輪：

5已確認(rèn)位置

第三輪：

5,4已確認(rèn)位置

全已排好！

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

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

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

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

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

3 程序?qū)崿F(xiàn)

#include<bits/stdc++.h>
using namespace std;
int n, a[10005], ans;
int main(){
   cin>>n;//幾個(gè)數(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++){ //枚舉相鄰兩個(gè)元素
       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   車廂重組(洛谷)

思路：

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

:

#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)計(jì)次數(shù) 
   return 0;//結(jié)束撒花！
}

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

思路：

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

#include<bits/stdc++.h>
using namespace std;
int n,i,j;//注意雙變量需提前設(shè)置
int a[1050];//數(shù)組開大點(diǎn)
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 マッサージチェア(洛谷)

思路：

這道題比上一道題難一些，但還是板子，一共六個(gè)數(shù)，分為學(xué)生和座椅，不能混合在一起，需要個(gè)數(shù)組，數(shù)組不用開太大，因?yàn)橹挥?img doc360img-src='http://image109.360doc.com/DownloadImg/2021/07/0601/225695023_27_20210706012230114' src="http://pubimage.360doc.com/wz/default.gif" alt="圖片">個(gè)數(shù)，將兩個(gè)數(shù)組都冒泡排序一下，再設(shè)置一個(gè)，循環(huán)三次就行了（島國(guó)題要換行?。?/p>

#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;
} 

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

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

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

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 選擇排序流程

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

2 選擇排序?qū)崿F(xiàn)

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

3 程序?qū)崿F(xiàn)

#include<bits/stdc++.h>
using namespace std;
int n, a[10005], ans;
int main(){
   cin>>n;//幾個(gè)數(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;//相當(dāng)于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ù)組后將對(duì)它排序，直接用選擇排序模板先排好序，注意下標(biāo)從開始，再用個(gè)循環(huán)統(tǒng)計(jì)奇數(shù)還是偶數(shù)大，每次循環(huán)弄個(gè)即可，最后輸出就好了。

#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];
    }//輸入不多說(shuō)
    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)計(jì)ans
    cout << ans << endl;
    return 0;
}

三. 插入排序

1 插入排序流程

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

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

通過(guò)上面例子，你應(yīng)該對(duì)直接插入排序的過(guò)程有了個(gè)清晰的了解?？梢钥吹?，插入排序是將待插入元素一個(gè)個(gè)插入到初始有序部分，插入的位置遵循了使插入后依然有序的原則，一般都是從后往前枚舉有序部分來(lái)進(jìn)行插入的

2 插入排序?qū)崿F(xiàn)

放到代碼的注釋里了！

3 插入排序代碼

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

void insertSort(){
   for(int i=2;i<=n;i++){//從2到n枚舉起，因?yàn)榈谝粋€(gè)一定有序
      int val=a[i];//存當(dāng)前的數(shù)
      int j=i-1;//定義j，注意因?yàn)槭堑怪乃允莍-1
      while(j>=1&&a[j]>val){//判斷是否滿足插入條件
         a[j+1]=a[j];//如果滿足即插入
         j--;//再減1循環(huán)
      }
      a[j+1]=val;//注意存當(dāng)前插入過(guò)的位置
   }
   return ;//void函數(shù)，不需要返回值
}

4 優(yōu)秀好題

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

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

四. 歸并排序

1 歸并排序流程

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

同樣，我們?cè)賮?lái)看一個(gè)例子，要將序列{66,12,33,57,64,27,18}進(jìn)行歸并排序。

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

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

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

整個(gè)過(guò)程如下圖4-1一樣!

2 插入排序?qū)崿F(xiàn)

放到代碼的注釋里了！

3 程序?qū)崿F(xiàn)

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

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)秀好題

因?yàn)闅w并排序代碼繁多，不如其它三種排序，me還沒有找到合適的題目，只要不卡時(shí)間盡量不用它，前面的都可以用它來(lái)做，只不過(guò)模板會(huì)改很多而已。