排序算法之插入排序和希尔排序（shell sort）

插入排序（inserction sort）和希尔排序（shell sort）

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

void reverseArray(int in[], int out[], int size); // 数组逆序
void adjustArray(int in[], int out[], int size); // 数组调整，使之轻微乱序
void randomArray(int in[], int out[], int size); // 使数组乱序
void insertionSort(int arr[], int size); // 插入排序
void shellSort(int arr[], int size); // 希尔排序
void printArray(int arr[], int size); // 显示数组元素
int cmp(const void *a, const void *b); // 比较器，用于系统qsort函数

void reverseArray(int in[], int out[], int size) {
  int arr[size];
  memcpy(arr, in, sizeof(int) * size);
  for (int i = 0; i < size; i++) {
    out[i] = arr[size - 1 - i];
  }
}

void adjustArray(int in[], int out[], int size) {
  srand((unsigned int)time(0));
  memcpy(out, in, sizeof(int) * size);
  int n = size < 30 ? 1 : size / 30;
  for (int i = 0; i < n; i++) {
    int r = rand() % size;
    int r2 = r + 3;
    if (r + 3 >= size) {
      r2 = r - 3;
    }
    int temp = out[r];
    out[r] = out[r2];
    out[r2] = temp;
  }
}

void randomArray(int in[], int out[], int size) {
  srand((unsigned int)time(0));
  int arr[size];
  memcpy(arr, in, sizeof(int) * size);
  int n = 0;
  for (; n < size; n++) {
    int pos = 0;
    int r = rand() % (size - n);
    for (int i = 0; i < size; i++) {
      if (arr[i] != -1) {
        if (pos == r) {
          out[n] = arr[i];
          arr[i] = -1;
          break;
        }
        pos++;
      } else {
        continue;
      }
    }
  }
}

void insertionSort(int arr[], int size) {
  for (int i = 0; i < size; i++) {
    int temp = arr[i];
    int p = i - 1;
    while (p >= 0 && temp < arr[p]) {
      arr[p + 1] = arr[p];
      p--;
    }
    arr[p + 1] = temp;
  }
}

void shellSort(int arr[], int size) {
  for (int gap = size / 2; gap > 0 ; gap /= 2) {
    for (int i = gap; i < size; i++) {
      int temp = arr[i];
      int p = i - 1;
      while (p + 1 - gap >= 0 && temp < arr[p + 1 - gap]) {
        arr[p + 1] = arr[p + 1 - gap];
        p -= gap;
      }
      arr[p + 1] = temp;
    }
  }
}

void printArray(int arr[], int size) {
  for (int i = 0; i < size; i++) {
    printf("%d ", arr[i]);
  }
  printf("\n");
}

int cmp(const void *a, const void *b) {
  return *((int *)a) - *((int *)b);
}

void demo(int size, int type) {
  int data[size];
  for (int i = 0; i < size; i++) {
    data[i] = i;
  }
  if (type == 0) {
    randomArray(data, data, size);
  } else if (type == 1) {
    adjustArray(data, data, size);
  } else {
    reverseArray(data, data, size);
  }

  if (size < 30) printArray(data, size);
  int data2[size];
  memcpy(data2, data, sizeof(data));
  int data3[size];
  memcpy(data3, data, sizeof(data));
  clock_t t = clock();
  qsort(data, size, sizeof(int), &cmp);
  char *names[] = {"乱序", "几乎顺序", "逆序"};
  printf("%d个数据，%s，系统qsort耗时%ld微秒\n", size, names[type], clock() - t);
  t = clock();
  shellSort(data2, size);
  printf("%d个数据，%s，希尔排序耗时%ld微秒\n", size, names[type], clock() - t);
  t = clock();
  insertionSort(data3, size);
  printf("%d个数据，%s，插入排序耗时%ld微秒\n", size, names[type], clock() - t);
  if (size < 30) printArray(data, size);
  printf("\n");
}

int main(int argc, const char * argv[]) {
  demo(25, 0);
  demo(25, 1);
  demo(25, 2);
  demo(100, 0);
  demo(100, 1);
  demo(100, 2);
  demo(500, 0);
  demo(500, 1);
  demo(500, 2);
  demo(5000, 0);
  demo(5000, 1);
  demo(5000, 2);
  demo(50000, 0);
  demo(50000, 1);
  demo(50000, 2);
}

相关文章

排序算法之快速排序