排序算法是最基本最常用的算法，不同的排序算法在不同的場(chǎng)景或應(yīng)用中會(huì)有不同的表現(xiàn)，我們需要對(duì)各種排序算法熟練才能將它們應(yīng)用到實(shí)際當(dāng)中，才能更好地發(fā)揮它們的優(yōu)勢(shì)。今天，來總結(jié)下各種排序算法。

下面這個(gè)表格總結(jié)了各種排序算法的復(fù)雜度與穩(wěn)定性：

各種排序算法復(fù)雜度比較.png

冒泡排序

冒泡排序可謂是最經(jīng)典的排序算法了，它是基于比較的排序算法，時(shí)間復(fù)雜度為O(n^2)，其優(yōu)點(diǎn)是實(shí)現(xiàn)簡(jiǎn)單，n較小時(shí)性能較好。

• 算法原理
  相鄰的數(shù)據(jù)進(jìn)行兩兩比較，小數(shù)放在前面，大數(shù)放在后面，這樣一趟下來，最小的數(shù)就被排在了***位，第二趟也是如此，如此類推，直到所有的數(shù)據(jù)排序完成

• c++代碼實(shí)現(xiàn)

void bubble_sort(int arr[], int len) 
{ 
      for (int i = 0; i < len - 1; i++) 
      { 
          for (int j = len - 1; j >= i; j--) 
          { 
              if (arr[j] < arr[j - 1]) 
              { 
                  int temp = arr[j]; 
                  arr[j] = arr[j - 1]; 
                  arr[j - 1] = temp; 
              } 
          } 
      } 
} 

選擇排序

• 算法原理
  先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再?gòu)氖Ｓ辔磁判蛟刂欣^續(xù)尋找最小（大）元素，然后放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。

• c++代碼實(shí)現(xiàn)

void select_sort(int arr[], int len) 
  { 
      for (int i = 0; i < len; i++) 
      { 
          int index = i; 
          for (int j = i + 1; j < len; j++) 
          { 
              if (arr[j] < arr[index]) 
                  index = j; 
          } 
          if (index != i) 
          { 
              int temp = arr[i]; 
              arr[i] = arr[index]; 
              arr[index] = temp;  
          } 
      } 
  } 

插入排序

• 算法原理
  將數(shù)據(jù)分為兩部分，有序部分與無序部分，一開始有序部分包含第1個(gè)元素，依次將無序的元素插入到有序部分，直到所有元素有序。插入排序又分為直接插入排序、二分插入排序、鏈表插入等，這里只討論直接插入排序。它是穩(wěn)定的排序算法，時(shí)間復(fù)雜度為O(n^2)

• c++代碼實(shí)現(xiàn)

void insert_sort(int arr[], int len) 
  { 
      for (int i = 1; i < len; i ++) 
      { 
          int j = i - 1; 
          int k = arr[i]; 
          while (j > -1 && k < arr[j] ) 
          { 
              arr[j + 1] = arr[j]; 
              j --; 
          } 
          arr[j + 1] = k; 
      } 
  } 

快速排序

• 算法原理
  快速排序是目前在實(shí)踐中非常高效的一種排序算法，它不是穩(wěn)定的排序算法，平均時(shí)間復(fù)雜度為O(nlogn)，最差情況下復(fù)雜度為O(n^2)。它的基本思想是：通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過程可以遞歸進(jìn)行，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列。

• c++代碼實(shí)現(xiàn)

void quick_sort(int arr[], int left, int right) 
{ 
  if (left < right) 
  { 
      int i = left, j = right, target = arr[left]; 
      while (i < j) 
      { 
          while (i < j && arr[j] > target) 
              j--; 
          if (i < j) 
              arr[i++] = arr[j]; 
 
          while (i < j && arr[i] < target) 
              i++; 
          if (i < j) 
              arr[j] = arr[i]; 
      } 
      arr[i] = target; 
      quick_sort(arr, left, i - 1); 
      quick_sort(arr, i + 1, right); 
  } 
} 

歸并排序

• 算法原理
  歸并排序具體工作原理如下（假設(shè)序列共有n個(gè)元素）：

  • 將序列每相鄰兩個(gè)數(shù)字進(jìn)行歸并操作（merge)，形成floor(n/2)個(gè)序列，排序后每個(gè)序列包含兩個(gè)元素
  • 將上述序列再次歸并，形成floor(n/4)個(gè)序列，每個(gè)序列包含四個(gè)元素

  • 重復(fù)步驟2，直到所有元素排序完畢

    歸并排序是穩(wěn)定的排序算法，其時(shí)間復(fù)雜度為O(nlogn)，如果是使用鏈表的實(shí)現(xiàn)的話，空間復(fù)雜度可以達(dá)到O(1)，但如果是使用數(shù)組來存儲(chǔ)數(shù)據(jù)的話，在歸并的過程中，需要臨時(shí)空間來存儲(chǔ)歸并好的數(shù)據(jù)，所以空間復(fù)雜度為O(n)

• c++代碼實(shí)現(xiàn)

