【数据结构与算法】排序算法总结（下）-阿里云开发者社区

交换排序

1.基本思想

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

2.冒泡排序

以升序为例，降序同理。冒泡排序是将相邻的元素两两比较，如果左边的元素比右边的元素大，则交换这两元素，以此类推，一次循环过后较大的元素就来到了数组后面的位置。

void Swap(int* x, int* y)
{
  int tmp = *x;
  *x = *y;
  *y = tmp;
}
// 最坏时间复杂度为O(N^2)
// 最好时间复杂度为O(N)
void BubbleSort(int* a, int n)
{
  for (int i = 0; i < n - 1; i++)
  {
    int exchange = 0;
    for (int j = 1; j < n - i; j++)
    {
      if (a[j - 1] > a[j])
      {
        Swap(&a[j - 1], &a[j]);
        exchange = 1;
      }
    }
    if (exchange == 0)
    {
      break;
    }
  }
  //for (int i = 0; i < n - 1; i++)
  //{
  //  int exchange = 0;
  //  for (int j = 0; j < n - 1 - i; j++)
  //  {
  //    if (a[j] > a[j + 1])
  //    {
  //      Swap(&a[j], &a[j + 1]);
  //      exchange = 1;
  //    }
  //  }
  //  if (exchange == 0)
  //  {
  //    break;
  //  }
  //}
}

冒泡排序的特性总结

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

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

空间复杂度：O(1)

稳定性：稳定

3.快速排序

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

基准值key一般为是第一个或者是最后一个，但这种选数方式有一个缺点就是当数组有序时，有可能造成递归深度太深，栈溢出。除了这种选数方式，还有三数取中法和随机数法。

Hoare 版本

如何保证相遇位置的值比key小？

左边第一个位置的值做key，R 先走；右边第一个位置的值做key，L 先走。

R 停下来，L 撞到 R 相遇，相遇位置的值比key小

L 停下来，R 撞到 L 相遇，相遇位置的值比key小

三数取中法

// 三数取中--避免有序时递归深度过深
int GetMidIndex(int* a, int left, int right)
{
  int mid = left + (right - left) / 2;
  if (a[left] < a[mid])
  {
    if (a[mid] < a[right])
    {
      return mid;
    }
    else if (a[left] > a[right])
    {
      return left;
    }
    else
    {
      return right;
    }
  }
  else // a[left] >= a[mid]
  {
    if (a[mid] > a[right])
    {
      return mid;
    }
    else if (a[left] < a[right])
    {
      return left;
    }
    else
    {
      return right;
    }
  }
}

交换数组的函数

void Swap(int* x, int* y)
{
  int tmp = *x;
  *x = *y;
  *y = tmp;
}

// hoare
// 返回值为分界点
int PartSort1(int* a, int left, int right)
{
  // 三数取中
  int mid = GetMidIndex(a, left, right);
  Swap(&a[left], &a[mid]);
  int keyPos = left;
  while (left < right)
  {
    // 6 6 6 6 6
    // R找小
    while (left < right && a[right] >= a[keyPos])
    {
      right--;
    }
    // L找大
    while (left < right && a[left] <= a[keyPos])
    {
      left++;
    }
    // 没有相遇就交换
    if (left < right)
    {
      Swap(&a[left], &a[right]);
    }
  }
  int meetPos = left;
  Swap(&a[keyPos], &a[meetPos]);
  return meetPos;
}

挖坑法

// 挖坑法
// 返回值为分界点
int PartSort2(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)
  {
    // 右边找小，填到左边坑里去
    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;
  return hole;
}

前后指针法

// 前后指针法
// 返回值为分界点
int PartSort3(int* a, int left, int right)
{
  // 选随机数法
  srand((unsigned int)time(NULL)); // 需要包含time.h头文件
  int p = rand() % (right - left + 1) + left;  // [left, right]
  Swap(&a[left], &a[p]);
  int keyPos = left;
  int prev = left;
  int cur = left + 1;
  while (cur <= right)
  {
    // cur找小于a[keyPos]的值
    if (a[cur] < a[keyPos] && ++prev != cur)
    {
      Swap(&a[prev], &a[cur]);
    }
    cur++;
  }
  Swap(&a[prev], &a[keyPos]);
  return prev;
}

