天天看點
傳回

工作多年之後回顧經典排序算法

原文連結

排序都要做的事情是比較和交換

穩定排序：排序前後，兩個相等的元素在其序列中的前後位置順序相同

這裡隻有插入排序和歸并排序是穩定排序

以下示例均假設我們要從小到大進行排序

選擇排序

非穩定排序

排序效率和輸入無關

選擇排序的基本步驟：先找出最小元素放到0号位置，再找出次小元素放到1号位置，再找出次次小元素放到2号位置，以此類推

工作多年之後回顧經典排序算法
工作多年之後回顧經典排序算法

代碼實作 

#ifndef __SELECTIONSORT_H__
#define __SELECTIONSORT_H__

class Selection
{
public:
	//選擇排序
  void Sort(char *a, int length)
  {
    for (int index = 0; index < length - 1; ++index)
    {
      //找出從目前位置index開始到後面所有元素中最小元素的下标
      int indexOfCurMin = index;
      for (int i = index + 1; i < length; ++i)
      {
        if (a[i] < a[indexOfCurMin])
        indexOfCurMin = i;
      }

      //将找到的最小元素和index位置上的元素進行交換
      int temp = a[index];
      a[index] = a[indexOfCurMin];
      a[indexOfCurMin] = temp;
    }
  }
};

#endif

特性

該算法的優點是對輸入資料的移動次數最少。缺點是運作效率低，無法處理大規模的資料

性能分析

使用該算法對n個元素進行排序時

時間複雜度為O(n^2)，需要對元素進行n(n-1)/2次比較以及n-1次交換。值得注意的是，元素交換次數與元素個數成線性關系，這是其它排序算法都沒有的

空間複雜度為0

插入排序

穩定排序

排序效率和輸入有關，當待排序的元素越有序（倒置很少）時，該算法可能比其它任何算法都要快

插入排序的基本步驟：每一次都将一個未排序的元素插入到已經排好序的數組中

工作多年之後回顧經典排序算法
工作多年之後回顧經典排序算法

代碼實作 

#ifndef __INSERTIONSOER_H__
#define __INSERTIONSOER_H__

//插入排序
class Insertion
{
public:
  void Sort1_0(char *a, int length)
  {
    for (int index = 1; index < length; ++index)
    {
      for (int i = index; i > 0; --i)
      {
        if (a[i] < a[i - 1])
        {
          char temp = a[i];
          a[i] = a[i - 1];
          a[i - 1] = temp;
        }
        //else
        //  break;
      }
    }
  }
  
  //優化版本
  void Sort2_0(char *a, int length)
  {
    for (int index = 1; index < length; ++index)
    {
      char needToInsert = a[index];
    
      int i;
      for (i = index - 1; i >= 0 && needToInsert < a[i]; --i)
        a[i + 1] = a[i];  //右移
    
      a[i + 1] = needToInsert;
    }
  }
};

#endif

特性

這裡需要補充兩個概念

倒置：兩個待排序元素的排列順序與目标順序相反

部分有序：如果元素倒置的數量小于元素個數的某個倍數時，那麼就說這些待排序元素是部分有序的

該算法缺點是運作效率低，無法處理大規模的資料

插入排序和冒泡排序很像，冒泡排序的算法如下：從未排序元素的第一對直到最後一對，如果第一個元素比第二個元素大就交換，重複這個步驟直到所有元素都排序完成

性能分析

使用該算法對n個元素進行排序時

時間複雜度在最壞的情況下為O(n^2)，最好的情況為O(n)，是以平均為O(n^2)。元素間的比較次數大于等于倒置數，小于等于倒置數+數組大小-1，在最壞的情況下為n(n-1)/2次，最好的情況下為n-1次。元素間進行交換的次數等于倒置數，在最壞的情況下為n(n-1)/2次，最好的情況下為0次

空間複雜度為0

希爾排序

非穩定排序

排序效率是否輸入有關取決于第二步使用的排序算法是否輸入有關

希爾排序的基本步驟：

  1. 确定h的初值
  2. 每次循環都使數組中任意間隔為h的元素都是有序的（這樣的數組稱為h有序數組）
  3. 每次循環結束，h都要遞減一次，直到h等于1

