几种排序算法的实现与测速

2022-05-29

// Several sort algorithms' implement and examination
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
using namespace std;

void RandArray(int A[], int low, int high, int len) {
  srand(time(0));
  for (int i = 1; i <= len; i++) A[i] = rand() % (high - low + 1) + low;
}
void PrintArray(int A[], int len) {
  for (int i = 1; i < len; i++) cout << A[i] << ", ";
  cout << A[len] << endl;
}

// 插入排序算法
void InsertionSort(int A[], int len) {
  int i, j;
  for (i = 2; i <= len; i++) {
    A[0] = A[i];
    for (j = i - 1; A[0] < A[j]; j--) A[j + 1] = A[j];
    A[j + 1] = A[0];
  }
}

void HalfInsertionSort(int A[], int len) {
  int i, j, low, high, mid;
  for (i = 2; i <= len; i++) {
    A[0] = A[i];
    low = 1;
    high = i;
    while (low < high) {
      mid = (low + high) / 2;
      if (A[mid] < A[i])
        low = mid + 1;
      else
        high = mid - 1;
    }
    for (j = i; j > low; j--) A[j] = A[j - 1];
    A[low] = A[0];
  }
}

void ShellSort(int A[], int len) {
  for (int dk = len / 2; dk >= 1; dk /= 2)
    for (int i = dk + 1, j; i <= len; i++)
      if (A[i - dk] > A[i]) {
        A[0] = A[i];
        for (j = i - dk; j > 0 && A[0] < A[j]; j -= dk) A[j + dk] = A[j];
        A[j + dk] = A[0];
      }
}

// 交换排序算法
void BubbleSort(int A[], int len) {
  for (int k = len - 1; k >= 1; k--) {
    bool flag = true;
    for (int i = 1; i <= k; i++)
      if (A[i] > A[i + 1]) {
        swap(A[i], A[i + 1]);
        flag = false;
      }
    if (flag) return;
  }
}

int QSPartition(int A[], int low, int high) {
  int pivot = A[low];
  while (low < high) {
    while (low < high && A[high] >= pivot) high--;
    A[low] = A[high];
    while (low < high && A[low] <= pivot) low++;
    A[high] = A[low];
  }
  A[low] = pivot;
  return low;
}
void QS(int A[], int low, int high) {
  if (low < high) {
    int pivotpos = QSPartition(A, low, high);
    QS(A, pivotpos + 1, high);
    QS(A, low, pivotpos - 1);
  }
}
void QuickSort(int A[], int len) { QS(A, 1, len); }

// 选择排序算法
void SelectionSort(int A[], int len) {
  for (int i = 1; i < len; i++) {
    A[0] = A[i];
    int min = i;
    for (int j = i + 1; j <= len; j++)
      if (A[j] < A[0]) {
        min = j;
        A[0] = A[j];
      }
    if (i != min) swap(A[i], A[min]);
  }
}
void HeadAjust(int A[], int k, int len) {
  A[0] = A[k];
  for (int i = k * 2; i <= len; i *= 2) {
    if (i < len && A[i] < A[i + 1]) i++;
    if (A[0] >= A[i]) break;
    A[k] = A[i];
    k = i;
  }
  A[k] = A[0];
}
void HeapSort(int A[], int len) {
  for (int i = len / 2; i > 0; i--) HeadAjust(A, i, len);
  for (int i = len; i > 1; i--) {
    swap(A[i], A[1]);
    HeadAjust(A, 1, i - 1);
  }
}

// 归并排序
void Merge(int A[], int B[], int low, int mid, int high) {
  int i, j, k;
  for (i = low; i <= high; i++) B[i] = A[i];
  for (i = low, j = mid + 1, k = i; i <= mid && j <= high; k++)
    A[k] = (B[i] > B[j]) ? B[j++] : B[i++];
  while (i <= mid) A[k++] = B[i++];
  while (j <= high) A[k++] = B[j++];
}
void MS(int A[], int B[], int low, int high) {
  if (low < high) {
    int mid = (low + high) / 2;
    MS(A, B, low, mid);
    MS(A, B, mid + 1, high);
    Merge(A, B, low, mid, high);
  }
}
void MergeSort(int A[], int len) {
  int *B = (int *)malloc(sizeof(int) * (len + 1));
  MS(A, B, 1, len);
  free(B);
}

