排序算法比較

冒泡排序	選擇排序	插入排序	希爾排序	歸并排序	堆排序	快速排序
時間(平均)	O(n2)	O(n2)	O(n2)	O(n1.3)	O(nlogn)	O(nlogn)
時間(最好)	O(n)	O(n2)	O(n)	O(n)	O(nlogn)	O(nlogn)
時間(最差)	O(n2)	O(n2)	O(n2)	O(n2)	O(nlogn)	O(nlogn)
空間	O(1)	O(1)	O(1)	O(1)	O(n)	O(1)
穩定性	穩定	不穩定	穩定	不穩定	穩定	不穩定

穩定：如果a原本在b前面，而a=b，排序之後a仍然在b的前面。

不穩定：如果a原本在b的前面，而a=b，排序之後a可能會出現在b的後面。

時間複雜度：對排序資料的總的操作次數。反映當n變化時，操作次數呈現的規律。

空間複雜度：指算法在計算機内執行時所需存儲空間的度量，是資料規模n的函數。

七種排序算法

冒泡排序

冒泡排序是一種簡單的排序算法。它重複地走訪過要排序的數列，一次比較兩個元素，如果它們的順序錯誤就把它們交換過來。走訪數列的工作是重複地進行直到沒有再需要交換，也就是說該數列已經排序完成。這個算法的名字由來是因為越小的元素會經由交換慢慢“浮”到數列的頂端。
- 算法描述
  - 比較相鄰元素，如果第一個比第二個大，就交換他們兩個；
  - 對每一對相鄰元素做同樣的工作，從開始第一對到結尾的最後一對，這樣最後的元素就是最大元素；
  - 針對所有元素重複以上步驟，除了最後一個；
  - 重複步驟1~3，直到排序完成。