ps：h的遞減方式是多種多樣的，不同的遞減方式決定了希爾排序算法的效率，目前還沒有研究出最好的遞減序列

工作多年之後回顧經典排序算法
工作多年之後回顧經典排序算法

代碼實作 

//基于插入排序的希爾排序算法
#ifndef __SHELLSORT_H__
#define __SHELLSORT_H__

//希爾排序
class Shell
{
public:
  //1.0版本
  void Sort1_0(char *a, int length)
  {
    //确定h的最大值
    int h = 1;
    while (h < length / 3)
      h = 3 * h + 1;    //1,4,13,40,121,364,1093，...
  
    while (h >= 1)  //間隔控制
    {
      for (int i = 0; i < h; ++i)  //每個子數組的頭
      {
        //對每個子數組進行插入排序
        for (int j = i + h; j < length; j += h)
        {
          char needToInsert = a[j];
          int k;
          for (k = j - h; j >= i&&needToInsert < a[k]; k -= h)
            a[k + h] = a[k];
      
          a[k + h] = needToInsert;
        }
      }
    
      h /= 3;
    }
  }
  
  //2.0版本
  void Sort2_0(char *a, int length)
  {
    //确定h的最大值
    int h = 1;
    while (h < length / 3)
      h = 3 * h + 1;    //1,4,13,40,121,364,1093，...
  
    while (h >= 1)
    {
      for (int i = h; i < length; ++i)    //從所有子數組的第二進制素開始到最後的元素，妙
      {
        //在i元素所屬的子數組内對i元素進行插入排序
        char needToInsert = a[i];
        int j;
        for (j = i - h; j >= 0 && needToInsert < a[j]; j -= h)
          a[j + h] = a[j];
    
        a[j + h] = needToInsert;
      }
    
      h /= 3;
    }
  }
};

#endif

特性

該算法的優點是可以處理大規模的資料，适用于大部分場合，其它更複雜優秀的排序算法最多比該算法快2倍。缺點是無法處理超大規模的資料

性能分析

使用該算法對n個元素進行排序時

時間複雜度目前在數學上是未知的

空間複雜度為0

歸并排序

穩定排序

排序效率與輸入無關

工作多年之後回顧經典排序算法
工作多年之後回顧經典排序算法
工作多年之後回顧經典排序算法
工作多年之後回顧經典排序算法
工作多年之後回顧經典排序算法
工作多年之後回顧經典排序算法

代碼實作 

#ifndef __MERGESORT_H__
#define __MERGESORT_H__

#include <iostream>  /* NULL */
#include <algorithm>  /* min */

using namespace std;

class Merge
{
private:
  //原數組的副本,輔助空間
  char *aux;
public:
  Merge(){ aux = NULL; }
  
  //單次歸并，将a數組的兩部分已排好的子數組合并起來
  //mid代表左邊子數組的最後一個元素下标
  void merge(char *a, int left, int mid, int right)
  {
    for (int i = left; i <= right; ++i)
      aux[i] = a[i];
  
    int idxOfLeft = left;
    int idxOfRight = mid + 1;
    //開始歸并
    for (int i = left; i <= right; ++i)
    {
      if (idxOfLeft > mid&&idxOfRight <= right)
        a[i] = aux[idxOfRight++];
      else if (idxOfLeft <= mid&&idxOfRight > right)
        a[i] = aux[idxOfLeft++];
      else if (aux[idxOfLeft] < aux[idxOfRight])
        a[i] = aux[idxOfLeft++];
      else
        a[i] = aux[idxOfRight++];
    }
  }
  
  //自頂向下的遞歸歸并排序
  //這個函數還可以優化，如果left和right之間的插值小到一定的程度，就不用再遞歸了；直接用插入排序、希爾排序或者選擇排序，速度可以提升；其中插入排序可以縮短10%~15%
  void SortCore(char *a, int left, int right)
  {
    if (left >= right)        //可以改成==
      return;
    else
    {
      int mid = (left + right) / 2;
      SortCore(a, left, mid);
      SortCore(a, mid + 1, right);
      merge(a, left, mid, right);    //這條語句在執行前還可以做一個判斷：如果a[mid]<=a[mid+1]，這條語句可以不執行；
    }
  }
  
