探索数据结构：初入算法之经典排序算法-阿里云开发者社区

一、插入排序

步骤：

从第一个元素开始，该元素可以认为已经被排序
取下一个元素tem，从已排序的元素序列从后往前扫描
如果该元素大于tem，则将该元素移到下一位
重复步骤3，直到找到已排序元素中小于等于tem的元素
tem插入到该元素的后面，如果已排序所有元素都大于tem，则将tem插入到下标为0的位置
重复步骤2~5

动态展示过程如下：

思路：

在待排序的元素中，假设前n-1个元素已有序，现将第n个元素插入到前面已经排好的序列中，使得前n个元素有序。按照此法对所有元素进行插入，直到整个序列有序。

但我们并不能确定待排元素中究竟哪一部分是有序的，所以我们一开始只能认为第一个元素是有序的，依次将其后面的元素插入到这个有序序列中来，直到整个序列有序为止。

代码实现如下：

void InsertSort(int* a, int n)
{
  for (int i = 0; i < n - 1; i++)
  {
    int end = i;
    //数组在[0, end]是有序的
    while (end >= 0)
    {
      if (a[end + 1] < a[end])//升序
      {
        Swap(&a[end], &a[end + 1]);
        end--;
      }
      else
        break;
    }
  }
}

时间复杂度：最坏情况下为O(N*N)，此时待排序列为逆序，或者说接近逆序
最好情况下为O(N)，此时待排序列为升序，或者说接近升序。
空间复杂度：O(1)

二、希尔排序

步骤：

先选定一个小于N的整数gap作为分组数量，然后将所有距离为gap的元素分在同一组，并对每一组的元素进行直接插入排序。然后再取一个比第一增量小的整数作为第二增量，重复上述操作…一般我们选择每次分组数量为上次的1/3。
当分组的数量（gap）减到1时，就相当于整个序列被分到一组，进行一次直接插入排序，排序完成。

动态展示过程如下：

分解战术如下（颜色相同为一组）：

思路：希尔排序，先将待排序列进行预排序，使待排序列接近有序，然后再对该序列进行一次插入排序，此时插入排序的时间复杂度为O(N)，

代码实现如下：

void ShellSort(int* a, int n)
{
  int gap = n;
  while (gap > 1)
  {
    gap = gap / 3 + 1;//最后一次为1（大于1时为预排序，等于1为插入排序）
    for (int i = 0; i < n - gap; i++)//插入排序变式（分成gap组，每组插入排序)
    {
      int end = i;
      while (end >= 0)
      {
        if (a[end + gap] < a[end])//升序
        {
          Swap(&a[end], &a[end + gap]);
          end -= gap;
        }
        else
          break;
      }
    }
  }
}

时间复杂度平均：O(N^1.3)

空间复杂度：O(1)

三、选择排序

思路：

每次从待排序列中选出一个最小值，然后放在序列的起始位置，直到全部待排数据排完即可。

实际上，我们可以一趟选出两个值，一个最大值一个最小值，然后将其放在序列开头和末尾，这样可以使选择排序的效率快一倍。

动态展示过程如下：

代码实现如下：

void SelectSort(int* a, int n)
{
  int begin = 0, end = n - 1;
  while (begin < end)
  {
    int min = begin, max = end;
    for (int i = begin; i < end; i++)
    {
      if (a[i] < a[min])
        min = i;
      if (a[i] > a[max])
        max = i;
    }
 
    if (min == end)
    {
      Swap(&a[begin], &a[min]);
      Swap(&a[end], &a[max]);
    }
    else
    {
      Swap(&a[end], &a[max]);
      Swap(&a[begin], &a[min]);
    }
    begin++, end--;
  }
}

时间复杂度：最坏情况：O(N^2)
最好情况：O(N^2)
空间复杂度：O(1)

四、堆排序

在前面的堆与二叉树章节讲过，在此就不再赘述。

void AdjustDown(int* a, int n, int root)
{
  int child = root * 2 + 1;
  while (child < n)
  {
    if (child + 1 < n && a[child] < a[child + 1])//建大堆
    {
      child++;
    }
 
    if (a[root] < a[child])//建大堆
    {
      Swap(&a[child], &a[root]);
      root = child;
      child = root * 2 + 1;
    }
    else
    {
      break;
    }
  }
}
void HeapSort(int* a, int n)
{
  for (int i = ((n - 1) - 1) / 2; i >= 0; i--)
  {
    AdjustDown(a, n, i);
  }
 
  for (int i = 1; i < n; i++)
  {
    Swap(&a[0], &a[n - i]);
    AdjustDown(a, n - i, 0);
  }
}

