排序 (Sort)

氣泡排序 (Bubble Sort)

i 和 i+1 比，比較大的往後。
經過一輪後，最大的會在最後面，下一論則不比較已經排好的。

//declare arr[size]
for(i=size-1; i>=1; i--) //當i=1時，j只做0和1。
  for(j=0; j<i; j++)
    if(arr[j] > arr[j+1])
      //switch

效率：O(n²)

插入排序 (Insertion Sort)

第1個元素不用排，在已排序區，其他都在未排序區。
從第2個元素開始，插到已排序區。在已排序區中，從尾端往回比較大小排序。

for(i=1; i<size; i++){
  insert = arr[i];
  j=i-1; //往回比大小
  while(j>=0 && arr[j]>insert){
    arr[j+1] = arr[j]; //insert還獨立在外面
    j--;
  }
  arr[j+1] = insert; //while()退出時會-1，所以要+1
}

效率：O(n²)

合併排序 (Merge Sort)

#include <bits/stdc++.h>
using namespace std;
#define size 6
void merge(int *arr, int L, int M, int R){
  int left = L; //左半部執行到第幾個
  int right = M+1; 
  int tmp[size], i=L; //i是陣列tmp的索引值
  while((left<=M)&&(right<=R)){ //代表還有元素可以合併
    if(arr[left]<arr[right])
      tmp[i++]=arr[left++];
    else tmp[i++]=arr[right++];
  }
  while(left<=M) //代表還有剩餘元素需要放入陣列tmp
    tmp[i++]=arr[left++];
  while(right<=R)
    tmp[i++]=arr[right++];
  for(i=L; i<=R; i++)
    arr[i] = tmp[i];
}
void mergesort(int *arr, int L, int R){
  int M;
  if(L<R){
    M = (L+R)/2;
    mergesort(arr, L, M); //切割成左半部
    mergesort(arr, M+1, R);
    merge(arr, L, M, R);
  }
}
int main(){
  int arr[size] = {3,2,5,1,4,6};
  mergesort(arr, 0, size-1);
  for(int i=0; i<size; i++)
    cout << arr[i] << " ";
}

效率：O(n log(n))

快速排序 (Quick Sort)

效率：O(n log(n))

選一個 pivot 為基準，找出 i 和 j。
i 為由前往後第一個 > pivot 的，j 為由後往前第一個 < pivot 的。
找到 i 和 j 後，如果 i ≤ j，i 與 j 互換。
如果 j 在 i 的左邊或 i 和 j 相同，pivot 與 j 互換，此時 pivot 已排序完畢。
以 pivot 的左半部與右半部分成兩部分，重複以上步驟。

//Quick Sort
#include <stdio.h>
#define size 10
void quicksort(int *arr, int l, int r){
  int i=l, j=r+1, tmp;
  if(l<r){
    while(i<j){
      while(arr[++i] < arr[l]);
      while(arr[--j] > arr[l]);
      if(i>=j) break;
      tmp = arr[i];
      arr[i] = arr[j];
      arr[j] = tmp;
    }
    tmp = arr[j];
    arr[j] = arr[l];
    arr[l] = tmp;
    quicksort(arr, l, j-1);
    quicksort(arr, j+1, r);
  }
}
int main(){
  int arr[size] = {7,1,8,3,5,2,9,6,0,4};
  quicksort(arr, 0, size-1);
  int i;
  for(i=0; i<size; i++)
    printf("%d ", arr[i]);
}