插?排序

插?排序(Insertion Sort)類似于玩撲克牌插牌過程，每次將?個待排序的元素按照其關鍵字??插?到前?已排好序的序列中，按照該種?式將所有元素全部插?完成即可

#include <iostream>  
using namespace std;  const int N = 1e5 + 10;  
int n;  
int a[N];  void insert_sort()  
{  // 依次枚舉待排序的元素  for(int i = 2; i <= n; i++) // 第?個位置默認就是有序的  {  int key = a[i];  // 前?? key ?的，統?右移  int j = i - 1;  while(j >= 1 && a[j] > key)  {  a[j + 1] = a[j];  j--;  }  a[j + 1] = key;  }  
}int main()  
{  cin >> n;  for(int i = 1; i <= n; i++) cin >> a[i];  insert_sort();  for(int i = 1; i <= n; i++) cout << a[i] << " ";  return 0;  
}

時間復雜度

• 當整個序列有序的時候，插?排序最優，此時時間復雜度為O(n) 。
• 當整個序列逆序的時候，每個元素都要跑到最前?，時間復雜度為O(n2)

選擇排序

選擇排序(Selection Sort)是?種特別直觀的排序算法。每次找出未排序序列中最?的元素，然后放進有序序列的后?

#include <iostream>  
using namespace std;  
const int N = 1e5 + 10;  
int n;  
int a[N];  
void selection_sort()  
{  for(int i = 1; i < n; i++) // 待排序區間的?位置  {  // [i, n] 區間就是待排序的區間  int pos = i;for(int j = i + 1; j <= n; j++) // 查找待排序區間最?的元素的下標  {  if(a[j] < a[pos])  {  pos = j;  }  }  swap(a[i], a[pos]);  }  
}  
int main()  
{  cin >> n;  for(int i = 1; i <= n; i++) cin >> a[i];  selection_sort();  for(int i = 1; i <= n; i++) cout << a[i] << " ";  return 0;  
}

【時間復雜度】

• ?論數組有序還是?序，在未排序區間內找最?值的時候，都需要遍歷?遍待排序的區間，因此時間復雜度為O(n2)

冒泡排序

冒泡排序(Bubble Sort)也是?種簡單的排序算法。它的?作原理是每次檢查相鄰兩個元素，如果前?的元素與后?的元素滿?給定的排序條件，就將相鄰兩個元素交換。當沒有相鄰的元素需要交換時，排序就完成了。
由于在算法的執?過程中，較?的元素像是?泡般慢慢浮到數列的末端，故叫做冒泡排序

#include <iostream>
using namespace std;  
const int N = 1e5 + 10;  
int n;  
int a[N];  
// 優化后的冒泡排序  
void bubble_sort()  
{  // 依次枚舉待排序區間的最后?個元素  for(int i = n; i > 1; i--)  {  bool flag = false;  // [1, i] 就是待排序區間  for(int j = 1; j < i; j++)  {  if(a[j] > a[j + 1])  {  swap(a[j], a[j + 1]);  flag = true;  }  }  if(flag == false) return;  }  
}  
int main()  
{  cin >> n;  for(int i = 1; i <= n; i++) cin >> a[i];  bubble_sort();  for(int i = 1; i <= n; i++) cout << a[i] << " ";  return 0;  
}

時間復雜度

• 如果數組有序，只會掃描?遍，時間復雜度為O(n) 。
• 如果逆序，所有元素都會向后冒?次到合適位置，時間復雜度為O(n2)

堆排序

堆排序(Heap Sort)是指利?堆這種數據結構所設計的?種排序算法。本質上是優化了選擇排序算法，如果將數據放在堆中，能夠快速找到待排序元素中的最?值或最?值。
堆排序的過程分兩步：

1. 建堆。升序建?堆，降序建?堆。
   建堆過程，從倒數第?個?葉?節點開始，倒著?直到根結點位置，每個結點進?向下調整。