五、冒泡排序

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

六、快速排序

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

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

6.1 hoare版本

思路：
选出一个key，一般是最左边或是最右边的。
定义一个begin和一个end，begin从左向右走，end从右向左走。（需要注意的是：若选择最左边的数据作为key，则需要end先走；若选择最右边的数据作为key，则需要bengin先走）。
在走的过程中，若end遇到小于key的数，则停下，begin开始走，直到begin遇到一个大于key的数时，将begin和right的内容交换，end再次开始走，如此进行下去，直到begin和end最终相遇，此时将相遇点的内容与key交换即可。（选取最左边的值作为key）
此时key的左边都是小于key的数，key的右边都是大于key的数
将key的左序列和右序列再次进行这种单趟排序，如此反复操作下去，直到左右序列只有一个数据，或是左右序列不存在时，便停止操作，此时此部分已有序。

单趟动图展示如下：

【补】快速排序的优化：

法1：三数取中法选基准值key（三数取中）

法2：递归到小的子区间时，可以考虑使用插入排序（小区间优化）

三数取中代码：

int GetMid(int* a, int left, int right)
{
  int midi = (left + right) / 2;
  if (a[left] < a[midi])
  {
    if (a[midi] < a[right])
      return midi;
    else if (a[left] < a[right])//midi最大，二人取大为中
      return right;
    else
      return left;
  }
  else  //a[left] > a[midi]
  {
    if (a[midi] > a[right])
      return midi;
    else if (a[left] < a[right])//midi最小，二人取小为中
      return left;
    else
      return right;
  }
}

小区间优化代码：

void InsertSort(int* a, int n)
{
  for (int i = 0; i < n - 1; i++)
  {
    int end = i;
    //数组在[0, end]是有序的
    while (end >= 0)
    {
      if (a[end + 1] < a[end])//升序
      {
        Swap(&a[end], &a[end + 1]);
        end--;
      }
      else
        break;
    }
  }
}

【ps】左边作key，right先走，相遇位置的值一定比基准值小，或相遇位置就是key的位置

Q：为什么相遇位置的值一定比基准值小，或者相遇位置就是key？

A：第一种情况：R找到小，但L找大没找到，这时L会遇到R；第二种情况：R找小没找到，直接遇到L，此时要么是一个比key小的位置，要么直接到key。类似地，若右端作key，则让L先走，相遇位置值就比key大。

代码示例如下：

int PartSort1(int* a, int left, int right)
{
  //三数取中
  int midi = GetMid(a, left, right);
  Swap(&a[midi], &a[left]);
 
  int begin = left, end = right;
  int key = left;
  while (begin < end)
  {
    while (begin < end && a[end] >= a[key])
      end--;
    
    while (begin < end && a[begin] <= a[key])
      begin++;
 
    Swap(&a[begin], &a[end]);
  }
  Swap(&a[key], &a[begin]);
  return begin;
}

6.2 挖坑法

挖坑法是后人基于Hoare版本实现的改进版。

拿走key的值，留下一个坑位。right下标指针找小，找到后将值填到该坑位上，并留下一个新坑位；left下标指针找大，找到后将值填到新坑位上，且再留下一个坑，以此往复。

直到left与right相遇，就将key的值填到 left == right 的坑位。

代码示例如下：

int PartSort2(int* a, int left, int right)
{
  //三数取中
  int midi = GetMid(a, left, right);
  Swap(&a[midi], &a[left]);
 
  int begin = left, end = right;
  int key = a[left];
  int flag = left;
  while (begin < end)
  {
    while (begin < end && a[end] >= key)
      end--;
    a[flag] = a[end];
    flag = end;
 
    while (begin < end && a[begin] <= key)
      begin++;
    a[flag] = a[begin];
    flag = begin;
  }
  a[begin] = key;
 
  return begin;
}

6.3 前后指针法

对于前指针prev（左）、后指针cur（右）、基准值key（数组头部），若cur找到比key小的值，则++prev，cur与prev位置的值交换；若cur找到比key大的值，则++cur。相当于把比key大的值翻转到右边（大的值往右边运），比key小的值翻转到左边（把小的值往左边运）。