  //啟動函數
  void Sort(char *a, int length)
  {
    //防止記憶體洩漏
    if (aux != NULL)
    {
      delete[] aux;
      aux = NULL;
    }
  
    aux = new char[length];
    SortCore(a, 0, length - 1);
  }
  
};

class MergeBu
{
private:
  //a數組的副本,輔助空間
  char *aux;

public:
  MergeBu(){ aux = NULL; }
  
  //單次歸并，将a數組的兩部分已排好的子數組合并起來
  //mid代表左邊子數組的最後一個元素下标
  void merge(char *a, int left, int mid, int right)
  {
    for (int i = left; i <= right; ++i)
      aux[i] = a[i];
  
    int idxOfLeft = left;
    int idxOfRight = mid + 1;
    //開始歸并
    for (int i = left; i <= right; ++i)
    {
      if (idxOfLeft > mid&&idxOfRight <= right)
        a[i] = aux[idxOfRight++];
      else if (idxOfLeft <= mid&&idxOfRight > right)
        a[i] = aux[idxOfLeft++];
      else if (aux[idxOfLeft] < aux[idxOfRight])
        a[i] = aux[idxOfLeft++];
      else
        a[i] = aux[idxOfRight++];
    }
  }
  
  //自底向上的歸并排序
  //可以給連結清單進行排序，而不用輔助數組
  void Sort(char *a, int length)
  {
    //保險
    if (aux)
    {
      delete[] aux;
      aux = NULL;
    }
  
    aux = new char[length];
  
    for (int subArraySize = 1; subArraySize < length; subArraySize <<= 1)
    {
      for (int left = 0; left + subArraySize < length; left += (subArraySize << 1))    //注意這裡的終止條件
        merge(a, left, left + subArraySize - 1, min(left + (subArraySize << 1) - 1, length - 1));
    }
  }
};

#endif

特性

該算法的優點是能夠處理超大規模的資料，缺點是需要O(n)大小的輔助空間

性能分析

使用該算法對n個元素進行排序時

時間複雜度為O(nlgn)，元素間的比較次數在最壞的情況下為nlgn次，在最好的情況下為(nlgn/2)次，平均為(nlgn)(3/4)次。

空間複雜度為O(n)+遞歸輔助棧大小

快速排序

非穩定排序

在介紹算法之前需要先了解一個操作--切分

切分的目标是通過調整數組将首元素(或尾元素)放到正确的位置。該位置左邊的元素都小于該位置的元素，右邊的元素都大于該位置的元素。切分的一個經典應用是查找數組中第k大的元素。需要注意的是，切分要在一個數組上進行各種交換操作，如果不想改變原數組的話，則需要多建立一個數組來進行輔助

快速排序函數的基本步驟：對數組進行切分，再對經過切分得到的兩個子數組分别調用快速排序函數

工作多年之後回顧經典排序算法
工作多年之後回顧經典排序算法
工作多年之後回顧經典排序算法
工作多年之後回顧經典排序算法

代碼實作 

#ifndef __QUICKSORT_H__
#define __QUICKSORT_H__

class Quick
{
public:
  void Sort(char *a, int length)
  {
    //在開始遞歸排序前最好先打亂一下數組，防止不合理的切分；這樣就不容易出現O(N^2)這種情況
    SortCore(a, 0, length - 1);
  }
  
  //可以優化：在數組被分割得小于某個數值的時候，改用插入排序
  void SortCore(char *a, int left, int right)
  {
    if (left >= right)
    {
      return;
    }
    else
    {
      int j = Partition(a, left, right);
      SortCore(a, left, j - 1);
      SortCore(a, j + 1, right);
    }
  }
  
  //可以優化：選取部分元素來找出這部分元素的中位數當作基準
  //可以優化（代碼看quick3way）  
  int Partition(char *a, int left, int right)
  {
    //分割标準，取了首元素來當标準
    char standard = a[left];

    int i = left+1;
    int j = right;
    while(true)
    {
      //特别注意 ++i 和 --j 的位置
      //注意a[i] <= standard和standard <= a[j]的等于号
      while (i <= right && a[i] <= standard){ ++i; }      //i <= right可以改成i < right
      while (j >= left + 1 && standard <= a[j]){ --j; }    //j >= left+1不可以更改j > left+1
     
      if (i < j)
      {
        char temp = a[i];
        a[i] = a[j];
        a[j] = temp;
      }
      else
        break;
     
    }

    a[left] = a[j];
    a[j] = standard;
  
    return j;
  }
};

