天天看點
傳回

【算法】各種排序算法的總結與優缺點

排序是最基本的算法，裡面包含了最基礎的思想。一個簡單的優化可以讓排序快很多。

O ( n 2 ) O(n^2) O(n2)的排序算法

冒泡排序 

//冒泡排序
template <typename T>
void bubbleSort(T *arr, int size)
{
    for (int i = 0; i < size; ++i)
    {
        for (int j = 0; j < size - i - 1; ++j)
        {
            if (arr[j] > arr[j + 1])
                swap(arr[j], arr[j + 1]);
        }
    }
}

插入排序

​

template<typename T>
void insertSort(T *arr,int size)
{
    for(int i = 0;i < size;++i)
    {
        int j;  
        for(j = i;j > 0 && arr[j] < arr[j-1];--j){swap(arr[j],arr[j-1]);}
    }
}

選擇排序 

//選擇排序 複雜度O(n^2)
template<typename T>
void selectionSort(T *arr,int size)
{
    int k;
    for(int i = 0;i < size-1; ++i)
    {
        k = i;
        for(int j = i+1;j < size;++j)
        if(arr[j] < arr[k])
            k = j;    
        if(k != i) mySwap(arr[k],arr[i]);
    }
}

測試排序使用時間的時候，總是選擇排序快于插入排序，按理說，插入排序應該比選擇排序要快啊，因為插入排序可以提前終止循環，這是為什麼呢？