【ps】prev要么紧跟cur（即prev的下一个位置就是cur/prev紧跟在比key大的值后面），要么跟cur中间间隔着一段由比key大的值组成的区间。

代码示例如下：

int PartSort3(int* a, int left, int right)
{
  int prve = left, cur = left + 1;
  int key = a[left];
  while (cur <= right)
  {
    if (prve < cur && a[cur] <= key)
    {
      prve++;
      Swap(&a[prve], &a[cur]);
    }
    cur++;
  }
  Swap(&a[left], &a[prve]);
 
  return prve;
}
 
void QuickSort(int* a, int left, int right)
{
  if (left >= right)
    return;
 
  if (right - left + 1 < 10)
  {
    //小区间优化
    InsertSort(a + left, right - left + 1);
  }
  else
  {
    //int key = PartSort1(a, left, right);
    //int key = PartSort2(a, left, right);
    int key = PartSort3(a, left, right);
 
    QuickSort(a, key + 1, right);
    QuickSort(a, left, key - 1);
  }
}

6.4 非递归实现

用栈实现（关于栈的完整代码和更多解释，详见探索数据结构：栈的实现方法）。

先将所有数据组成的区间端点端点值入栈，然后，每次从栈里取一段区间的端点值（首次是所有数据组成的区间）进行单趟的排序；单趟排序中，被划分的子区间分别入栈（因为栈的特点是后进先出，所以右先入左后入才能使序列跟入栈前保持一致）；直到划分的子区间只有一个值或子区间不存在就不再入栈。

代码实现：

int PartSort(int* a, int left, int right)
{
  int midi = GetMid(a, left, right);
  if (midi != left)
    Swap(&a[midi], &a[left]);
 
  int prev = left, cur = left + 1;
  int keyi = left;
  while (cur <= right)
  {
    if (a[cur] < a[keyi] && ++prev != cur)
    {
      Swap(&a[prev], &a[cur]);
    }
 
    cur++;
  }
 
  Swap(&a[prev], &a[keyi]);
 
  keyi = prev;
  return keyi;
}
 
void QuickSortNonR(int* a, int left, int right)
{
  ST st;
  StackInit(&st);
  //先入右值（尾部的值），再入左值（头部的值）
  StackPush(&st, right);
  StackPush(&st, left);
 
  while (!StackEmpty(&st))
  {
    //先出左值，再出右值
    int begin = StackTop(&st);
    StackPop(&st);
    int end = StackTop(&st);
    StackPop(&st);
 
    //进行单趟的排序，且记录排序后的基准值下标
    int keyi = PartSort(a, begin, end);
 
    //分出区间：[begin,keyi-1] keyi [keyi+1, end]
    //并分别入栈
    if (keyi + 1 < end)    //先入右区间
    {
      StackPush(&st, end);    //先入右值
      StackPush(&st, keyi + 1); //再入左值
    }
    if (begin < keyi - 1)    //再入左区间
    {
      StackPush(&st, keyi - 1);    //先入右值
      StackPush(&st, begin);       //再入左值
    }
  }
 
  StackDestroy(&st);
}

七、归并排序

7.1 递归实现

归并排序算法有两个基本的操作，一个是分，也就是把原数组划分成两个子数组的过程。另一个是治，它将两个有序数组合并成一个更大的有序数组。

将待排序的线性表不断地切分成若干个子表，直到每个子表只包含一个元素，这时，可以认为只包含一个元素的子表是有序表。
将子表两两合并，每合并一次，就会产生一个新的且更长的有序表，重复这一步骤，直到最后只剩下一个子表，这个子表就是排好序的线性表。

可以看到这种结构很像一棵完全二叉树，本文的归并排序我们采用递归去实现（也可采用迭代的方式去实现）。

动画展示：

代码实现：

