②快速排序三数取中版

我们选数要选一个合适的数，不能过大也不能过小，大小适中最为适合，于是我们提出了三数取中，即：取第一个数，最后一个数以及中间的数三个数比较，取中位数。

int GetMidIndex(int* a, int begin, int end)
{
  int mid = begin + (end - begin) / 2;
  if (a[begin] < a[mid])
  {
  if (a[mid] < a[end])
    return mid;
  else//a[mid]>=a[end]
  {
    return a[end] > a[mid] ? end : mid;
  }
  }
  else//(a[begin]>=a[mid])
  {
  if (a[mid] > a[end])
    return mid;
  else//a[mid]<=a[end]
    return a[begin] > a[end] ? end : begin;
  }
}
int PartSort2(int* a, int left, int right)
{
  int mid = GetMidIndex(a,left,right);
  Swap(&a[left], &a[mid]);
  int keyi = left;
  while (left < right)
  {
  //因为选取在左侧，所以要right先走
  while (left < right && a[right] >= a[keyi])//右选小
  {
    right--;
  }
  while (left < right && a[left] <= a[keyi])//左选大
  {
    left++;
  }
  //选到左大，右小，进行交换
  if (left < right)
    Swap(&a[left], &a[right]);
  }
  int meeti = left;
  Swap(&a[keyi], &a[meeti]);
  return meeti;
}
void QuickSort(int* a, int left, int right)
{
  if (left >= right)
  return;
  int meeti = PartSort2(a, left, right);
  QuickSort(a, left, meeti-1);
  QuickSort(a, meeti + 1, right);
}

三数取中有个细节需要提醒一下，如果找到中位数，不是把这个中位数的下标作为keyi，而是把这个数和最左侧的数进行交换，还是以left作为keyi。

我们再来看一下三数取中模式递归调用堆栈的情况。

我们看到三数取中已经很不错了，但是它最后三层调用了80%的堆栈，如果这样的快排去排更多的数据，很可能会栈溢出，为了避免，我们可以进一步优化，把最后接近有序的数据用插排来排，这样会快上不少，也能避免栈溢出。

void QuickSort(int* a, int left, int right)
{
  if (left >= right)
  return;
  if (right - left <= 8)
  {
  InsertSort(a + left, right - left + 1);
  }
  else
  {
  int meeti = PartSort2(a, left, right);
  QuickSort(a, left, meeti - 1);
  QuickSort(a, meeti + 1, right);
  }
}

2.挖坑法

挖坑法是快排的另一种玩法，效率和hoare版本的差不多，也是用到了三数取中。

//挖坑法
int PartSort3(int* a, int left, int right)
{
  int mid = GetMidIndex(a, left, right);
  Swap(&a[left], &a[mid]);
  int key = a[left];//存下来
  int hole = left;
  while (left < right)
  {
  //因为选取在左侧，所以要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;
  //选到左大，右小，进行交换
  if (left < right)
    Swap(&a[left], &a[right]);
  }
  a[hole] = key;
  return hole;
}

3.前后指针版

int PartSort4(int* a, int left, int right)
{
  int mid = GetMidIndex(a, left, right);
  Swap(&a[left], &a[mid]);
  int keyi = left;
  int prev = left;
  int cur = left+1;
  while (cur <= right)
  {
  if (a[cur] < a[keyi] && ++prev != cur)
    Swap(&a[cur], &a[prev]);
  ++cur;
  }
  Swap(&a[keyi], &a[prev]);
  return prev;
}

4.非递归实现快排

有些公司在面试的时候曾经提出这个问题，当然对于没有接触过的，当时可能就懵了。

我们来分析一下递归的时候，栈做了什么：

递归版本我们借助栈做了什么？不就是对这组数据不断细分然后进行三数取中再排，之前我们压栈放的这些分组，借助我们自己实现的栈去放也是一样的道理。

只不过我们需要先调用栈：

