常见排序算法及其稳定性分析

 
// 希尔排序
void ShellSort(int* a, int n) {
  int gap = n - 1;//grap为分组之间的间隔
  while (gap > 1) {
    gap = gap / 3 + 1;//每次分组的间距都越来越小，直到间距为一
    for (int i = 0; i < gap; i++) {//i表示每组的开头位置
      for (int j = i; j < n - gap; j += gap) {//对每一组插入排序
        int end = j;
        int temp = a[j + gap];
        while (end >= 0) {
          if (temp < a[end]) {
            a[end + gap] = a[end];
            end -= gap;
          }
          else {
            break;
          }
        }
        a[end + gap] = temp;
      }
    }
  }
}

int PartSort1(int* a, int left, int right) {//单趟排序
  int end = right;
  int begin = left;
  int mid = GetMid(a, left, right);//基准值的下标
  Swap(&a[left], &a[mid]);//跟首元素交换
  int key = left;
  while (begin < end) {
    while (end > begin && a[end] >= a[key])end--;
    while (end > begin && a[begin] <= a[key])begin++;
    Swap(&a[end], &a[begin]);
  }
  Swap(&a[key], &a[begin]);
  return begin;//单趟排序后返回最后key所处的位置
}
void QuickSort(int* a, int left, int right){//递归
     if (left >= right)return;
      int mid = PartSort3(a, left, right);
    QuickSort(a, left, mid - 1);
    QuickSort(a, mid + 1, right);
}

void QuickSortNonR(int* a, int left, int right) {
  Stack ST;
  StackInit(&ST);
  StackPush(&ST, right);//根据栈的特性，先将右区间压栈
  StackPush(&ST, left);
  while (!StackEmpty(&ST)) {
    int l = StackTop(&ST);
    StackPop(&ST);
    int r = StackTop(&ST);
    StackPop(&ST);//取出一个区间[l,r]
    if (l > r)Swap(&l, &r);
    int keyi = PartSort1(a, l, r);//单趟排序
    if (keyi -1> l) {
      StackPush(&ST, keyi - 1);
      StackPush(&ST, l);
    }
    if (keyi + 1 < r) {
      StackPush(&ST, r);
      StackPush(&ST, keyi + 1);
    }
  }
  StackDestroy(&ST);
}

void MergeSort(int* a, int begin, int end, int* temp) {//temp用于暂时存放合并后的数组
  if (begin >= end)return;
  int mid = (begin + end) / 2;
  MergeSort(a, begin, mid, temp);
  MergeSort(a, mid + 1, end, temp);//先递归区间
  
  int begin1 = begin, end1 = mid;
  int begin2 = mid + 1, end2 = end;//两个区间的端点指针
  int i = begin;//合并数组的下标的指针
  while (begin1 <= end1 && begin2 <= end2) {
    if (a[begin1] < a[begin2]) {//比较两个区间的首元素，小的放入temp中，两个指针往后移
      temp[i++] = a[begin1++];
    }
    else {
      temp[i++] = a[begin2++];
    }
  }//有可能还有某个区间还有元素没有放进去
  while (begin1 <= end1) {
    temp[i++] = a[begin1++];
  }
  while (begin2 <= end2) {
    temp[i++] = a[begin2++];
  }
  //将合并好的数组复制到原数组中
  memcpy(a + begin, temp + begin, sizeof(int) * (end - begin + 1));
}

 
void MergeSortNonR(int* a, int n) {
  int* temp = malloc(sizeof(int) * n);
  if (temp == NULL) {
    perror("malloc");
  }
 
  int grap = 1;//每组元素个数，根据递归区间思想，上一层的组长度是下一层的一半
  
  while (grap < n) {//分组的元素个数小于n,等于n意味着就是整个数组
    for (int i = 0; i < n; i += grap * 2) {//每次合并相邻两个区间，i为第一个区间的起点
      int begin1 = i, end1 = i + grap - 1;
      int begin2 = i + grap, end2 = i + grap * 2 - 1;
 
      if (end1 >= n || begin2 >= n) {//查看当前的相邻的两个区间是否在数组中
        break;
      }
      if (end2 >= n) {//可能不够均分，最后一个区间右端点取n-1
        end2 = n - 1;
      }
      int cur = i;//以下就是合并区间
      while (begin1 <= end1 && begin2 <=end2) {
        if (a[begin1] < a[begin2]) {
          temp[cur++] = a[begin1++];
        }
        else {
          temp[cur++] = a[begin2++];
        }
      }
 
      while (begin1 <= end1) {
        temp[cur++] = a[begin1++];
      }
      while (begin2 <= end2) {
        temp[cur++] = a[begin2++];
      }
      memcpy(a + i, temp+i, sizeof(int)*(end2 -i + 1));
    }
    grap = grap * 2;//上一层的每一个区间元素个数
  }
  free(temp);
}