void _MergeSort(int* arr, int left, int right, int* temp)
{
  //分解：
  //分割数组只有一个元素时停止递归
  if (left >= right)
  {
    return;
  }
 
  int mid = (left + right) / 2;
 
  _MergeSort(arr, left, mid, temp);   //分割并排序数组左半边
  _MergeSort(arr, mid + 1, right, temp);  //分割并排序数组右半边
 
  //合并：
  int begin1 = left, end1 = mid;      //数组1的左右区间
  int begin2 = mid + 1, end2 = right;   //数组2的左右区间
  int i = begin1;
 
  //排序两个有序数组
  while (begin1 <= end1 && begin2 <= end2)
  {
    if (arr[begin1] <= arr[begin2])
    {
      temp[i] = arr[begin1];
      begin1++;
    }
    else
    {
      temp[i] = arr[begin2];
      begin2++;
    }
    i++;
  }
 
  while (begin1 <= end1)
  {
    temp[i] = arr[begin1];
    begin1++;
    i++;
  }
 
  while (begin2 <= end2)
  {
    temp[i] = arr[begin2];
    begin2++;
    i++;
  }
 
  //拷贝临时数组的内容到原数组（可以调用memcpy函数）
  //memcpy(arr+left, temp+left, (right-left+1)*sizeof(int));
  for (i = left; i <= right; i++)
  {
    arr[i] = temp[i];
  }
}
 
void MergeSort(int* arr, int size)
{
  int* temp = (int*)malloc(size * sizeof(int));
  if (temp == NULL)
  {
    perror("malloc fail\n");
    return;
  }
 
  _MergeSort(arr, 0, size - 1, temp); //归并排序的过程
 
  free(temp);
  temp = NULL;
}

7.2 非递归实现

7.2.1 思路实现

通过循环实现。将从同一组中分出的两个数据进行比较，按大小（升序）合并为一个有序区间。

将待排序的序列不断二分，直至二分的结果为单个数据，接着，将从同一组中分出的两个数据进行比较，按大小顺序一一归并为一个有序（升序）区间；归并后，重新排序，再对有序区间进行二二归并（每个有序区间有两个数据），然后是四四归并（每个有序区间有四个数据）......以此类推，直至待排序的序列整体有序。

而对于两个有序区间的归并，同样要开辟一个新的临时数组来存排好序的数据，最后，将排好序的序列整体拷贝回原数组。

971e64139e3f6ceb1be075e45d466893_ba8394b50890461c97ea3d4b0b986a23.png

7.2.2 数组边界问题

在归并排序的非递归实现中，我们要遍历数组，将两个长度为gap的数组排序合并，但是gap总是2的幂次方，这就导致数组长度不一定是 gap*2 的倍数，这就导致两个数组在遍历到数组边界时会导致越界问题。所以我们要对数组的边界问题进行处理

1. 第一个数组越界

黄色和蓝色数组是需要合并的两个数组，第一个数组指的是黄色数组，第二个数组指的是蓝色数组

此时遍历到数组末尾时，第一个数组只有一个元素，但是需要合并的数组长度是2，所以第一个数组访问时会造成越界（第二个数组自然也越界）

2. 第二个数组全部越界

此时遍历到数组末尾时，第一个数组的长度刚好到原数组的末尾，第二个数组不存在，访问第二个数组是会越界

3. 第二个数组部分越界

此时第一个数组在数组内，第二个数组只有一部分在数组内，第二个数组存在但是长度没有gap，访问第二个数组时会越界

解决方法：

我们来解决这些数组越界问题的方法是调整数组区间范围：

第一个数组越界时，第二个数组不存在，所以不用合并，第一个数组本身就是有序数组

第二个数组完全越界时，第二个数组依然不存在，所以不用合并

第三个数部分组越界时，第二个数组存在但是不完整，此时我们将第二个数组的结束位置调整为原数组末尾位置即可，让第一个数组和第二个数组合并。

代码示例：