#include"Stack.h"
#pragma once
#include<stdio.h>
#include<stdbool.h>
#include<assert.h>
#include<stdlib.h>
typedef int STDataType;
typedef struct Stack
{
  STDataType* a;
  int top;
  int capacity;
}ST;
void StackInit(ST* ps);
void StackDestory(ST* ps);
void StackPush(ST* ps,STDataType x);
void StackPop(ST* ps);
STDataType StackTop(ST* ps);
bool StackEmpty(ST* ps);
int StackSize(ST* ps);
void StackInit(ST* ps)
{
  assert(ps);
  ps->a = NULL;
  ps->top = 0;
  ps->capacity = 0;
}
void StackDestory(ST* ps)
{
  assert(ps);
  free(ps->a);
  ps->a = NULL;
  ps->top = ps->capacity = 0;
}
void StackCheckCapacity(ST* ps)
{
  assert(ps);
  if (ps->top == ps->capacity)
  {
  int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
  STDataType* newStack = (STDataType*)realloc(ps->a, sizeof(STDataType) * newcapacity);
  if (newStack == NULL)
  {
    perror("realloc fail");
    exit(-1);
  }
  else
  {
    ps->a = newStack;
    ps->capacity = newcapacity;
  }
  }
}
void StackPush(ST* ps, STDataType x)
{
  assert(ps);
  StackCheckCapacity(ps);
  ps->a[ps->top] = x;
  ++ps->top;
}
bool StackEmpty(ST* ps)
{
  assert(ps);
  return ps->top == 0;
}
void StackPop(ST* ps)
{
  assert(ps);
  assert(!StackEmpty(ps));
  --ps->top;
}
STDataType StackTop(ST* ps)
{
  assert(ps);
  return ps->a[ps->top - 1];
}
int StackSize(ST* ps)
{
  assert(ps);
  return ps->top;
}
void QuickSortNonr(int* a, int left, int right)
{
  ST st;
  StackInit(&st);
  StackPush(&st, left);
  StackPush(&st, right);
  while (!StackEmpty(&st))
  {
  int right = StackTop(&st);
  StackPop(&st);
  int left = StackTop(&st);
  StackPop(&st);
  int keyi=PartSort4(a, left, right);
  if (keyi + 1 < right)
  {
    StackPush(&st, keyi+1);
    StackPush(&st, right);
  }
  if (left < keyi - 1)
  {
    StackPush(&st, left);
    StackPush(&st, keyi - 1);
  }
  }
  StackDestory(&st);
}

快速排序特性总结：

1. 快速排序整体的综合性能和使用场景都是比较好的。

2. 时间复杂度：O(N*logN)

3. 空间复杂度：O(logN).

4. 稳定性：不稳定.

五、归并排序

基本思想：

归并排序（ MERGE-SORT ）是建立在归并操作上的一种有效的排序算法 , 该算法是采用分治法（ Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

5.1递归版归并排序

我们观察归并排序的过程，就会发现，它本质是不断细分，(不断递归)，直到只剩两个数，然后借助第三空间，取小尾插，再返回上一级，层层递进，最后再把第三空间排号的数拷贝到原数组中，这时候就完成了归并的过程。

//归并排序
void _MergeSort(int* a, int begin, int end, int* tmp)
{
  if (begin >= end)
  return;
  int mid = begin + (end - begin) / 2;
  _MergeSort(a, begin, mid, tmp);
  _MergeSort(a, mid + 1, end, tmp);
  int begin1 = begin, end1 = mid;
  int begin2 = mid + 1, end2 = end;
  int i = begin;
  while (begin1 <= end1 && begin2 <= end2)
  {
  if (a[begin1] <= a[begin2])
    tmp[i++] = a[begin1++];
  else
    tmp[i++] = a[begin2++];
  }
  while (begin1 <= end1)
  {
  tmp[i++] = a[begin1++];
  }
  while (begin2 <= end2)
  {
  tmp[i++] = a[begin2++];
  }
  memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));
}
void MergeSort(int* a, int n)
{
  int* tmp = (int*)malloc(sizeof(int) * n);
  if (tmp == NULL)
  {
  perror("malloc fail");
  return;
  }
  _MergeSort(a, 0, n - 1, tmp);
  free(tmp);
  tmp = NULL;
}