- 代碼實作
```
void swap(int &a, int &b)
{
 int temp = a;
 a = b;
 b = temp;
}

vector<int> bubbleSort(vector<int> vec)
{
 int len = vec.size();
 for(int i = ; i < len-; ++i)
 {
     for(int j = ; j < len - i - ; ++j)
     {
         if(vec[j] > vec[j + ])
            swap(vec[j],vec[j + ]);
     }
 }
 return vec;
}
           
```
選擇排序

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然後，再從剩餘未排序元素中繼續尋找最小（大）元素，然後放在已排序序列的末尾。以此類推，直到所有元素均排序完畢。
- 算法描述
  
  n個記錄的直接選擇排序可經過n-1趟直接選擇排序得到有序結果，具體算法如下：
  - 初始狀态：無序區為R[1…n]，有序區為空；
  - 第一趟排序（i=1,2,3,…,n-1）開始時，目前有序區和無序區分别為R[1,…,i-1]和R(i…n)。該趟排序從目前無序區中選出關鍵字最小的記錄R[k]，将它與無序區的第1個記錄R交換，使R[1…i]和R[i+1…n）分别變為記錄個數增加1個的新的有序區和記錄個數減少1個的新的無序區；
  - n-1趟結束，數組有序化了。
- 代碼實作
```
vector<int> selectionSort(vector<int> vec)
{
 int len = vec.size();
 int minIndex;
 for(int i = ; i < len - ; ++i)
 {
     minIndex = i;
     for(int j = i + ; j < len; ++j)
     {
         if(vec[j] < vec[minIndex]) //尋找最小值
            minIndex = j;         //将最小值的索引儲存
     }
     swap(vec[i], vec[min]);        //交換最小值與目前無序集的第一個元素
 }
 return vec;
}
           
```
- 算法分析
  
  選擇排序無論怎麼樣的資料，時間複雜度都是O(n2)，是以使用選擇排序時，資料規模越小越好。

插入排序

通過建構有序序列，對于未排序資料，在已排序序列中從後向前掃描，找到相應位置并插入。

算法描述
- 從第一個元素開始，該元素可以認為已經被排序；
- 取出下一個元素，在已經排序的元素序列中從後向前掃描；
- 如果該元素（已排序）大于新元素，将該元素移到下一個位置；
- 重複步驟3，直到找到已排序的元素小于或者等于新元素的位置；
- 将新元素插入到該位置後
- 重複步驟2~5。

代碼實作

vector<int> insertionSort(vector<int> vec)
{
 int len = vec.size();
 int preIndex, cuurent;
 for(int i = ; i < len; ++i)
 {
     preIndex = i - ;  //前一個下标，用于比較
     current = vec[i];  //存目前未排序的元素，因為後續移動過程會占用vec[i]，是以現将其儲存起來
     while(preIndex >=  && vec[preIndex] > current) //隻有目前一個元素下标>=0，并且前一個元素大于目前元素時，才會進行移動
     {
         vec[preIndex + ] = vec[preIndex];
     }
     vec[preIndex + ] = current; //否則，直接放在前一個元素後第一個位置
 }
 return vec;
}

算法分析

在一個數組中進行，隻需要O(1)的空間複雜度。插入排序是一種穩定排序算法。

希爾排序

希爾排序是第一個突破O(n2)的排序算法，是簡單插入排序的改進版。它會優先比較距離較遠的元素。希爾排序又叫縮小增量排序。
- 算法描述
  
  先将整個待排序的記錄序列分割成為若幹子序列分别進行直接插入排序，具體算法如下：
  - 選擇一個增量序列t1，t2，…，tk，其中ti>tj，tk = 1；
  - 按增量序列個數k，對序列進行k趟排序；
  - 每趟排序，根據對應的增量ti，将待排序列分割成若幹長度為m的子序列，分别對個子表進行直接插入排序。僅增量因子為1時，整個序列作為一個表來處理，表長即為整個序列長度。
- 代碼實作
```
vector<int> shellSort(vector<int> vec)
{
 int len = vec.size();
 int temp;
 int gap = ;
 while(gap < len / )
 {
     gap = gap *  + ;
 }
 for(gap; gap > ; gap = floor(gap / ))
 {
     for(int i = gap; i < len; i++)
     {
         temp = vec[i];
         for(int j = i - gap; j >  && vec[j] >temp; j -= gap)
         {
             vec[j + gap] = vec[j];
         }
         vec[j + gap] = temp;
     }
 }
 return vec;
}
           
```

歸并排序

歸并排序是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法的一個典型的應用。将已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若将兩個有序表合并成一個有序表，稱為2-路歸并。

算法描述
- 把長度為n的輸入序列分成兩個長度為n/2的子序列；
- 對這兩個子序列分别采用歸并排序；
- 将兩個排序好的子序列合并成一個最終的排序序列。

代碼實作

void Merging(int *list1, int list1_size, int *list2, int list2_size)
{
 int i = , j = , k = , m = ;
 int temp[MAXSIZE]; //臨時數組，用于存放排好序的序列
 while(i < list1_size && j < list2_size)  //對兩組元素進行排序
 {
     if(list1[i] < list2[j])
     {
         temp[k] = list1[i];
         k++;
         i++;
     }
     else
     {
         temp[k] = list2[j];
         k++;
         j++;
     }
     while(i < list1_size) //當list2沒有元素時，将list1的元素依次放入尾部
     {
         temp[k] = list1[i];
         i++;
     }
     while(j < list2_size)
     {
         temp[k] = list2[j];
         j++;
     }
     for(m = ; m < (list1_size + list2_size); m++)  //将排好序的元素放在list1中
     {
         list1[m] = temp[m];
     }
 }
}

void MergeSort(int k[], int n)
{
 while(n > )
 {
     int *list1 = k; //前半部分的起始指針
     int list1_size = n / ;  //前半部分的長度
     int *list2 = k + n / ;  //後半部分的起始指針
     int list2_size = n - list1_size;  //後半部分的長度

     //開始遞歸
     MergeSort(list1, list1_size);
     MergeSort(list2, list2_size);

     Merging(list1, list1_size, list2, list2_size);
 }
}

算法分析

歸并排序是一種穩定的排序方法。和選擇排序一樣，歸并排序的性能不受輸入資料的影響，但是表現比選擇排序好，代價是需要額外的空間。

快速排序

通過一趟排序将待排記錄分隔成獨立的兩部分，其中一部分記錄的關鍵字均比另一部分小，則可分别對這兩部分記錄繼續進行排序，以達到整個序列有序。

算法描述

快速排序使用分治法來把一個串分為兩個子串。具體算法如下：
- 從數列中挑出一個元素，成為“基準”；
- 重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準後面。在這個分區退出之後，該基準就處于數列的中間位置。這個稱為分區操作；
- 遞歸地把小于基準元素的子數列和大于基準元素的子數列排序。

代碼實作

int Partition(vector<int> &vec, int low, int high); //分區操作
void QSort(vector<int> &vec, int low, int high); 

void QuickSort(vector<int> &vec)
{
 QSort(vec, , vec.size());
}

void QSort(vector<int> &vec, int low, int high)
{
 int pivot;
 if(low < high)
 {
     pivot = Patition(vec, low, high);
     QSort(vec, low, pivot - );
     QSort(vec, pivot + , high);
 }
}

int Partition(vector<int> &vec, int low, int high)
{
 int key;
 key = vec[low];  //選擇第一個元素為基準
 while(low < high)
 {
     while(low < high && vec[high] >= key)
         high--;
     swap(vec, low, high);
     while(low < high && vec[low] <= key)
         low++;
     swap(vec, low, high);
 }
 renturn low;
}

堆排序

利用堆這種資料結構所設計的一種排序算法。堆既是一種近似完全二叉樹結構，同時滿足一定的性質，即子結點的鍵值或索引總是小于或大于它的父節點。
- 算法描述
  - 将初始待排序關鍵字序列（R1,R2,…,Rn）建構成大頂堆，此堆為初始的無序區；
  - 将堆頂元素R[1]與最後一個元素R[n]交換，此時得到新的無序區（R1,R2,…,Rn-1）和新的有序區（Rn），且滿足R[1,2…n-1] <= R[n]；
  - 由于交換後新的堆頂R[1]可能違反堆的性質，是以需要對目前無序區（R1,R2,…Rn-1）調整為新堆，然後再次将R[1]與無序區最後一個元素交換，得到新的無序區。不斷重複此過程，直到有序區的元素個數為n-1，則整個排序過程完成。
- 代碼實作
```
void HeapAdjust(vector<int> &vec, int s, int n)
{
 int i;
 int temp = vec[s];  //根
 for(i =  * s; i <= n; i*=) //從該節點的左孩子開始比較
 {
     if(i < n && vec[i] < vec[i+])  //如果左孩子小于右孩子
         i++;
     if(temp >= vec[i])
         break;
     vec[s] = vec[i];
     s = i;
 }
 vec[s] = temp;
}

void HeapSort(vector<int> &vec)
{
 int i;
 int n = vec.size();
 for(i = n / ; i >= ; i--)
 {
     HeapAdjust(vec, i, n);     //調整為大頂堆
 }
 for(i = n; i >=; i--)
 {
     swap(vec, , i);  //交換第一個元素和目前最後一個元素
     HeapAdjust(vec, , i-); //繼續調整
 }
}
           
```

面試知識點總結——排序算法排序算法比較七種排序算法

排序算法比較

七種排序算法

繼續閱讀

别人的百度面試

面試常考知識點—資料庫

資料庫 drop,delete,truncate三種删除方式的具體差別drop:delete：truncate:

C++ STL内部簡單細節整理STL的構成STL的版本

Java常見面試題—Future與FutureTask

常見面試題整理—Linux系統常用操作

typeof傳回值詳解

面試知識點總結 - ES6 異步處理方案 promise

C++類對象成員變量和成員函數記憶體配置設定的問題

面試知識點總結——深淺拷貝

後端面試知識點總結算法與資料結構算法與資料結構

面試知識點總結——構造函數解析

JAVA垃圾回收（GC）

45天突擊java面試，你準備好了嗎？#java本篇資料主要涵蓋了面試前的準備、履歷的寫作、面試中常見的知識點和問題、J

web前端中雙等==和三等===的差別