2. 排序。刪除堆頂的邏輯。
   每次將堆頂元素與堆中最后?個元素交換，然后將堆頂元素往下調整。直到堆中剩余?個元素，所有元素就都有序了。
   因此，堆排序僅需?到向下調整算法

#include <iostream>  
using namespace std;  
const int N = 1e5 + 10;  
int n;  
int a[N];  
void down(int parent, int len)  
{  int child = parent * 2;  while(child <= len)  {  if(child + 1 <= len && a[child + 1] > a[child]) child++;  if(a[parent] >= a[child]) return;swap(a[parent], a[child]);  parent = child;  child = parent * 2;  }  
}  
void heap_sort()  
{  // 1. 建堆  for(int i = n / 2; i >= 1; i--)  {  down(i, n);  }  // 2. 排序  for(int i = n; i > 1; i--) // 枚舉堆??最后?個元素的位置  {  swap(a[1], a[i]);  down(1, i - 1);  }  
}  
int main()  
{  cin >> n;  for(int i = 1; i <= n; i++) cin >> a[i];  heap_sort();  for(int i = 1; i <= n; i++) cout << a[i] << " ";  return 0;  
}

時間復雜度
時間復雜度需要計算兩部分：?部分是建堆的時間復雜度，另?部分是排序。

• 排序部分的時間復雜度很好估計，每次都是從堆中選擇?個最?值，然后與最后?個元素交換，然后調整。?次選擇的時間復雜度為log n ，?共執?n 次，?概就是n log n 級別。
• 建堆的時間復雜度：
  計算向下調整算法建堆時間復雜度
  

則需要移動結點總的移動步數為：每層結點個數*向下調整次數
$$T(h)=2^h?1?h$$
根據?叉樹的性質：n = 2^h - 1 和h = log2 (n + 1)
$$T(n)=n?{\log }_2(n+1)\approx n$$

綜上所述，堆排序的時間復雜度主要取決于排序的過程，也就是n log n

快速排序

快速排序(Quick Sort)，既然敢起這樣的名字，說明它是常?排序算法中較為優秀的。事實上，在很多情況下，快排確實是效率較?的算法

算法原理

常規快排：在待排序區間中任取?個元素作為樞軸(pivot，或稱基準值，通常選取區間?元素)，然后按照基準值??將區間中元素分割成左右兩部分，左側區間中元素?于基準值，右側區間中元素?于等于基準值，即基準值已經放在其該放的位置上，該過程稱為?次劃分。劃分結束后，再遞歸排基準值左側，遞歸排基準值右側即可

優化?：三路劃分

三路劃分優化：其實可以做到按照基準元素，將所有元素分成三個區間。左部分全部?于pivot，中間部分全部等于pivot，右部分全部?于pivot。然后中間部分就不?管了，直接遞歸處理左右部分

1. 從區間中任取一個元素作為基準值，一般取區間最左側元素，然后按照基準值對區間中元素進行劃分
   

2. 遞歸排基準值左側；遞歸排基準值右側
   ?這個三路劃分，就是典型的數組分三塊算法

優化?：隨機選擇基準元素

選擇基準元素的?式：

• 每次選擇待排序序列的最左邊元素
  那么，當整個序列有序的時候，每次遞歸就會劃分出特別?的?段右區間，遞歸的層數是n次，每次要遍歷整個數組?遍，時間復雜度就退化成n^2 。
  每次選擇最右邊元素也是同理。
• 每次選擇待排序序列的中間元素
  可以構造?個特殊的序列，使得每次取中間元素的時候都會取到最?值，依舊會退化成n^2。
• 隨機選擇基準元素
  每次選擇基準元素的時候，都從待排序的序列中隨機選擇?個數。在隨機性的前提下，可以證明算法的時間復雜度趨近于nlogn 。
  因此，每次選擇基準元素時，都使?隨機函數選擇

C++中的隨機函數

C++提供了函數srand和rand，搭配使?可以返回?個隨機值

