# 快速排序

快排(QUICK-SORT)基于分治思想，核心是对子数组partition，partition挑选一个参考基准(主元，通常为第一个或最后一个元素)，以主元为分界将数据分为两份，子数组递归partition。

// QUICKSORT
if p < r
   then q ← PARTITION(A, p, r)
        QUICKSORT(A, p, q - 1)
        QUICKSORT(A, q + 1, r)

// PARTITION
x ← A[r]
i ← p - 1
for j ← p to r - 1
     do if A[j] ≤ x
           then i ← i + 1
                exchange A[i] <-> A[j]
exchange A[i + 1] <-> A[r]
return i + 1

// GoLang
func partition(a []int, lo, hi int) int {
  pivot := a[hi]
  i := lo - 1
  for j := lo; j < hi; j++ {
    if a[j] < pivot {
      i++
      a[j], a[i] = a[i], a[j]
    }
  }
  a[i+1], a[hi] = a[hi], a[i+1]
  return i + 1
}

func quickSort(a []int, lo, hi int) {
  if lo >= hi {
    return
  }
  p := partition(a, lo, hi)
  quickSort(a, lo, p-1)
  quickSort(a, p+1, hi)
}

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 将给定数组排序
     * @param arr int整型vector 待排序的数组
     * @return int整型vector
     */
    vector<int> MySort(vector<int>& arr) {
        quickSort(arr, 0, arr.size() - 1);
        return arr;
    }
    
    void quickSort(vector<int>& arr, int lo, int hi) {
        if (lo >= hi) return;
        int p = partition(arr, lo, hi);
        quickSort(arr, lo, p - 1);
        quickSort(arr, p + 1, hi);
    }
    
    int partition(vector<int>& arr, int lo, int hi) {
        int pivot = arr[hi];
        int i = lo - 1;
        for (int j = lo; j < hi; j++) {
            if (arr[j] < pivot) {
                i++;
                swap(arr, i, j);
            }
        }
        swap(arr, i + 1, hi);
        return i + 1;
    }
    
    void swap(vector<int>& arr, int i, int j) {
        int tmp = arr[j];
        arr[j] = arr[i];
        arr[i] = tmp;
    }
};

# 归并排序

归并排序(MERGE-SORT)使用分治思想，每两个有序数组相互比较合并。

吹拉弹唱

# 快速排序

# 归并排序

# 堆排序

# 桶排序

# 冒泡排序

# 选择排序

# 插入排序