一、排序的概念

1.1排序的概念

排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。

稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j] ，且 r[i] 在 r[j] 之前，而在排序后的序列中， r[i] 仍在 r[j] 之前，则称这种排序算法是稳定的；否则称为不稳定的。

内部排序：数据元素全部放在内存中的排序。

外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。

1.2排序运用

1.3排序算法

二、插入排序

基本思想：直接插入排序是一种简单的插入排序法，其基本思想是：把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列。

实际中我们玩扑克牌时，就用了插入排序的思想：

2.1直接插入排序

当插入第 i(i>=1) 个元素时，前面的 array[0],array[1],…,array[i-1] 已经排好序，此时用 array[i] 的排序码与array[i-1],array[i-2],…的排序码顺序进行比较，找到插入位置即将 array[i] 插入，原来位置上的元素顺序后移。

直接插入排序就是把从第二个数开始的数当作外来的数据往数组里插入数据，我们把要插入的数先存下来，然后把它之前的每个数和它比较，如果比它大，就往后移动，如果它之前的数等于或小于它，就停止，然后插入。

void InsertSort(int* a, int n)
{
  for (int i = 0; i < n - 1; i++)
  {
  int end = i;
  int tmp = a[end + 1];//要插入的数
  while (end >= 0)
  {
    if (a[end] > tmp)
    {
    a[end + 1] = a[end];
    end--;
    }
    else
    break;
  }
  a[end + 1] = tmp;
  }
}

直接插入排序的特性总结：

1、元素集合越接近有序，直接插入排序算法的时间效率越高。(因为它需要移动的次数少了)

2、时间复杂度：O(N^2)

3、空间复杂度：O(1)，它是一种稳定的排序算法。

4、稳定性：稳定。

2.2希尔排序(缩小增量排序)

希尔排序法又称缩小增量法。希尔排序法的基本思想是：希尔排序通过比较相距一定间隔的元素来进行，各趟比较所用的距离随着算法的进行而减小，直到只比较相邻元素的最后一趟排序为止。

希尔排序是对直接插入排序的优化，它的操作很简单，就是：

1、预排序

2、直接插入排序

预排序：选定一个gap值，将间隔为gap的数据分为一组，每一组进行插入排序。

例如：

像这样，选定的gap是3，对gap组数据进行插入排序，插入排序后的结果是：

进行预排序之后，再对它进行插入排序，因为已经优化了不少，它的时间复杂度会降低很多。

同时，我们通过这样还发现一个规律：

gap越大，大的数据可以越快跳到后面，小的数据可以越快跳到前面，但是，不是很接近有序，当gap越小，跳得越慢，越接近有序。当gap=1时，他就是单纯的直接插入排序，当然这个直接插入排序已经被优化了很多，于是，我们能否进一步优化希尔排序呢？我们可以设定一个gap，让这个gap从大到小，一直到gap=1，这时通过不断优化，它的时间复杂度被降到最低。

void ShellSort(int* a, int n)
{
  int gap = n;
  while (gap >1)
  {
  gap = gap / 2;
  //插排
  for (int i = 0; i < gap; i++)//gap组
  {
    for (int j = i; j < n - gap; j += gap)
    {
    //第一个和后一个比较
    int end = j;
    int tmp = a[end + gap];
    while (end >= 0)
    {
      if (a[end] > tmp)
      {
      a[end + gap] = a[end];
      end -= gap;
      }
      else
      break;
    }
    a[end + gap] = tmp;
    }
  }
  }
}

希尔排序的特性总结：

1. 希尔排序是对直接插入排序的优化。

2. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样再进行插入排序就会很快。