void MergeSortNonR(int* a, int n)
{
  int* tmp = (int*)malloc(sizeof(int) * n);
  if (tmp == NULL)
  {
    perror("malloc fail\n");
    return;
  }
 
  //（单趟）一一归并
  int gap = 1;//每组归并的数据个数
  while (gap < n)
  {
    for (int i = 0; i < n; i += 2 * gap)
    {
      // [begin1,end1][begin2, end2]
      int begin1 = i, end1 = i + gap - 1;
      int begin2 = i + gap, end2 = i + 2 * gap - 1;
 
      //修正边界
      //归并一部分，拷贝一部分
      if (end1 >= n || begin2 >= n)
      {       
        break;//第一个区间或第二个区间越界就不拷贝
      }
      if (end2 >= n)
      {       
        end2 = n - 1;//第二个区间越界就修正区间边界end2
      }
 
      //依次比较两个区间相同下标位置的值，并按序放入临时数组
      int j = i;
      while (begin1 <= end1 && begin2 <= end2)
      {
        if (a[begin1] < a[begin2])
        {
          tmp[j] = a[begin1];
          j++, begin1++;
        }
        else
        {
          tmp[j] = a[begin2];
          j++, begin2++;
        }
      }
 
      //没走完的区间继续归并
      while (begin1 <= end1)
      {
        tmp[j] = a[begin1];
        j++, begin1++;
      }
      while (begin2 <= end2)
      {
        tmp[j] = a[begin2];
        j++, begin2++;
      }
 
      //归并一部分，拷贝一部分
      memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));
    }
    //一一归并 => 二二归并 => 四四归并 => ...
    gap *= 2;
  }
  free(tmp);
}

八、计数排序

计数排序的作用是，按照大小顺序排列每个数据，并保留每个数据重复出现的次数。它又称为鸽巢原理，是对哈希直接定址法的变形应用。实现它的基本步骤为：1. 统计相同元素出现次数；2. 根据统计的结果将序列回收到原来的序列中。

详解算法：

先假设 20 个数列为：{9, 3, 5, 4, 9, 1, 2, 7, 8，1，3, 6, 5, 3, 4, 0, 10, 9, 7, 9}。

让我们先遍历这个无序的随机数组，找出最大值为 10 和最小值为 0。这样我们对应的计数范围将是 0 ~ 10。然后每一个整数按照其值对号入座，对应数组下标的元素进行加1操作。

比如第一个整数是 9，那么数组下标为 9 的元素加 1，如下图所示。

第二个整数是 3，那么数组下标为 3 的元素加 1，如下图所示。

继续遍历数列并修改数组......。最终，数列遍历完毕时，数组的状态如下图。

数组中的每一个值，代表了数列中对应整数的出现次数。

有了这个统计结果，排序就很简单了，直接遍历数组，输出数组元素的下标值，元素的值是几，就输出几次。比如统计结果中的 1 为 2，就是数列中有 2 个 1 的意思。这样我们就得到最终排序好的结果。

0, 1, 1, 2, 3, 3, 3, 4, 4, 5, 5, 6, 7, 7, 8, 9, 9, 9, 9, 10

动画展示：

贴别说明：

虽然计数排序看上去很强大，但是它存在两大局限性：

1.当数列最大最小值差距过大时，并不适用于计数排序

比如给定 20 个随机整数，范围在 0 到 1 亿之间，此时如果使用计数排序的话，就需要创建长度为 1 亿的数组，不但严重浪费了空间，而且时间复杂度也随之升高。

2.当数列元素不是整数时，并不适用于计数排序

如果数列中的元素都是小数，比如 3.1415，或是 0.00000001 这样子，则无法创建对应的统计数组，这样显然无法进行计数排序。

正是由于这两大局限性，才使得计数排序不像快速排序、归并排序那样被人们广泛适用。

代码示例：

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;    //countA[i]记录了某一数据出现的次数，countA[i]出现几次，就往原数组中写几个对应的值
            //i + min相当于还原出原数据
    }
  }
 
  free(countA);
}

探索数据结构：初入算法之经典排序算法

一、插入排序

二、希尔排序

三、选择排序

四、堆排序

五、冒泡排序

六、快速排序

6.1 hoare版本

6.2 挖坑法

6.3 前后指针法

6.4 非递归实现

七、归并排序

7.1 递归实现

7.2 非递归实现

7.2.1 思路实现

7.2.2 数组边界问题

八、计数排序

【Tips】排序算法的复杂度&稳定性

热门文章

最新文章

相关课程

相关电子书

相关实验场景

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

探索数据结构：初入算法之经典排序算法

一、插入排序

二、希尔排序

三、选择排序

四、堆排序

五、冒泡排序

六、快速排序

6.1 hoare版本

6.2 挖坑法

6.3 前后指针法

6.4 非递归实现

七、归并排序

7.1 递归实现

7.2 非递归实现

7.2.1 思路实现

7.2.2 数组边界问题

八、计数排序

【Tips】排序算法的复杂度&稳定性

热门文章

最新文章

相关课程

相关电子书

相关实验场景