快速排序

基于分治
先快排再递归
image.png
暴力解法
image.png
快排代码模板

  1. #include <iostream>
  3. using namespace std;
  5. const int N = 1e6 + 10;
  7. int n;
  8. int q[N];
  10. void quick_sort(int q[], int l, int r)
  11. {
  12.     if(l >= r) return;
  13.     int x = q[l + r >> 1], i = l - 1, j = r + 1;
  14.     while(i < j)
  15.     {
  16.         do i ++ ; while(q[i] < x);
  17.         do j -- ; while(q[j] > x);
  18.         if (i < j) swap(q[i], q[j]);
  19.     }
  20.     quick_sort(q, l, j);  // i - 1
  21.     quick_sort(q, j + 1, r);  // i
  22. }
  24. int main()
  25. {
  26.     scanf("%d", &n);
  27.     for(int i = 0; i < n; i ++) scanf("%d", &q[i]);
  29.     quick_sort(q, 0, n - 1);
  31.     for(int i = 0; i < n; i ++) printf("%d ",q[i]);
  32.     return 0;
  33. }

归并排序

分治思想
先递归两边再做排序
双指针算法
image.png
image.png