3. 希尔排序的时间复杂度不好计算，我们知道时间复杂度一般都是选择实际会出现的最坏情况去计算，但是希尔排序实际不会出现最坏情况，它是一个不断优化的过程，无法实际求出，所以根据大量数据得出，推导出来平均时间复杂度： O(N^1.3—N^2）

4. 稳定性：不稳定

5.希尔排序的空间复杂度是0(1).

三、选择排序

基本思想：每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。

3.1直接选择排序

在元素集合 array[i]--array[n-1] 中选择关键码最大 ( 小 )的数据元素，若它不是这组元素中的最后一个 ( 第一个 ) 元素，则将它与这组元素中的最后一个（第一个）元素交换，在剩余的array[i]--array[n-2] （ array[i+1]--array[n-1] ）集合中，重复上述步骤，直到集合剩余 1 个元素。

像图示这样的仅去找最大的倒着排，或者找最小的正着排，未免效率太过低效。

尽管选择排序自身确实比较拉跨，但是我们还是稍作优化，设立两个指针，分别从两头开始，遍历找最小的和最大的，然后最小的和首位交换，最大的和最后一个交换。这样一次遍历可以分别找出这次遍历最大的数和最小的数。

void SelectSort(int* a, int n)
{
  int begin = 0, end = n - 1;
  while (begin < end)
  {
  int maxi = end, mini = begin;
  int i = 0;
  for (i = begin; i <= end; i++)
  {
    if (a[i] > a[maxi])
    maxi = i;
    if (a[i] < a[mini])
    mini = i;
  }
  Swap(&a[begin], &a[mini]);
  //修正
  if (maxi == begin)
    maxi = mini;
  Swap(&a[end], &a[maxi]);
  --end;
  ++begin;
  }
}

注意，这里对maxi的修正，他这里主要是考虑到一些特殊情况，比如：

像这种情况，如果不进行修正，那么我们可以运行一下代码，会生成什么，首位begin和mini交换，然后maxi所指向的数是多少？是最小的数，很显然会产生错误。所以我们要进行修正。

那么，还有一个问题，为什么只对maxi进行修正？mini不需要进行修正吗？修正和我们先交换谁有关，如果我们先交换maxi和end所指向的，那么mini就需要修正。

void SelectSort(int* a, int n)
{
  int begin = 0, end = n - 1;
  while (begin < end)
  {
  int maxi = end, mini = begin;
  for (int i = begin; i <=end; i++)
  {
    if (a[i] > a[maxi])
    maxi = i;
    if (a[i] < a[mini])
    mini = i;
  }
  //修正和你选择交换的顺序有关
  //如果选择先交换最大的和最后一个
  Swap(&a[end], &a[maxi]);
  if (mini == end)
    mini = maxi;
  Swap(&a[begin], &a[mini]);
  ++begin;
  --end;
  }
}

这个修正，主要是为了解决 mini在 end的情况。

直接选择排序的特性总结：

1. 直接选择排序思考非常好理解，但是效率不是很好，实际中很少使用。

2. 时间复杂度： O(N^2)。

3. 空间复杂度： O(1)。

4. 稳定性：不稳定。

5. 直接选择排序需要注意修正的问题。

3.2堆排序

堆排序是基于堆可以快速选出最大或最小的数以及它的双亲与子独特的关系而设计的一种排序。它是选择排序的一种。

1、动图演示

2、实现思路

之前博主在撰写介绍数据结构--堆这一章时，介绍过向上调整建堆和向下调整建堆这两种建堆方式，我们选择了向下调整建堆的方式，因为它时间复杂度更低。我们要利用它可以快速选出最大或最小的特点来排序。排升序建大堆，排降序则建小堆。

可能有的读者不太明白，排升降序和建大小堆的关系。博主就再啰嗦一下，以排升序建大堆为例。

我们的思路是：先把数组中的元素建成大堆，然后再把第一个数也就是根，和最后一个数交换，然后对第一个数进行向下调整建堆(但是最后一个数不参与建堆)，这时候最大的数就已经选出来排在末尾，而第一个数的左右子树满足向下调整的要求，然后重复对剩下的数选出次大的，排到倒数第二个，依次选数倒着排。

void Swap(int* a, int* b)
{
  int tmp = *a;
  *a = *b;
  *b = tmp;
}
void AdjustDown(int* a, int parent, int n)
{
  int maxchild = parent * 2 + 1;
  while (maxchild < n)
  {
  if (maxchild + 1 < n && a[maxchild + 1] > a[maxchild])
  {
    maxchild++;
  }
  if (a[maxchild] > a[parent])
  {
    Swap(&a[maxchild], &a[parent]);
    parent = maxchild;
    maxchild = parent * 2 + 1;
  }
  else
    break;
  }
}
void HeapSort(int* a, int n)
{
  //建堆
  for (int i = (n - 2) / 2; i >= 0; --i)
  {
  AdjustDown(a, i, n);
  }
  //排序
  for (int j = 1; j < n; j++)
  {
  Swap(&a[0], &a[n - j]);
  AdjustDown(a, 0, n - j);
  }
}
void PrintArray(int* a, int n)
{
  for (int i = 0; i < n; ++i)
  {
  printf("%d ", a[i]);
  }
  printf("\n");
}
int main()
{
  int a[] = { 22,13,35,31,20,46,60,30,91,81,96 };
  int n = sizeof(a) / sizeof(int);
  HeapSort(a, n);
  PrintArray(a, n);
  return 0;
}

3.复杂度

堆排序的时间复杂度是0(N*logN)，堆排序没有占用额外的空间，因此空间复杂度是O(1)。

四、交换排序

基本思想：所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。

4.1冒泡排序

冒泡排序比较简单，它是典型的交换排序。

void BubbleSort(int* a, int n)
{
  for (int i = 0; i < n-1; ++i)//这里注意不是i<n
  {
  int flag = 1;
  for (int j = 0; j < n - i-1; ++j)
  {
    if (a[j] > a[j + 1])
    {
    Swap(&a[j], &a[j + 1]);
    flag = 0;
    }
  }
  if (flag == 1)
    break;
  }
}

冒泡排序的特性总结：

1. 冒泡排序是一种非常容易理解的排序

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

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

4. 稳定性：稳定

4.2快速排序

快速排序是 Hoare 于 1962 年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

将区间按照基准值划分为左右两半部分的常见方式有：

1. hoare版本

2. 挖坑法

3. 前后指针版本

1.hoare版本

①快速排序未优化版

单趟排序：

1、选一个key。(一般是第一个或者是最后一个)。

2、单趟排序，要求小的在key的左边，大的在key的右边

int PartSort1(int* a, int left, int right)
{
  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 = PartSort1(a, left, right);
  QuickSort(a, left, meeti-1);
  QuickSort(a, meeti + 1, right);
}

这是用递归实现的快排，这里我想说明两个问题。

1、keyi的选取和left和right哪个先走有什么联系？

2、未优化的快排有什么缺陷？

先来说明第一个问题：

这段代码keyi选取的是第一个数的下标，即left。通过图解可以说明一些问题：

如果L先走，我们很明显就会发现最后keyi左侧的不是都小于keyi所指向的那个数。

所以，这里博主直接给出结论：

如果左边第一个作为keyi，一定要R先走

如果右边第一个作为keyi，一定有L先走

未优化的快排有什么缺陷呢？

我们所写的快排是基于递归实现的，而且我们每次都选取都是最左侧的数来作为keyi，如果是排无序的数没什么问题，如果是排较为有序的一组数呢？

博主设计让直接插入排序和堆排排同样一组数据，然后让快排去排堆排排过的数据，看看耗费时间。

int main()
{   
    srand(time(0));
  const int N = 2000;
  int* a1 = (int*)malloc(sizeof(int) * N);
  int* a4 = (int*)malloc(sizeof(int) * N);
  for (int i = 0; i < N; ++i)
  {
  a1[i] = rand();
  a4[i] = a1[i];
  }
  int begin1 = clock();
  InsertSort(a1, N);
  int end1 = clock();
  int begin4 = clock();
  HeapSort(a4, N);
  int end4 = clock();
  int begin5 = clock();
  QuickSort(a4, 0, N - 1);//有序进行快排，栈溢出
  int end5 = clock();
  printf("InsertSort:%d\n", end1 - begin1);
  printf("HeapSort:%d\n", end4 - begin4);
  printf("QuickSort:%d\n", end5 - begin5);
  free(a1);
  free(a4);
    return 0;
}

我们惊奇地发现，未优化的快排对一组有序的数据排序耗费的时间，竟要超过插入排序。这是为什么呢？我们把我们所写的快排的递归本质来分析一下：

当我们排有序的数的时候，它的递归深度是非常深的，这会调用大量堆栈，甚至程序崩溃，而它的复杂度也接近0(N^2)。这样看来我们需要对它的选数进行调整。

排序总结(difficult but Liver)（上）