快速排序

1. 快速排序是在数组中随机的找一个值，将比这个值小的数放在该数的左边，大的放在右边，然后左右分别递归。
2. 将每次递归的左右端点设为l, r
3. 首先在数组中随机取一个值存放在x中，我直接取数组中间位置的值。int x = a[l + r >> 1]（>>是位运算）
4. 然后定义两个指针i, j分别从左往右和从右往左。
5. 先将i从左往右移动，直到遇到一个比x大的数就停下。j相反。
6. 然后判断i < j成立的话就交换两个数。

void qs(int l, int r) {
  if (l >= r) return;	//此时只有一个值，直接返回
  int x = a[(r - l >> 1) + l];	//取中间值作为随机值
  int i = l - 1, j = r + 1;	//左右指针指向数组外面1的位置，方便后面操作
  while (i < j) {	//调整位置，知道i < j
    while (a[++i] < x);
    while (a[--j] > x);
    if (i < j) swap(a[i], a[j]);
  }
  qs(l, j);	//递归
  qs(j + 1, r);
}

归并排序

1. 二分数组，然后将排好序的左右数组合并成一个数组。

void ms(int l, int r) {
  if (l >= r) return;	//此时只有一个值，直接返回
  int mid = (r - l >> 1) + l;	//取中点
  ms(l, mid);	//左
  ms(mid + 1, r);	//右
  int i = l, j = mid + 1, k = l;	//两个指针分别指向左右的第一个位置
  while (i <= mid && j <= r) tmp[k++] = a[i] < a[j] ? a[i++] : a[j++];	//比较指针位置大小，然后放进tmp，移动指针
  //将剩下的放进tmp
  while (i <= mid) tmp[k++] = a[i++];
  while (j <= r) tmp[k++] = a[j++];
  for (int i = l; i <= r; ++i) a[i] = tmp[i];	//排好序之后放回源数组
}

堆排序

1. 维护一个完全二叉树，由于是完全二叉树，所以直接用一个数组来模拟不会浪费空间。根节点为i,左右分别为2*i和2*i+1
2. 该二叉树的根节点小于等于两个子节点。(递归定义)
3. 定义一个down操作，将不满足上述定义的根节点向下移动。
4. 先直接将所有数值放进数组中
5. 然后将数组的前半段执行down操作（只需要操作前半段就可以排序整个数组）

#include <iostream>
using namespace std;
const int N = 1e5 + 10;

int h[N], cnt, n, m;

void down(int u) {
  int t = u, uu = u << 1;	//计算根节点的2倍，减少后面的计算次数 
  if (uu <= cnt && h[uu] < h[t]) t = uu;	//和左边比较
  if (uu +1 <= cnt && h[uu + 1] < h[t]) t = uu + 1;	//和右边比较
  if (t != u) {	//判断是否需要交换
    swap(h[t], h[u]);
    down(t);
  }
}

int main(){
  cin >> n >> m;
  for (int i = 1; i <= n; ++i) scanf("%d", &h[i]);
  cnt = n;
  for (int i = n >> 1; i ; --i) down(i);
  
  while (m--) {
    printf("%d ", h[1]);
    h[1] = h[cnt--];
    down(1);
  }
  return 0;
}

六种排序算法的性能分析

#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
const int M = 1e4 + 10;

int a[N], a_bak[N], tmp[N], algo[N], n, m, cnt, all[6][M];
char name[6][15] = {"Quick Sort", "Merge Sort",  "Heap Sort",
                    "Shell Sort", "Bubble Sort", "Select Sort"};
clock_t st, ed;

void init() {
  srand(time(NULL));
  for (int i = 1; i <= n; ++i) algo[i] = a[i] = a_bak[i] = rand();
  a[0] = INT32_MIN;
  sort(algo + 1, algo + n + 1);
}

//第x个算法的第y次测试
void judge(int x, int y) {
  bool flag = 1;
  for (int i = 1; i <= n; ++i)
    if (a[i] != algo[i]) {
      printf("%s\t Test %d        Wrong Anwser\n", name[x], y);
      flag = 0;
      break;
    }
  if (flag) {
    printf("%s\t Test %d        Time Spent : %dms\n", name[x], y,
           (int)(ed - st));
    all[x][y] = (int)ed - st;
  }
  memcpy(a, a_bak, (n + 1) * sizeof(int));
}

