【算法】六大排序 插入排序 希尔排序 选择排序 堆排序 冒泡排序 快速排序

//直接插入排序
void InsertSort(int* a,int n)
{
  //排序 
  for (int i = 0; i + 1 < n; i++)
  {
    //end是有序数列的最后一个位置的下标
    int end = i;
    int tmp = a[end + 1];
    //end >= 0 防止在--end时数组越界
    while (end >= 0 && tmp < a[end])
    {
      a[end +1] = a[end];
      --end;
    }
    a[end+1] = tmp;
  }
}

//希尔排序   正常一组一组排序
void ShellSort(int* a,int n)
{
  //定义第一次gap的值  
  int gap = n;
  //多次预排序，gap=1时是直接排序
  while (gap > 1)
  {
    //减小gap的值直到1
    gap = gap / 3 + 1;
    //多趟排序
    for (int j = 0; j < gap; j++)
    {
      //单趟排序  i是当前有序序列最后一个位置的下标
      for (int i = j; i + gap < n; i += gap)
      {
        int end = i;
        //记录一下待插入的数据
        int tmp = a[end + gap];
        //end >= 0 防止在end -=gap 时数组越界
        while (end >= 0 && tmp < a[end])
        {
          a[end + gap] = a[end];
          end -= gap;
        }
        a[end + gap] = tmp;
      }
    }
  }
}

//选择排序
void SelectSort(int* a, int n)
{
  //多趟排序
  int begin = 0;
  int end = n - 1;
  while (begin < end)
  {
    //先假设 a[0] 位置既是最小值又是最大值
    //mini是最小值的下标，maxi是最大位置的下标
    int mini = begin, maxi = begin;
    //单趟遍历，选出最大值于最小值
    for (int i = begin; i <=end; ++i)
    {
      if (a[i] > a[maxi])
      {
        maxi = i;
      }
      else if (a[i] < a[mini])
      {
        mini = i;
      }
    }
    Swap(&a[begin], &a[mini]);
    if (begin == maxi)
    {
      maxi = mini;
    }
    Swap(&a[end], &a[maxi]);
    ++begin;
    --end;
  }
}

//冒泡排序
int BubbleSort(int*a,int n)
{
  for (int j = 0; j < n; j++)
  {
    //end是排序数组的最后一个需要排序元素的下标
    int end = n - 1 - j;
    //定义一个交换标志
    int exchange = 0;
    for (int i = 0; i < end; i++)
    {
      if (a[i] > a[i + 1])
      {
        Swap(&a[i], &a[i + 1]);
        exchange = 1;
      }
    }
    // 一趟冒泡过程中，没有发生交换，说明已经有序了，不需要再处理
    if (exchange == 0)
    {
      break;
    }
  }
}

//快速排序   hoare法   
void QuickSort(int* a, int begin, int end)
{
  //当区间只有一个值时，或区间不存在时退出递归
  if (begin >= end)
  {
    return;
  }
  //left是闭区间最最左边的下标，right是最右边位置的下标
  int left = begin, right = end;
  //选择最左边作为key值
  int keyi = left;
  //一趟排序
  while (left < right)
  {
    //右边先走，找到a[right]<key的位置
    while (left < right && a[right] >= a[keyi])
    {
      --right;
    }
    //左边后走，找到a[left]>key的位置
    while (left < right && a[left] <= a[keyi])
    {
      ++left;
    }
    //交换左右两边的值,如果left == right了，也没有必要交换了。
    if (left != right)
    {
      Swap(&a[left], &a[right]);
    }
  }
  //交换左右两边的值,如果keyi == left了，也没有必要交换了。
  if (keyi != left)
  {
    Swap(&a[keyi], &a[left]);
  }
  keyi = left;
  //此时区间被分割为[begin,keyi-1] keyi [keyi+1,end]
  //注意传递的是begin,不是0,中间递归时不一定是从0开始的区间，0是一个常量，begin是一个变量。
  QuickSort(a, begin, keyi-1);
  QuickSort(a, keyi+1, end);
}

//快速排序  挖坑法
void QuickSort(int* a, int begin, int end)
{
  //当区间只有一个值时，或区间不存在时退出递归
  if (begin >= end)
  {
    return;
  }
  int left = begin, right = end;
  int keyi = left;
  //刚开始时keyi的位置作为坑位
  int hole = keyi;
  int key = a[keyi];
  while (left < right)
  {
    while (left < right && a[right] >= key)
    {
      --right;
    }
    a[hole] = a[right];
    hole = right;
    while (left < right && a[left] <= key)
    {
      ++left;
    }
    a[hole] = a[left];
    hole = left;
  }
  a[hole] = key;
  keyi = hole;
  //此时区间被分割为[begin,keyi-1] keyi [keyi+1,end]
  //注意传递的是begin,不是0,中间递归时不一定是从0开始的区间，0是一个常量，begin是一个变量。
  QuickSort(a, begin, keyi - 1);
  QuickSort(a, keyi + 1, end);
}

//快速排序  前后指针法
void QuickSort(int* a, int begin, int end)
{
  //当区间只有一个值时，或区间不存在时退出递归
  if (begin >= end)
  {
    return;
  }
  int prev = begin , cur = begin + 1;
  int keyi = begin;
  while (prev <= cur && cur <= end)
  {
    if (a[cur] < a[keyi] && ++prev != cur)
    {
      Swap(&a[prev], &a[cur]);
    }
    ++cur;
  }
  Swap(&a[keyi], &a[prev]);
  keyi = prev;
  //此时区间被分割为[begin,keyi-1] keyi [keyi+1,end]
  //注意传递的是begin,不是0,中间递归时不一定是从0开始的区间，0是一个常量，begin是一个变量。
  QuickSort(a, begin, keyi - 1);
  QuickSort(a, keyi + 1, end);
}

//单趟排序
int Partion3(int* a ,int begin ,int end)
{
  int prev = begin , cur = begin + 1;
  int keyi = begin;
  while (prev <= cur && cur <= end)
  {
    if (a[cur] < a[keyi] && ++prev != cur)
    {
      Swap(&a[prev], &a[cur]);
    }
    ++cur;
  }
  Swap(&a[keyi], &a[prev]);
  keyi = prev;
  return keyi;
}
//快速排序的非递归实现
void QuickSortNonR(int* a ,int begin ,int end)
{
  Stack st;
  StackInit(&st);
  StackPush(&st, begin);
  StackPush(&st, end);
  while (!StackEmpty(&st))
  {
    int right = StackTop(&st);
    StackPop(&st);
    int left = StackTop(&st);
    StackPop(&st);
    //一趟排序
    int keyi = Partion3(a, left, right);
    //此时区间被划分为[left,keyi-1]keyi[keyi+1,right]
    if (keyi + 1 < right)
    {
      StackPush(&st, keyi + 1);
      StackPush(&st, right);
    }
    if (left < keyi - 1)
    {
      StackPush(&st, left);
      StackPush(&st, keyi - 1);
    }
  }
  StackDestroy(&st);
}