void merge(int arr[], int temp_arr[], int start_index, int mid_index, int end_index) 
 { 
     int i = start_index, j = mid_index + 1; 
     int k = 0; 
     while (i < mid_index + 1 && j < end_index + 1) 
     { 
         if (arr[i] > arr[j]) 
             temp_arr[k++] = arr[j++]; 
         else 
             temp_arr[k++] = arr[i++]; 
     } 
     while (i < mid_index + 1) 
     { 
         temp_arr[k++] = arr[i++]; 
     } 
     while (j < end_index + 1) 
         temp_arr[k++] = arr[j++]; 
 
     for (i = 0, j = start_index; j < end_index + 1; i ++, j ++) 
         arr[j] = temp_arr[i]; 
 } 
 
 void merge_sort(int arr[], int temp_arr[], int start_index, int end_index) 
 { 
     if (start_index < end_index) 
     { 
         int mid_index = (start_index + end_index) / 2; 
         merge_sort(arr, temp_arr, start_index, mid_index); 
         merge_sort(arr, temp_arr, mid_index + 1, end_index); 
         merge(arr, temp_arr, start_index, mid_index, end_index); 
     } 
 } 

堆排序

二叉堆

二叉堆是完全二叉樹或者近似完全二叉樹，滿足兩個(gè)特性

• 父結(jié)點(diǎn)的鍵值總是大于或等于(小于或等于)任何一個(gè)子節(jié)點(diǎn)的鍵值
• 每個(gè)結(jié)點(diǎn)的左子樹和右子樹都是一個(gè)二叉堆

當(dāng)父結(jié)點(diǎn)的鍵值總是大于或等于任何一個(gè)子節(jié)點(diǎn)的鍵值時(shí)為***堆。當(dāng)父結(jié)點(diǎn)的鍵值總是小于或等于任何一個(gè)子節(jié)點(diǎn)的鍵值時(shí)為最小堆。一般二叉樹簡(jiǎn)稱為堆。

堆的存儲(chǔ)

一般都是數(shù)組來存儲(chǔ)堆，i結(jié)點(diǎn)的父結(jié)點(diǎn)下標(biāo)就為(i – 1) / 2。它的左右子結(jié)點(diǎn)下標(biāo)分別為2 * i + 1和2 * i + 2。如第0個(gè)結(jié)點(diǎn)左右子結(jié)點(diǎn)下標(biāo)分別為1和2。存儲(chǔ)結(jié)構(gòu)如圖所示：

堆結(jié)構(gòu).png

 堆排序原理

堆排序的時(shí)間復(fù)雜度為O(nlogn)

• 算法原理（以***堆為例）

  • 先將初始數(shù)據(jù)R[1..n]建成一個(gè)***堆，此堆為初始的無序區(qū)
  • 再將關(guān)鍵字***的記錄R[1]（即堆頂）和無序區(qū)的***一個(gè)記錄R[n]交換，由此得到新的無序區(qū)R[1..n-1]和有序區(qū)R[n]，且滿足R[1..n-1].keys≤R[n].key
  • 由于交換后新的根R[1]可能違反堆性質(zhì)，故應(yīng)將當(dāng)前無序區(qū)R[1..n-1]調(diào)整為堆。
  • 重復(fù)2、3步驟，直到無序區(qū)只有一個(gè)元素為止。

• c++代碼實(shí)現(xiàn)

/** 
 * 將數(shù)組arr構(gòu)建大根堆 
 * @param arr 待調(diào)整的數(shù)組 
 * @param i   待調(diào)整的數(shù)組元素的下標(biāo) 
 * @param len 數(shù)組的長(zhǎng)度 
 */ 
void heap_adjust(int arr[], int i, int len) 
{ 
    int child; 
    int temp; 
 
    for (; 2 * i + 1 < len; i = child) 
    { 
        child = 2 * i + 1;  // 子結(jié)點(diǎn)的位置 = 2 * 父結(jié)點(diǎn)的位置 + 1 
        // 得到子結(jié)點(diǎn)中鍵值較大的結(jié)點(diǎn) 
        if (child < len - 1 && arr[child + 1] > arr[child]) 
            child ++; 
        // 如果較大的子結(jié)點(diǎn)大于父結(jié)點(diǎn)那么把較大的子結(jié)點(diǎn)往上移動(dòng)，替換它的父結(jié)點(diǎn) 
        if (arr[i] < arr[child]) 
        { 
            temp = arr[i]; 
            arr[i] = arr[child]; 
            arr[child] = temp; 
        } 
        else 
            break; 
    } 
} 
 
/** 
 * 堆排序算法 
 */ 
void heap_sort(int arr[], int len) 
{ 
    int i; 
    // 調(diào)整序列的前半部分元素，調(diào)整完之后***個(gè)元素是序列的***的元素 
    for (int i = len / 2 - 1; i >= 0; i--) 
    { 
        heap_adjust(arr, i, len); 
    } 
 
    for (i = len - 1; i > 0; i--) 
    { 
        // 將第1個(gè)元素與當(dāng)前***一個(gè)元素交換，保證當(dāng)前的***一個(gè)位置的元素都是現(xiàn)在的這個(gè)序列中***的 
        int temp = arr[0]; 
        arr[0] = arr[i]; 
        arr[i] = temp; 
        // 不斷縮小調(diào)整heap的范圍，每一次調(diào)整完畢保證***個(gè)元素是當(dāng)前序列的***值 
        heap_adjust(arr, 0, i); 
    } 
}