PartSort1、PartSort2和PartSort3函数都是保证数组左边的数据小于key，中间的数据为key，右边的数据大于key，然后利用递归将区间继续分割，从而实现数组有序。

快排递归代码实现

// [begin, end]
// 快速排序最好时间复杂度为O(N^2)，最坏时间复杂度为O(N^2)
void QuickSort(int* a, int begin, int end)
{
  // 区间不可再分了
  if (begin >= end)
  {
    return;
  }
  // begin和end相近时，数组已经非常接近有序
  if (end - begin <= 8) 
  {
    InsertSort(a + begin, end + 1 - begin);
  }
  else
  {
    int keyPos = PartSort3(a, begin, end);
    // 划分为两个子区间：[begin, keyPos-1] keyPos [keyPos+1, end]
    QuickSort(a, begin, keyPos - 1);
    QuickSort(a, keyPos + 1, end);
  }
}

快排递归展开图

快速排序的优化

三数取中法和随机选数法

递归到小的子区间时，使用插入排序

尽管快速排序有了以上的优化，但是面对着大量的重复数据，快速排序对这些数据进行排序还是显得比较吃力的。

快速排序除了，递归的实现还有非递归的实现方式。递归就是系统帮你建立函数栈帧，而非递归就是需要你自己手动压栈。

那如何手动压栈呢？首先，我们需要申请一个栈st。左边界left和右边界right依次入栈，当栈st不为空时，先出右边界right，后出左边界left。当left >= right时，不需要排序，直接continue；当left < right时，调用PartSort3函数并用keyPos``PartSort3函数的返回值，分为两个子区间[left, keyPos -1]和[keyPos + 1, right]。当这两个区间都有效时，先压右区间后压左区间；当区间无效时，就不压栈了。重复以上过程直至栈为空。

快排非递归代码实现

typedef int STDataType;
typedef struct Stack
{
  STDataType* a;
  int top;
  int capacity;
}ST;
void StackInit(ST* ps);
void StackDestroy(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 = ps->capacity = 0;
}
void StackDestroy(ST* ps)
{
  assert(ps);
  free(ps->a);
  ps->a = NULL;
  ps->top = ps->capacity = 0;
}
void StackPush(ST* ps, STDataType x)
{
  assert(ps);
  // 扩容
  if (ps->top == ps->capacity)
  {
    int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
    STDataType* tmp = (STDataType*)realloc(ps->a, newCapacity * sizeof(STDataType));
    if (tmp == NULL)
    {
      perror("realloc fail");
      exit(-1);
    }
    ps->a = tmp;
    ps->capacity = newCapacity;
  }
  ps->a[ps->top] = x;
  ps->top++;
}
void StackPop(ST* ps)
{
  assert(ps);
  assert(!StackEmpty(ps));
  --ps->top;
}
STDataType StackTop(ST* ps)
{
  assert(ps);
  assert(!StackEmpty(ps));
  return ps->a[ps->top - 1];
}
bool StackEmpty(ST* ps)
{
  assert(ps);
  return ps->top == 0;
}
int StackSize(ST* ps)
{
  assert(ps);
  return ps->top;
}
void QuickSortNonR(int* a, int begin, int end)
{
  ST st;
  StackInit(&st);
  // 先入左边界 后入右边界
  StackPush(&st, begin);
  StackPush(&st, end);
  while (!StackEmpty(&st))
  {
    //先出右边界 后出左边界
    int right = StackTop(&st);
    StackPop(&st);
    int left = StackTop(&st);
    StackPop(&st);
    if (left >= right)
    {
      continue;
    }
    int keyPos = PartSort3(a, left, right);
    // [left, keyPos-1] keyPos [keyPos+1, right]
    if (keyPos + 1 < right)
    {
      StackPush(&st, keyPos + 1);
      StackPush(&st, right);
    }
    if (left < keyPos - 1)
    {
      StackPush(&st, left);
      StackPush(&st, keyPos - 1);
    }
  }
  StackDestroy(&st);
}

快速排序的特性总结

快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序

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

空间复杂度：O(logN)

稳定性：不稳定

归并排序

1.基本思想

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

2.归并排序