//三向切分的快速排序：在一個數組中，不會多次選擇主鍵值同樣的元素作為基準；可以改成三向切分，就是比基準值小的元素放在左邊，與基準值相等的元素放在中間，比基準值大的元素放在右邊；對于包含大量重複元素的數組，可以将時間複雜度有NlgN降到N
class Quick3way
{
public:
  void Sort(char *a, int length)
  {
    //在開始遞歸排序前最好先打亂一下數組，防止不合理的切分；這樣就不容易出現O(N^2)這種情況
    SortCore(a, 0, length - 1);
  }
  
  void SortCore(char *a, int left, int right)
  {
    if (left >= right)
    {
      return;
    }
    else
    {
      //三向切分
#if 0
      //第一次切分
      char standard = a[left];
      int i = left+1;
      int j = right;
      while(true)
      {
        while (a[i] < standard && i <= right){ ++i; }
        while (standard <= a[j] && j >= left+1){ --j; }
    
        if (i < j)
        {
          char temp = a[i];
          a[i] = a[j];
          a[j] = temp;
        }
        else
          break;
      }
      a[left] = a[j];
      a[j] = standard;
    
      int lessRight = j - 1;
    
      //第二次切分
      j = right;
      while(true)
      {
        while (a[i] == standard && i <= right){ ++i; }
        while (standard < a[j] && j >= lessRight + 2){ --j; }
    
        if (i < j)
        {
          char temp = a[i];
          a[i] = a[j];
          a[j] = temp;
        }
        else
          break;
      }
    
      int equelRight = j;
    
      SortCore(a, left, lessRight);
      SortCore(a, equelRight + 1, right);
#endif
#if 1  
      //如果無法了解這段代碼，請使用樣例：6、2、3、7、6、6、9、1，來模拟一下
      char standard = a[left];
      //[left,lt-1]中的元素都小于基準值
      //[lt,i-1]中的元素都等于基準值
      //[gt+1,right]中的元素都大于基準值
      int lt = left;
      int i = left + 1;
      int gt = right;
      while (i <= gt)
      {
        if (a[i] < standard)
        {
          char temp = a[i];
          a[i] = a[lt];
          a[lt] = temp;
      
          ++i;
          ++lt;
        }
        else if (a[i] == standard)
        {
          ++i;
        }
        else if (a[i] > standard)
        {
          char temp = a[i];
          a[i] = a[gt];
          a[gt] = temp;
      
          --gt;
        }
      }
      
      SortCore(a, left, lt - 1);
      SortCore(a, i, right); 
#endif
    }
  }
};

#endif

特性

該算法的優點是可優化的空間大，經過精心調優的快速排序在大多數情況下都會比其他基于比較的排序算法更快，缺點是如果每次切分選擇的元素都不正确，算法運作效率就會大幅度降低。例如第一次選了最小元素，第二次選擇了次小元素作基準...，這種情況下時間複雜度就會變成O(n^2)，但是這種情況出現的機率比你電腦被雷劈中的機率還要小

性能分析

使用該算法對n個元素進行排序時

時間複雜度為O(nlgn)，雖然和歸并排序一樣，但是比歸并要快

空間複雜度為遞歸輔助棧的大小

優先隊列

在講解堆排序之前需要先介紹一個資料結構--優先隊列。該資料結構每一次取元素都隻能擷取最大（或最小）的元素

實作優先隊列的方式有很多種

可以通過數組來實作無序或有序的優先隊列

工作多年之後回顧經典排序算法

還可以通過二叉堆來實作。二叉堆是一棵父節點總是大于（或小于）等于兩個子節點的二叉樹，這樣一棵二叉樹又可以說是堆有序的。二叉堆可以使用數組形式的完全二叉樹來存儲

樹包括堆，堆包括二叉堆。因為一般使用的堆都是二叉堆，是以通常将二叉堆稱為堆

為堆添加或移除元素都會先破壞堆的有序狀态，然後再周遊堆來恢複有序狀态（這個過程稱為堆的有序化）

基于二叉堆實作的優先隊列

以下二叉堆都是最大堆

