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

// 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;
}