排序大集合~

  • 2021 年 8 月 20 日
  • 筆記

       排序演算法：將雜亂無章的數據元素，通過一定的方法按關鍵字順序排列的過程

       排序的方法有許多種，如：插入排序、希爾排序、冒泡排序、歸併排序、選擇排序……這些不同排序的排序演算法，其中的原理也大不相同。

    （小聲嗶嗶：此篇部落格中排序演算法的定義參考了百度百科qwq……)

Part 1.按演算法分類

       

Part 2.按時間複雜度分類

       

 

 

開始貼程式碼啦！

（PS:以下所列的排序演算法均為從小到大排序）

      

      為了使數據有小到大（升序）排列，在比較和交換的過程中，越小的數就會像氣泡一樣慢慢地「浮」到數列的頂端，所以把這種演算法命名為「冒泡排序」。

      冒泡排序 簡易版（穩定）

#include<bits/stdc++.h>
using namespace std;
int a[1000001];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
      cin>>a[i];
    for(int i=1;i<=n-1;i++)//進行n-1輪比較 
      for(int j=1;j<=n-i;j++)//每輪比較n-i次 
        if(a[j]>a[j+1]) swap(a[j],a[j+1]);//比較大小，交換兩數位置 
    for(int i=1;i<=n;i++)
      cout<<a[i]<<" ";
}

 

 

       如下這種改良版的冒泡排序只要排序完成就會推出序列，這種方式已經減少了時間的許多浪費。假設現有一個長度10000的數組，前1000無序，後9000有序並且大於前1000數據。用上面這種方法，數據交換次數在1000之內，但是剩下9000的數據雖然沒有交換，但是每次循環都會進行比較。剩下9000數據已經有序了，我們不用對它們進行判斷，浪費不必要的時間。

      冒泡排序 改良版（穩定）

#include<bits/stdc++.h>
using namespace std;
int a[1000001];
bool f;
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
      cin>>a[i];
    for(int i=n-1;i>=1;i--)
    {
        f=true;//bool類型變數f判斷是否交換 
        for(int j=1;j<=i;j++)
        {
            if(a[j]>a[j+1])
            {
                swap(a[j],a[j+1]);
                f=false;
            }
        }
        if(f==true) break;
    }
    for(int i=1;i<=n;i++)
      cout<<a[i]<<" ";
}

 

               

                  

 

      基本思想：把n個待排序的元素看成為一個有序表和一個無序表，開始時有序表中只包含一個元素，無序表中包含有n-1個元素，排序過程中每次從無序表中取出第一個元素，將它插入到有序表中的適當位置，使之成為新的有序表，重複n-1次可完成排序過程。

      插入排序（穩定）

#include<bits/stdc++.h> 
using namespace std;
int a[1000001];
int main()
{
    int n,temp,i,j,k;
    cin>>n; 
    for(i=0;i<n;i++)
        cin>>a[i];
    for(i=0;i<n;i++)
    {
        for(j=i-1;j>=0;j--)
            if(a[j]<a[i]) break;//找到比a[i]小的位置就退出，插在它後面 
        if(j!=i-1)
        {
            temp=a[i];//將比a[i]大的數向後移 
            for(k=i-1;k>j;k--)
                a[k+1]=a[k];
            a[k+1]=temp;
        }
    }
    for(int i=0;i<n;i++)
      cout<<a[i]<<" ";
}

 

                                    

       桶排序 (Bucket sort)就是所謂的箱排序，是一個排序演算法，工作的原理是將數組分到有限數量的桶子里。每個桶子再進行個別排序（有可能再使用別的排序演算法或是以遞歸方式繼續使用桶排序進行排序）。桶排序是鴿巢排序的一種歸納結果。當要被排序的數組內的數值是均勻分配的時候，桶排序使用線性時間O(n)。但桶排序並不是比較排序，他不受到 O(n log n) 下限的影響。

桶排序（穩定）

#include<bits/stdc++.h>
using namespace std;
int a[1000001];
int main()
{
    int n,k;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>k;
        a[k]++;
    }
    for(int i=0;i<=1000000;i++)
    {
        while(a[i]>0)
        {
            cout<<i<<" ";
            a[i]--;//輸出一個整數後，個數減一 
        }
    }
 }

 

                   

      基本思想：先取一個小於n的整數d1作為第一個增量，把文件的全部記錄分組。所有距離為d1的倍數的記錄放在同一個組中。先在各組內進行直接插入排序；然後，取第二個增量d2 =1(dt，dt-1…

希爾排序（不穩定）

#include<bits/stdc++.h>
using namespace std;
int a[1000001];
int main()
{
    int n,k,j;
    cin>>n; 
    for(int i=1;i<=n;i++)
        cin>>a[i];
    int gap=n/2;
    while(gap>0)
    {
        for(int i=gap+1;i<=n;i++)
        {
            j=i;
            while(j-gap>0&&a[j]<a[j-gap])
            {
                swap(a[j],a[j-gap]);
                j=j-gap;
            }
        }
        gap=gap/2;
    }
    for(int i=1;i<=n;i++)
      cout<<a[i]<<" ";
}

 

 

                                    

      快速排序是冒泡排序的一種改進演算法。它也是通過不斷地比較和移動交換來實現排序，只不過它的實現增大了記錄的比較和移動的距離，將關鍵字較大的元素從前面直接放到後面，關鍵字較小的元素直接從後面放到前面，從而減小了比較次數和交換次數。

快速排序（不穩定）

#include<bits/stdc++.h>
using namespace std;
int a[10000001];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
      cin>>a[i];
    sort(a+1,a+1+n);
    for(int i=1;i<=n;i++)
     cout<<a[i]<<" ";
}

 

 

                         

基本思想：每一趟在n-i+1(i=1，2，…n-1)個記錄中選取關鍵字最小的記錄作為有序序列中第i個記錄。基於此思想的演算法主要有簡單選擇排序、樹型選擇排序和堆排序。

選擇排序（不穩定）

#include<bits/stdc++.h> 
using namespace std;
int a[1000001];
int main()
{
    int n,k;
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>a[i];
    for(int i=0;i<n;i++)
    {
        k=i;//選最小的元素a[k]
        for(int j=i+1;j<n;j++)
            if(a[j]<a[k]) k=j;
        if(k!=i)//交換a[i]和a[k]，將現在的最小值放在a[i]的位置上 
            swap(a[i],a[k]);
    }
    for(int i=0;i<n;i++)
      cout<<a[i]<<" ";
}

VirMach 便宜 VPS

QNews

QNews