5.2非递归版归并排序

非递归版要比递归版本考虑更多情形，我们知道递归版本是递归到2个数据归并，然后返回，变为4个数据归并，不断返回。如果，我们刚开始就把数组里的数据从2个开始归并，然后开始不断扩大区间。

因为数据的个数不一定是整数倍，但是我们计算是按照整数倍来计算的，存在越界的情况，因此我们要修正一些场景。

我们要想明白归并排序是两组数据归并之后进行比较，取小的尾插，因此必须要有两组数据进行比较，我们分析越界情况有如下几种：

1.第一组end1越界。这种情况就没有了第二组，因此直接break，让它在其他gap值重新分组归并。

2.第二组全部越界。这种也是只有第一组

3.第二组越界部分越界。这种情况需要修正边界，修正第二组的right为数组末尾。可以比较。

void MergeSortNonR(int* a,int n)
{
  int* tmp = (int*)malloc(sizeof(int) * n);
  if (tmp == NULL)
  {
  perror("malloc fail");
  return;
  }
  int gap = 1;
  while (gap < n)
  {
  //gap个数据归并
  for (int j = 0; j < n; j +=2* gap)//因为是两组数据
  {
    int begin1 = j, end1 = j + gap - 1;
    int begin2 = j + gap, end2 = j + gap * 2 - 1;
    //第一组部分越界
    if (end1 >= n)
    {
    break;
    }
    //第二组全部越界
    if (begin2 >= n)
    {
    break;
    }
    //第二组部分越界
    if (end2 >= n)
    {
    end2 = n - 1;
    }
    int i = j;
    while (begin1 <= end1 && begin2 <= end2)
    {
    if (a[begin1] <= a[begin2])
    {
      tmp[i++] = a[begin1++];
    }
    else
    {
      tmp[i++] = a[begin2++];
    }
    }
    while (begin1 <= end1)
    {
    tmp[i++] = a[begin1++];
    }
    while (begin2 <= end2)
    {
    tmp[i++] = a[begin2++];
    }
    memcpy(a + j, tmp + j, (end2 - j + 1) * sizeof(int));
  }
  gap *= 2;
  }
  free(tmp);
  tmp = NULL;
}

归并排序的特性总结：

1. 归并的缺点在于需要 O(N) 的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。

2. 时间复杂度： O(N*logN)

3. 空间复杂度： O(N)

4. 稳定性：稳定

六、非比较排序(计数排序)

思想：计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。操作步骤：

1. 统计相同元素出现次数。

2. 根据统计的结果将序列回收到原来的序列中。

计数排序的思想很有趣，统计数组中每个数出现的次数存到另一个数组中，另一个数组的下标加上最小的值就是要排序数组里的元素，而这些下标对应的值就是它出现的次数。

void CountSort(int* a, int n)
{
  int max = a[0], min = a[0];
  for (int i = 1; i < n; ++i)
  {
  if (a[i] > max)
    max = a[i];
  if (a[i] < min)
    min = a[i];
  }
  int range = max - min+1;//这是范围
  int* countA = (int*)malloc(sizeof(int) * range);
  if (countA == NULL)
  {
  perror("malloc fail");
  return;
  }
  memset(countA, 0, sizeof(int) * range);
  for (int i = 0; i < n; ++i)
  {
  countA[a[i] - min]++;
  }
  int j = 0;
  for (int i = 0; i < range; ++i)
  {
  while (countA[i]--)
  {
    a[j]=i+min;
    ++j;
  }
  }
  free(countA);
}