//耗时分析
void analyze() {
  double ave, max, min, sum;
  for (int i = 0; i < 6; ++i) {
    min = max = all[i][0];
    sum = 0;
    for (int j = 0; j < m; ++j) {
      sum += all[i][j];
      if (all[i][j] < min) min = all[i][j];
      if (all[i][j] > max) max = all[i][j];
    }
    ave = sum / m;
    printf("%s :\n  Fastest : %.2lf\t  Slowest : %.2lf\t  Average : %.5lf\n\n",
           name[i], min, max, ave);
  }
}

// debug
void display() {
  for (int i = 1; i <= n; ++i) printf("%d ", a[i]);
  puts("");
}

void quick_sort(int l, int r) {
  if (l >= r) return;
  int x = a[(r - l >> 1) + l];
  int i = l - 1, j = r + 1;
  while (i < j) {
    while (a[++i] < x)
      ;
    while (a[--j] > x)
      ;
    if (i < j) swap(a[i], a[j]);
  }
  quick_sort(l, j);
  quick_sort(j + 1, r);
}

void merge_sort(int l, int r) {
  if (l >= r) return;
  int mid = (r - l >> 1) + l;
  merge_sort(l, mid);
  merge_sort(mid + 1, r);
  int i = l, j = mid + 1, k = l;
  while (i <= mid && j <= r) tmp[k++] = a[i] < a[j] ? a[i++] : a[j++];
  while (i <= mid) tmp[k++] = a[i++];
  while (j <= r) tmp[k++] = a[j++];
  for (int i = l; i <= r; ++i) a[i] = tmp[i];
}

// heap down操作
void down(int u) {
  int uu = u << 1, t = u;
  if (uu <= cnt && a[t] > a[uu]) t = uu;
  if (uu + 1 <= cnt && a[t] > a[uu + 1]) t = uu + 1;
  if (t != u) {
    swap(a[t], a[u]);
    down(t);
  }
}

void heap_sort() {
  int k = 1;
  cnt = n;
  for (int i = n >> 1; i; --i) down(i);
  while (cnt) {
    tmp[k++] = a[1];
    a[1] = a[cnt--];
    down(1);
  }
  for (int i = 1; i <= n; ++i) a[i] = tmp[i];
}

// 步长3
// void shell_sort(int n) {
//   int h = 1;
//   while (h < n / 3) h = 3 * h + 1;
//   while (h >= 1) {
//     for (int i = h; i < n; i++) {
//       for (int j = i; j >= h && a[j] < a[j - h]; j -= h) {
//         swap(a[j], a[j - h]);
//       }
//     }
//     h = h / 3;
//   }
// }

int get_sedgewick_arr(int n) {
  int i = 0, j, k = 1;
  while (true) {
    j = 9 * ((1 << 2 * i) - (1 << i)) + 1;
    if (j <= n) tmp[k++] = j;
    j = (1 << 2 * i + 4) - 3 * (1 << i + 2) + 1;
    if (j <= n)
      tmp[k++] = j;
    else
      break;
    i += 1;
  }
  return k;
}

// sedgewick步长
void shell_sort(int n) {
  int k = get_sedgewick_arr(n);
  int i, j, t, step;
  while (--k) {
    step = tmp[k];
    for (i = step; i < n; ++i) {
      j = i;
      t = a[j];
      while (j >= step) {
        if (t < a[j - step]) {
          a[j] = a[j - step];
          j -= step;
        } else
          break;
      }
      a[j] = t;
    }
  }
}

void bubble_sort() {
  for (int i = 1; i <= n; ++i)
    for (int j = n - 1; j >= i; --j)
      if (a[j] > a[j + 1]) swap(a[j], a[j + 1]);
}

void select_sort() {
  int min;
  for (int i = 1; i <= n; ++i) {
    min = i;
    for (int j = i + 1; j <= n; ++j)
      if (a[j] < a[min]) min = j;
    swap(a[i], a[min]);
  }
}

int main() {
  cin >> n >> m;  //每组n个随机数，共测试m组
  for (int i = 0; i < m; ++i) {
    init();
    int k = 6;
    while (k--) {
      st = clock();
      switch (k) {
        case 0:
          quick_sort(1, n);
          break;
        case 1:
          merge_sort(1, n);
          break;
        case 2:
          heap_sort();
          break;
        case 3:
          shell_sort(n + 1);
          break;
        case 4:
          bubble_sort();
          break;
        case 5:
          select_sort();
          break;
      }
      ed = clock();
      // display();
      judge(k, i);
    }
    puts("=================================================\n");
  }
  analyze();
  return 0;
}

输入n m分别代表产生乱序数组长度和测试次数。