#include <iostream>  
#include <ctime>  
using namespace std;  
int main()  
{  srand(time(0)); // 種下?個隨機數種?  for(int i = 1; i <= 10; i++)  {  cout << rand() << endl; // 每次?成?個隨機值  }  return 0;  
}

left和right指向第一個和最后一個元素，假設p等于4

i從第一個元素往最后一個元素遍歷
現在ai是4，和p一樣大，i++

ai是2，比p小，交換到前面，++l和i交換，i++

現在ai是4，和p一樣大，i++

現在ai是5，比p大，交換到最右邊，i和–r交換

i這是下標為4，ai為1，比p小，++l和i交換，i++

這是i等于5，r也是5，遍歷結束，此時p=4，兩個4已經在正確的位置上
中間區域也就是相等的區域，是l+1到r-1
左邊比p小的區域是left到l，右邊比p大的區域是r到right
接著遍歷left到l和r到right

#include <iostream>  
#include <ctime>  
using namespace std;  
const int N = 1e5 + 10;  
int n;  
int a[N];  
// 優化?：隨機選擇基準元素  
int get_random(int left, int right)  
{  return a[rand() % (right - left + 1) + left];  
}  void quick_sort(int left, int right)  
{  if(left >= right) return;  // 1. 選擇?個基準元素  int p = get_random(left, right);  // 2. 數組分三塊 - 荷蘭國旗問題  int l = left - 1, i = left, r = right + 1;  while(i < r)  {  if(a[i] < p) swap(a[++l], a[i++]);  else if(a[i] == p) i++;  else swap(a[--r], a[i]);  }  // [left, l] [l + 1, r - 1] [r, right]  quick_sort(left, l);  quick_sort(r, right);  
}  
int main()  
{  srand(time(0));  cin >> n;  for(int i = 1; i <= n; i++) cin >> a[i];  quick_sort(1, n);for(int i = 1; i <= n; i++) cout << a[i] << " ";  return 0;  
}

時間復雜度

• 如果每次基準元素都選擇得當，數組劃分的比較均勻，時間復雜度=遞歸層數*N*logN
• 如果劃分不當，數組分布比較極端，時間復雜度退化成N^2

歸并排序

歸并排序(Merge Sort)是?論數據有什么特性，時間復雜度就能穩定O(n log n) 的排序算法
歸并排序?的是分治思想，不知道分治是啥也沒關系，后續算法課會講到。它的主要過程分兩步：

1. 將整個區間從中間?分為?，先把左邊和右邊排排序；
2. 然后將左右兩個有序的區間合并在?起。
   其中，如何讓左右兩邊有序，就繼續交給歸并排序，因此歸并排序是?遞歸來實現的；合并兩個有序區間的操作，在順序表中講過類似的算法題

#include <iostream>  
using namespace std;  
const int N = 1e5 + 10;  
int n;  
int a[N];  
int tmp[N]; // 輔助歸并排序時，合并兩個有序數組  
void merge_sort(int left, int right)  
{  if(left >= right) return;  // 1. 先?分為?  int mid = (left + right) >> 1;  // [left, mid] [mid + 1, right]  // 2. 先讓左右區間有序  merge_sort(left, mid);  merge_sort(mid + 1, right);// 3. 合并兩個有序數組  int cur1 = left, cur2 = mid + 1, i = left;  // [left, mid] [mid + 1, right]  while(cur1 <= mid && cur2 <= right)  {  if(a[cur1] <= a[cur2]) tmp[i++] = a[cur1++];  else tmp[i++] = a[cur2++];  }  while(cur1 <= mid) tmp[i++] = a[cur1++];  while(cur2 <= right) tmp[i++] = a[cur2++];  for(int j = left; j <= right; j++)  {  a[j] = tmp[j];  }  
}  int main()  
{  cin >> n;  for(int i = 1; i <= n; i++) cin >> a[i];  merge_sort(1, n);  for(int i = 1; i <= n; i++) cout << a[i] << " ";  return 0;  
}

【時間復雜度】
每次遞歸都是標準的?分為?，因此時間復雜度為O(n log n)