归并排序的思路有点像二叉树的后序遍历，先将左右子区间分得不能再分了，然后进行归并，归并后则大区间有序了。同样右边的大区间有序了，然后将左右两个大区间再进行一次归并，那么原数组就有序了。值得注意的是，归并不是在原数组上归并，而是在辅助空间tmp里归并，然后再将归并后的结果拷贝回原数组相应的位置。

归并排序递归代码实现

void _MergeSort(int* a, int begin, int end, int* tmp)
{
  if (begin >= end)
  {
    return;
  }
  int mid = begin + (end - begin) / 2;
  // [begin, mid] [mid+1, end]
  _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, (end + 1 - begin) * sizeof(int));
}
void MergeSort(int* a, int n)
{
  int* tmp = (int*)malloc(n * sizeof(int));
  if (tmp == NULL)
  {
    perror("malloc fail");
    return;
  }
  _MergeSort(a, 0, n - 1, tmp);
  free(tmp);
  tmp = NULL;
}

归并排序也有非递归的方式实现，不过相对来说比较复杂，我们来学习一下。非递归的归并排序的思路就是定义gap，将数组分成n / gap组，每组gap个元素，两两一组进行归并。不过，有时候这种方法会造成数组越界，需要我们做出相应的处理。

越界情况

注意：第一组的左边界begin1永远不会越界。

第一组的右边界end1越界，直接break跳出for循环，无需往下归并。因为这部分的元素已经有序了。

第二组的左边界begin1越界，即第二组全部越界，直接break跳出for循环，无需往下归并。因为这部分的元素已经有序了。

第二组的右边界end2越界，即第二组部分越界，修正end2的值为n - 1，往下继续归并。因为这一部分数组还未真正的有序。

非递归的归并排序图解

归并排序非递归代码实现

void MergeSortNonR(int* a, int n)
{
  int* tmp = (int*)malloc(n * sizeof(int));
  if (tmp == NULL)
  {
    perror("malloc fail");
    return;
  }
  int gap = 1;
  while (gap < n)
  {
    for (int i = 0; i < n; i += 2 * gap)
    {
      // 归并 取小的数据尾插
      int begin1 = i, end1 = i + gap - 1;
      int begin2 = i + gap, end2 = i + 2 * gap - 1;
      // 第一组越界
      if (end1 >= n)
      {
        break;
      }
      // 第二组全部越界
      if (begin2 >= n)
      {
        break;
      }
      // 第二组部分越界
      if (end2 >= n)
      {
        // 修正一下end2，继续归并
        end2 = n - 1;
      }
      int j = i;
      while (begin1 <= end1 && begin2 <= end2)
      {
        if (a[begin1] <= a[begin2]) // 加上等号归并排序为稳定排序
        {
          tmp[j++] = a[begin1++];
        }
        else
        {
          tmp[j++] = a[begin2++];
        }
      }
      while (begin1 <= end1)
      {
        tmp[j++] = a[begin1++];
      }
      while (begin2 <= end2)
      {
        tmp[j++] = a[begin2++];
      }
      // 拷回到原数组 -- 归并哪部分就拷贝哪部分
      memcpy(a + i, tmp + i, (end2 + 1 - i) * sizeof(int));
    }
    gap *= 2;
  }
  free(tmp);
  tmp = NULL;
}

归并排序的特性总结

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

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

空间复杂度：O(N)

稳定性：稳定

计数排序

计数排序的基本思想就是统计相同元素出现次数，根据统计的结果将序列回收到原来的序列中。计数排序又分为绝对映射和相对映射两种方式。相对映射比绝对映射更好，因为相对映射比较节省空间，而且使用绝对映射的计数排序来排序数组，要求数组中不能有负数。

计数排序代码实现

// 时间复杂度：O(N+range)
// 空间复杂度：O(range)
// 适合数据范围集中，也就是range小
// 只适合整数，不适合浮点数、字符串等
void CountSort(int* a, int n)
{
  int i = 0;
  int max = a[0];
  int min = a[0];
  for (i = 1; i < n; i++)
  {
    if (a[i] > max)
    {
      max = a[i];
    }
    if (a[i] < min)
    {
      min = a[i];
    }
  }
  int range = max + 1 - min;
  int* countArr = (int*)calloc(range, sizeof(int));
  if (countArr == NULL)
  {
    perror("malloc fail");
    return;
  }
  for (i = 0; i < n; i++)
  {
    countArr[a[i] - min]++;
  }
  int j = 0;
  for (i = 0; i < range; i++)
  {
    while (countArr[i]--)
    {
      a[j++] = min + i;
    }
  }
  free(countArr);
  countArr = NULL;
}