[外鍊圖檔轉存失敗,源站可能有防盜鍊機制,建議将圖檔儲存下來直接上傳(img-JMwWFKuE-1587546526297)(https://i.loli.net/2020/03/10/Ymcw1fX3ge8pPhq.png)]

原因是選擇排序比較的是下标，而插入排序每一次比較都要交換，而交換所耗費的時間是高于簡單的比較的。

插入排序優化-将交換變成指派

template<typename T>
void insertSort(T *arr,int size)
{
    for(int i = 0;i < size;++i)
    {
        T e = arr[i];
        int j;  
        for(j = i;j > 0 && arr[j-1] > e;--j){arr[j] = arr[j-1];}
        arr[j] = e;
    }
}

運作時間明顯變快了

[外鍊圖檔轉存失敗,源站可能有防盜鍊機制,建議将圖檔儲存下來直接上傳(img-SPbt3sFy-1587546526302)(https://i.loli.net/2020/03/10/VhB69LnXso8tHIJ.png)]

對于近乎有序的資料來說，插入排序的速度要快很多，近乎 O ( n ) O (n) O(n)。而插入排序的實際應用有很多，比如日志，日志的時間是近乎有序的，但是生成日志可能會出錯，需要進行時間排序處理，這個時候使用插入排序會更好；還有銀行的一些流水單等等

拓展：

C++運算符重載

一般在類中實作，有兩種可以實作的方法
運算符重載例子，使用在一個類中 
class Student
{
public:
 string name;
 int score;
 bool operator<(const Student &otherStudent)
 {
     return this->score < otherStudent.score;
 }
 friend ostream &operator<<(ostream &os, const Student &student)
 {
     os << "Student:" << student.name << " "<<student.score<<endl;
     return os;
 }
};
  1. 使用友元函數 
    傳回值類型 operator 運算符(形參表)
{
...
}
//例Complex是一個複數類
friend Complex operator+(const Complex &c1,const Complex &c2){
    return Complex(c1.i + c2.i,c1.j + c2.j);
}
  2. 使用類裡面的函數 
    傳回值類型 operator 運算符(形參表)
{
...
}
//例Complex是一個複數類
Complex operator+(const Complex &complex){
    return Complex(this->i + complex.i,this->j + complex.j);
}

它們的差別就是參數的個數不同以及需不需要加上

fridend

這個關鍵字

O ( n log ⁡ ( n ) ) O(n\log (n)) O(nlog(n))的排序算法

歸并排序

代碼實作

template <typename T>
void __merge(T *arr, int l, int middle, int r)
{
    T aux[r - l + 1];
    for (int i = l; i <= r; ++i)
        aux[i - l] = arr[i];
    int i = l, j = middle + 1;
    for (int k = l; k <= r; ++k)
    {
        if (i > middle)
        {
            arr[k] = aux[j - l];
            j++;
        }
        else if (j > r)
        {
            arr[k] = aux[i - l];
            i++;
        }
        else if (aux[i - l] < aux[j - l])
        {
            arr[k] = aux[i - l];
            i++;
        }
        else
        {
            arr[k] = aux[j - l];
            j++;
        }
    }
}

template <typename T>
void __mergeSort(T *arr, int l, int r)
{
    if (l >= r)
        return;
    int middle = (l + r) / 2;
    __mergeSort(arr, l, middle);
    __mergeSort(arr, middle+1, r);
    if(arr[middle] > arr[middle+1])
        __merge(arr, l, middle, r);
}

//歸并排序
template <typename T>
void mergeSort(T *arr, int size)
{
    __mergeSort(arr, 0, size - 1);
}

下面這段代碼的标記部分需要考慮溢出的問題

[外鍊圖檔轉存失敗,源站可能有防盜鍊機制,建議将圖檔儲存下來直接上傳(img-1D7OF2Vo-1587546526307)(https://i.loli.net/2020/03/11/9GStd4s1fe7kINL.png)]

歸并排序快是快，但是要耗費多一倍 O ( n ) O(n) O(n)的存儲空間，也就是使用空間換時間。

希爾排序

動畫示範(來自@五分鐘算法)：

【算法】各種排序算法的總結與優缺點

代碼實作:

//希爾排序
template <typename T>
void shellSort(T *arr, int size)
{
    int dk[] = {5, 3, 1};
    for (int index = 0; index < 3; ++index)
    {
        for (int i = 0; i < size / dk[index]; ++i)
        {
            int j;
            int e = arr[i];
            for (j = i + dk[index]; j > dk[index] && arr[j] > e; j -= dk[index])
            {
                arr[j] = arr[j - dk[index]];
            }
            arr[j] = e;
        }
    }
}
希爾排序相當于是插入排序的更新版，增加了一個步長參數，使用希爾排序可以讓零散的資料實作跳躍行的交換，最後逐漸将數組轉化為有序，這樣最後使用步長為1的插入排序就非常快了。

快速排序

被稱為二十世紀影響最大的算法之一！

動畫示範(來自@五分鐘算法)：

【算法】各種排序算法的總結與優缺點

代碼實作：

template<typename T>
int __partition(T *arr,int l,int r){
    T v = arr[l];
    int j = l;
    for(int i = l+1;i <= r;++i){
        if(arr[i] < v){
            swap(arr[i],arr[++j]);
        }
    }
    swap(arr[l],arr[j]);
    return j;
}

template<typename T>
void __quickSort(T *arr,int l,int r)
{
     if(l >= r) return;
     int p = __partition(arr,l,r);
     __quickSort(arr,l,p-1);
     __quickSort(arr,p+1,r);
}

//快速排序
template<typename T>
void quickSort(T *arr,int size)
{
    __quickSort(arr,0,size-1);

}

優化一：

在數組的元素個數小于15個的時候使用插入排序進行優化:

template<typename T>
void __quickSort(T *arr,int l,int r)
{
+    if(r - l <= 15) insertionSort(arr,l,r);
     int p = __partition(arr,l,r);
     __quickSort(arr,l,p-1);
     __quickSort(arr,p+1,r);
}

優化二：

使用随機值作為劃分标準

template<typename T>
int __partition(T *arr,int l,int r){
+   swap(arr[l],arr[rand() % (r-l+1) + l]);
    T v = arr[l];
    int j = l;
    for(int i = l+1;i <= r;++i){
        if(arr[i] < v){
            swap(arr[i],arr[++j]);
        }
    }
    swap(arr[l],arr[j]);
    return j;
}

template<typename T>
void quickSort(T *arr,int size)
{
+   srand(time(NULL));
    __quickSort(arr,0,size-1);
}

缺點:

  1. 在近乎有序的數組排序中，快速排序的性能很差。時間複雜度也近乎 O ( n 2 ) O(n^2 ) O(n2)
  2. 對于有很多重複元素的數組，快速排序的性能也很差
快速排序版本二：兩路快排

使用兩個下标分别處理大于v與小于v的部分。(v為基準元素)

代碼實作：

template<typename T>
int __partition2(T *arr,int l,int r){
    swap(arr[l],arr[rand() % (r-l+1) + l]);
    T v = arr[l];
    int i = l  + 1,j = r;
    while(true)
    {
        while(arr[i] < v && i <= r) ++i;
        while(arr[j] > v && j >= l+1) --j;
        if(i > j) break;
        swap(arr[i++],arr[j--]);
    }
    swap(arr[l],arr[j]);
    return j;
}

template<typename T>
void __quickSort2(T *arr,int l,int r)
{
     if(r - l<= 15){
         insertSort(arr,l,r);
         return;
     }
        
     int p = __partition2(arr,l,r);
     __quickSort2(arr,l,p-1);
     __quickSort2(arr,p+1,r);
}

//快速排序版本二，雙路快排
template<typename T>
void quickSort2(T *arr,int size)
{
    srand(time(NULL));
    __quickSort2(arr,0,size-1);
}
快速排序版本三：三路快排

使用三個下标分别處理大于v、等于v與小于v的部分。(v為基準元素)

代碼實作：

template<typename T>
void __quickSort3(T *arr,int l,int r)
{
     if(r - l<= 15){
         insertSort(arr,l,r);
         return;
     }
    
    swap(arr[l],arr[rand() % (r-l+1) + l]);
    T v = arr[l];
    int lt = l; //arr[l+1...lt] < v
    int gt = r + 1;  //arr[gt...r] > v
    int i = l+1;    //arr[lt+1...i] == v

    while(i < gt){
        if(arr[i] < v){
            swap(arr[i++],arr[++lt]);
        }else if(arr[i] > v){
            swap(arr[i],arr[--gt]);
        }else{
            i++;
        }
    }
    swap(arr[l],arr[lt]);
    __quickSort3(arr,l,lt-1);
    __quickSort3(arr,gt,r);
}

//快速排序版本三，三路快排
template<typename T>
void quickSort3(T *arr,int size)
{
    srand(time(NULL));
    __quickSort3(arr,0,size-1);
}

堆排序

基數排序

桶排序

排序算法總結

圖檔：

【算法】各種排序算法的總結與優缺點

未完待續…🛴

參考：

  1. https://www.cnblogs.com/onepixel/p/7674659.html
  2. https://github.com/MisterBooo/Article
算法與資料結構 排序算法 c++ 算法
上一篇: 各種排序算法的優缺點
下一篇: 幾大排序算法幾大排序算法

繼續閱讀