工作多年之後回顧經典排序算法
工作多年之後回顧經典排序算法
工作多年之後回顧經典排序算法

代碼實作 

//優先隊列的一種實作方式：二叉堆
//二叉堆：用這個資料結構可以很容易進行排序，但是直接用這個資料結構來排序效率并不高，因為我們隻用很小一部分代碼就夠了
class MaxPQ
{
private:
  char *pq;    //節點為k，父節點為(k-1)/2，左孩子為2*k+1，右孩子為2*k+2
  int count;   //記錄堆中元素的個數
public:
  MaxPQ(int maxN)
  {
    pq = new char[maxN];
    count = 0;
  }
  ~MaxPQ()
  {
    delete[] pq;
  }
  bool isEmpty()
  {
    return count == 0;
  }
  int size()
  {
    return count;
  }
  void insert(char v)
  {
    pq[count] = v;
    swim(count);

    ++count;
  }
  char delMax()
  {
    char max = pq[0];

    char temp = pq[0];
    pq[0] = pq[count - 1];
    pq[count - 1] = temp;

    --count;

    sink(0);

    return max;
  }
  //核心
  void swim(int k)
  {
    while (k > 0 && pq[k] > pq[(k - 1) / 2])
    {
      char temp = pq[k];
      pq[k] = pq[(k - 1) / 2];
      pq[(k - 1) / 2] = temp;

      k = (k - 1) / 2;
    }
  }
  //核心
  void sink(int k)
  {
    while (2 * k + 1 < count)
    {
      int maxChild = 2 * k + 1;
      if (maxChild + 1 < count && pq[maxChild + 1] > pq[maxChild])
        ++maxChild;

      if (pq[k] >= pq[maxChild])
        break;
      else
      {
        char temp = pq[k];
        pq[k] = pq[maxChild];
        pq[maxChild] = temp;

        k = maxChild;
      }

    }
  }
};

性能分析

資料結構 插入第一個元素 删除最大元素
基于有序數組的優先隊列 N 1
基于無序數組的優先隊列 1 N
基于二叉堆的優先隊列 lgN lgN
某種理想的優先隊列 1 1

從N個元素中找到最大的M個元素所需的成本：

某種理想的優先隊列 時間複雜度 空間複雜度（用于存儲N個輸入）
其他最快的排序算法 NlgN N
數組實作的優先隊列 NM M
二叉堆實作的優先隊列 NlgM M

堆排序

非穩定排序

堆排序的基本步驟：

  1. 将一個數組建成堆，建堆的方法有兩種：
    1. 層序周遊二叉樹（從左到右周遊數組），每個節點都進行上浮操作
    2. 從非葉子節點開始反向層序周遊二叉樹（從右到左周遊數組），每個節點都進行下沉操作。這種方式的效率更高，隻需要少于2N次比較以及少于N次交換
  2. 不斷删除堆頂元素
工作多年之後回顧經典排序算法
工作多年之後回顧經典排序算法

代碼實作 

#ifndef __HEAPSORT_H__
#define __HEAPSORT_H__

class Heap
{
public:
  //注意：count是待排序數組的長度
  void sink(char *a, int k, int count)
  {
    while (2 * k + 1 < count)
    {
      int maxChild = 2 * k + 1;
      if (maxChild + 1 < count && a[maxChild + 1] > a[maxChild])
        ++maxChild;

      if (a[k] >= a[maxChild])
        break;
      else
      {
        char temp = a[k];
        a[k] = a[maxChild];
        a[maxChild] = temp;

        k = maxChild;
      }
    }
  }
  //可以優化：先下沉後上浮，可将比較次數減少一半；這個方法需要額外的空間來輔助，隻有當比較需要很高的代價時才采用
  void sort(char *a,int count)
  {
    for (int i = (count - 1) / 2; i >= 0; --i)
      sink(a, i, count);

    for (int i = count - 1; i > 0; --i)
    {
      char temp = a[i];
      a[i] = a[0];
      a[0] = temp;

      sink(a, 0, i);
    }
  }
};

#endif
遊戲開發
上一篇: 許多人購買相機時，會注重其是否具備WiFi傳輸功能。但當他們拿到相機時，卻不知道如何使用該功能。是以，本文将介紹如何使用
下一篇: amazon mws基礎開發

繼續閱讀