一張經(jīng)典算法圖鎮(zhèn)樓。

十大經(jīng)典排序算法

正文

常用術(shù)語說明

穩(wěn)定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面；
不穩(wěn)定：如果a原本在b的前面，而a=b，排序之后a可能會(huì)出現(xiàn)在b的后面；

內(nèi)排序：所有排序操作都在內(nèi)存中完成；
外排序：由于數(shù)據(jù)太大，因此把數(shù)據(jù)放在磁盤中，而排序通過磁盤和內(nèi)存的數(shù)據(jù)傳輸才能進(jìn)行；

時(shí)間復(fù)雜度: 一個(gè)算法執(zhí)行所耗費(fèi)的時(shí)間。
空間復(fù)雜度: 運(yùn)行完一個(gè)程序所需內(nèi)存的大小。

排序分類

算法介紹（全部以C語言的形式介紹）

int array[] = {6 ,1 ,2 ,7 ,9 ,3 ,4 ,5 ,10 ,8};
int num = sizeof(array)/sizeof(int);

1. 冒泡排序（Bubble Sort）
   人生中接觸的第一種排序方法。

• 算法描述
  通過交換使相鄰的兩個(gè)數(shù)變成小數(shù)在前大數(shù)在后，這樣每次遍歷后，最大的數(shù)就“沉”到最后面了。重復(fù)N次即可以使數(shù)組有序。

• 算法實(shí)現(xiàn)

  for (int i = 0; i < num - 1; i++) {
      for (int j = 0; j < num - 1 - i; j++) {
            if (array[j] > array[j + 1]) {
            int tmp = array[j];
            array[j] = array[j + 1];
            array[j + 1] = tmp;
          }
      }
  }

2. 快速排序（Quick Sort）

• 算法描述

  1.在待排序的元素任取一個(gè)元素作為基準(zhǔn)(通常選第一個(gè)元素，但最的選擇方法是從待排序元素中隨機(jī)選取一個(gè)作為基準(zhǔn))，稱為基準(zhǔn)元素；
  
  2.將待排序的元素進(jìn)行分區(qū)，比基準(zhǔn)元素大的元素放在它的右邊，比其小的放在它的左邊；
  
  3.對(duì)左右兩個(gè)分區(qū)重復(fù)以上步驟直到所有元素都是有序的。
  
  所以我是把快速排序聯(lián)想成東拆西補(bǔ)或西拆東補(bǔ)，一邊拆一邊補(bǔ)，直到所有元素達(dá)到有序狀態(tài)。
  

• 算法實(shí)現(xiàn)

  void sort(int *a,int left,int right) {
      if (left >= right) {
          return;
      }
    // 由于已經(jīng)將a[0]中的數(shù)保存到key中，可以理解成在數(shù)組a[0]上挖了個(gè)坑，可以將其它數(shù)據(jù)填充到這來。
    // 從j開始向前找一個(gè)比X小或等于X的數(shù)。當(dāng)j=8，符合條件，將a[8]挖出再填到上一個(gè)坑a[0]中。a[0]=a[8]; i++;  這樣一個(gè)坑a[0]就被搞定了，但又形成了一個(gè)新坑a[8]，這怎么辦了？簡(jiǎn)單，再找數(shù)字來填a[8]這個(gè)坑。這次從i開始向后找一個(gè)大于X的數(shù)，當(dāng)i=3，符合條件，將a[3]挖出再填到上一個(gè)坑中a[8]=a[3]; j--;
   
      int i = left;
      int j = right;
      int key = a[i]; //a[i]就是第一個(gè)坑
    
      while (i < j) {
          // 從右向左找小于x的數(shù)來填s[i]
          while (i < j && key <= a[j]) {
              j--;
          }
          a[i] = a[j];
          while (i < j && key >= a[i]) {
              i++;
          }
          a[j] = a[i];
      }
      a[i] = key;
      sort(a, left, i-1);
      sort(a, i+1, right);
  }

還有一種比較個(gè)性理解的版本:一次循環(huán)先交換大小的，最后才和基數(shù)的交換。

在博客坐在馬桶上看算法：快速排序看到的，評(píng)論區(qū)各種吵架，說這不是快排。感覺思路是一樣的。代碼如下

  void sort1(int *a,int left,int right) {
      if (left >= right) {
          return;
      }
      int i = left;
      int j = right;
      int key = a[i];
    
      while (i != j) {
          //順序很重要，要先從右邊開始找
          while (i < j && key <= a[j]) {
              j--;
          }
          //再找左邊的
          while (i < j && key >= a[i]) {
              i++;
          }
          //交換兩個(gè)數(shù)在數(shù)組中的位置
          if(i < j){
              int t=a[i];
              a[i]=a[j];
              a[j]=t;
          }
      }
      //最終將基準(zhǔn)數(shù)歸位
      a[left]=a[i];
      a[i]=key;
      sort1(a, left, i-1);
      sort1(a, i+1, right);
}

經(jīng)典排序算法二（選擇排序、堆排序）
經(jīng)典排序算法三（插入排序、希爾排序）