// 桶排序
void BucketSort(int A[], int len) {
  int bucket[len + 1];
  memset(bucket, 0, sizeof(int) * (len + 1));
  for (int i = 1; i <= len; i++) bucket[A[i]]++;
  for (int i = 0, j = 1; i <= len; i++)
    while (bucket[i]--) A[j++] = i;
}

void SpeedTest(void (**sorts)(int *, int), int n, int size) {
  int raw[size + 1];
  RandArray(raw, 0, size, size);
  int *A = new int[size + 1];
  for (int i = 0; i < n; i++) {
    memcpy(A, raw, sizeof(raw));
    clock_t start_time = clock();
    sorts[i](A, size);
    clock_t end_time = clock();
    printf("\t%.3f ms", double(end_time - start_time) / CLOCKS_PER_SEC * 1000);
  }
  cout << endl;
}

const int SIZE = 100;
void Test(void (*asort)(int *, int)) {
  int A[SIZE + 1];
  RandArray(A, 0, SIZE, SIZE);
  PrintArray(A, SIZE);
  int B[SIZE + 1];
  memcpy(B, A, sizeof(A));
  cout << "答案:";
  sort(B + 1, B + SIZE + 1);
  PrintArray(B, SIZE);
  cout << "结果:";
  asort(A, SIZE);
  PrintArray(A, SIZE);
}

int main(void) {
  // Test(&InsertionSort);
  // Test(&HalfInsertionSort);
  // Test(&ShellSort);
  // Test(&BubbleSort);
  // Test(&SelectionSort);
  // Test(&QuickSort);
  // Test(&HeapSort);
  // Test(&MergeSort);
  // Test(&BucketSort);

  void (*sorts[])(int *, int) = {
      &InsertionSort, &HalfInsertionSort, &ShellSort,
      &BubbleSort,    &SelectionSort,     &QuickSort,
      &HeapSort,      &MergeSort,         &BucketSort};
  cout << "数据规模\t直接插入\t折半插入\t希尔排序"
          "\t冒泡排序\t选择排序\t快速排序"
          "\t堆 排 序\t归并排序\t桶 排 序"
       << endl;
  for (int i = 1; i < 11; i++) {
    printf("%d", i * 2000);
    SpeedTest(sorts, 9, i * 2000);
  }

  return 0;
}

以下是我在服务器上跑出来的结果(clang++ -O2):

数据规模 直接插入 折半插入 希尔排序 冒泡排序 选择排序 快速排序 堆 排 序 归并排序 桶 排 序
2000 0.504 ms 0.272 ms 0.155 ms 4.964 ms 0.795 ms 0.103 ms 0.126 ms 0.118 ms 0.025 ms
4000 2.034 ms 0.752 ms 0.346 ms 20.473 ms 2.908 ms 0.220 ms 0.272 ms 0.233 ms 0.040 ms
6000 4.460 ms 1.479 ms 0.547 ms 46.734 ms 6.303 ms 0.332 ms 0.430 ms 0.382 ms 0.061 ms
8000 7.954 ms 2.433 ms 0.770 ms 82.834 ms 11.417 ms 0.452 ms 0.590 ms 0.496 ms 0.087 ms
10000 12.477 ms 3.648 ms 0.987 ms 130.707 ms 17.588 ms 0.580 ms 0.758 ms 0.630 ms 0.097 ms
12000 17.798 ms 5.127 ms 1.214 ms 193.288 ms 25.731 ms 0.717 ms 0.919 ms 0.788 ms 0.114 ms
14000 24.136 ms 6.934 ms 1.408 ms 256.753 ms 34.405 ms 0.843 ms 1.085 ms 0.890 ms 0.134 ms
16000 31.562 ms 9.034 ms 1.711 ms 333.238 ms 44.938 ms 0.980 ms 1.266 ms 1.064 ms 0.152 ms
18000 39.458 ms 11.540 ms 1.860 ms 426.160 ms 58.612 ms 1.130 ms 1.489 ms 1.178 ms 0.171 ms
20000 49.278 ms 14.158 ms 2.145 ms 522.074 ms 70.855 ms 1.238 ms 1.665 ms 1.319 ms 0.199 ms

UVa 201 正方形 题解