计数排序的特性总结

计数排序在数据范围集中时，效率很高，但是适用范围及场景有限。

时间复杂度：O(N + range)

空间复杂度：O(range)

稳定性：稳定

👉排序性能测试👈

void TestOP()
{
  srand((unsigned int)time(NULL));
  const int N = 100000;
  int* a1 = (int*)malloc(sizeof(int) * N);
  int* a2 = (int*)malloc(sizeof(int) * N);
  int* a3 = (int*)malloc(sizeof(int) * N);
  int* a4 = (int*)malloc(sizeof(int) * N);
  int* a5 = (int*)malloc(sizeof(int) * N);
  int* a6 = (int*)malloc(sizeof(int) * N);
  int* a7 = (int*)malloc(sizeof(int) * N);
  int* a8 = (int*)malloc(sizeof(int) * N);
  int* a9 = (int*)malloc(sizeof(int) * N);
  for (int i = 0; i < N; ++i)
  {
    a1[i] = rand();
    a2[i] = a1[i];
    a3[i] = a1[i];
    a4[i] = a1[i];
    a5[i] = a1[i];
    a6[i] = a1[i];
    a7[i] = a1[i];
    a8[i] = a1[i];
    a9[i] = a1[i];
  }
  int begin1 = clock();
  InsertSort(a1, N);
  int end1 = clock();
  int begin2 = clock();
  ShellSort(a2, N);
  int end2 = clock();
  int begin3 = clock();
  SelectSort(a3, N);
  int end3 = clock();
  int begin4 = clock();
  HeapSort(a4, N);
  int end4 = clock();
  int begin5 = clock();
  QuickSort(a5, 0, N - 1);
  int end5 = clock();
  int begin8 = clock();
  QuickSortNonR(a8, 0, N - 1);
  int end8 = clock();
  int begin6 = clock();
  MergeSort(a6, N);
  int end6 = clock();
  int begin9 = clock();
  MergeSortNonR(a9, N);
  int end9 = clock();
  int begin7 = clock();
  BubbleSort(a7, N);
  int end7 = clock();
  printf("InsertSort:%d\n", end1 - begin1);
  printf("ShellSort:%d\n", end2 - begin2);
  printf("SelectSort:%d\n", end3 - begin3);
  printf("HeapSort:%d\n", end4 - begin4);
  printf("QuickSort:%d\n", end5 - begin5);
  printf("QuickSortNonR:%d\n", end8 - begin8);
  printf("MergeSort:%d\n", end6 - begin6);
  printf("MergeSortNonR:%d\n", end9 - begin9);
  printf("BubbleSort:%d\n", end7 - begin7);
  free(a1);
  free(a2);
  free(a3);
  free(a4);
  free(a5);
  free(a6);
  free(a7);
}
int main()
{
  TestOP();
  return 0;
}

👉排序算法复杂度及稳定性分析👈

直接插入排序一般可以从前向后进行元素的插入，相同元素的相对位置可以不发生变化。

归并排序也可以保证相同元素的相对位置不变。

冒泡排序在元素相同的情况下也可以不进行交换，也可以保证稳定。

其余排序均无法做到稳定排序。

👉总结👈

本文重点讲解了八大排序以及其实现、复杂度和稳定性，重点需要掌握每种排序算法的思想和实现。以上就是本篇博客的全部内容了，如果大家觉得有收获的话，可以点个三连支持一下！谢谢大家啦！💖💝❣️

【数据结构与算法】排序算法总结（下）

交换排序

1.基本思想

2.冒泡排序

3.快速排序

归并排序

1.基本思想

2.归并排序

计数排序

👉排序性能测试👈

👉排序算法复杂度及稳定性分析👈

👉总结👈

热门文章

最新文章

相关课程

相关电子书

相关实验场景