数据结构和算法之排序总结下-阿里云开发者社区

💦 归并排序

🔑 核心思想 🔑

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

归并排序核心步骤：

❗ 动图演示：❕

🧿 实现代码 —— 递归版：

void _MergeSort(int* a, int left, int right, int* temp)
{
  //只有一个值
  if (left >= right)
    return;
  //[left, mid][mid+1, right]
  int mid = (right + left) / 2;
  //递归
  _MergeSort(a, left, mid, temp);
  _MergeSort(a, mid + 1, right, temp);
  //归并到temp
  int begin1 = left, end1 = mid;
  int begin2 = mid + 1, end2 = right;
    //&&其中一段区间结束就结束了
  int index = left;
  while (begin1 <= end1 && begin2 <= end2)
  {
    if (a[begin1] < a[begin2])
    {
      temp[index++] = a[begin1++];
    }
    else
    {
      temp[index++] = a[begin2++];
    }
  }
    //begin2结束了，拷贝剩下的begin1
  while (begin1 <= end1)
  {
    temp[index++] = a[begin1++];
  }
    //begin1结束了，拷贝剩下的begin2
  while (begin2 <= end2)
  {
    temp[index++] = a[begin2++];
  }
    //归并后的结果，拷贝至原数组
  int i = 0;
  for (i = left; i <= right; i++)
  {
    a[i] = temp[i];
  }
}
void MergeSort(int* a, int n)
{
  //临时数组 
  int* temp = (int*)malloc(sizeof(int) * n);
  //子函数递归
  _MergeSort(a, 0, n - 1, temp);
  //释放临时数组
  free(temp);
}

🧿 实现代码 —— 非递归版：

🔑 核心思想 🔑

void MergeSortNonR(int* a, int n)
{
  //临时数组 
  int* temp = (int*)malloc(sizeof(int) * n);
  int groupNum = 1;
  int i = 0; 
  while (groupNum < n)
  {
    for (i = 0; i < n; i += 2 * groupNum)
    {
      //[begin1, end1][begin2, end2]
      int begin1 = i, end1 = i + groupNum - 1;
      int begin2 = i + groupNum, end2 = i + groupNum * 2 - 1;
      //归并
      int index = begin1;
      //数组的数据个数，并不一定是按整数倍，所以分组可能越界或不存在
        //1.[begin2,end2]不存在或越界，修正为一个不存在的区间
      if (begin2 >= n)
      {
        begin2 = n + 1;
        end2 = n;
      }
        //2.end1越界，修正后归并
      if (end1 >= n)
      {
        end1 = n - 1;
      }
        //3.end2越界，修正后归并
      if (end2 >= n)
      {
        end2 = n - 1;
      }
      while (begin1 <= end1 && begin2 <= end2)
      {
        if (a[begin1] < a[begin2])
        {
          temp[index++] = a[begin1++];
        }
        else
        {
          temp[index++] = a[begin2++];
        }
      }
      //begin2结束了，拷贝剩下的begin1
      while (begin1 <= end1)
      {
        temp[index++] = a[begin1++];
      }
      //begin1结束了，拷贝剩下的begin2
      while (begin2 <= end2)
      {
        temp[index++] = a[begin2++];
      }
    }
    //拷贝回原数组
    for (i = 0; i < n; i++)
    {
      a[i] = temp[i];
    }
    //迭代
    groupNum *= 2;
    //输出每层
    //PrintArray(a, n);
  }
  //释放临时数组
  free(temp);
}

❗ 归并排序的特性总结：❕

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

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

3️⃣ 空间复杂度：O(N)

4️⃣ 稳定性：稳定

💦 非比较排序

1、计数排序

🔑 核心思想 🔑

计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。

计数排序核心步骤：

1️⃣ 统计相同元素出现次数

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

❗ 动图演示：❕

🧿 实现代码：

void CountSort(int* a, int n)
{
  //遍厉一遍找出最小值和最大值
  int min = a[0], max = a[0];
  int i = 0;
  for (i = 1; i < n; i++)
  {
    if (a[i] < min)
    {
      min = a[i];
    }
    if (a[i] > max)
    {
      max = a[i];
    }
  }
  //求出这个区间 
  int range = max - min + 1;
  //calloc空间，并初始化为0 
  int* count = (int*)calloc(range, sizeof(int));
  //统计  
  for (i = 0; i < n; i++)
  {
    //相对位置
    count[a[i] - min]++;
  }
  //根据count数组排序
  i = 0; 
  int j = 0; 
  for (j = 0; j < range; j++)
  {
    while (count[j]--)  
    {
      a[i++] = j + min;
    }
  }
  free(count);
}

❗ 计数排序的特性总结：❕

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

2️⃣ 时间复杂度：O(MAX(N,范围))

3️⃣ 空间复杂度：O(范围)

4️⃣ 稳定性：稳定

5️⃣ 只适合整数排序，浮点数/字符串不能排

2、基数排序

🔑 核心思想 🔑

基数排序又称桶排序，它分别按数据的个、十、百、千、万 … 排序，当然也可以先万、千、…

❗ 动图演示：❕

❓ 这里就不实现了，为什么 ❔

因为这种排序实际在校招中和现实中已经很少使用了，各位码友有兴趣的也可以自己了解下

💦 文件排序 (拓展)

⚠ 注意

小文件排序是没有意义的，当然我们这里只是模拟，所以给 100 个数据

🔑 核心思想 🔑

磁盘的读取速度相比内存差距非常大，所以我们不可能像在内存中两两归并。正确的归并方法是大文件平均分割成 N 份，保证每份大小都可以加载到内存，那么就可以把每个小文件加载到内存中，使用快排排序，再写回小文件，这时就达到文件中归并的先决条件

🧿 实现代码：

void _MergeFile(const char* File1, const char* File2, const char* mFile)
{
  //读文件1
  FILE* fout1 = fopen(File1, "r");
  if (fout1 == NULL)
  {
    printf("打开文件失败\n");
    exit(-1);
  }
  //读文件2
  FILE* fout2 = fopen(File2, "r");
  if (fout2 == NULL)
  {
    printf("打开文件失败\n");
    exit(-1);
  }
  //写文件3,把文件1和文件2写到文件3里
  FILE* fin = fopen(mFile, "w");
  if (fin == NULL)
  {
    printf("打开文件失败\n");
    exit(-1);
  }
  int num1, num2;
  //对于内存中没有问题，但是磁盘就有问题了。不管num1和num2谁小谁大，只要读了fout1和fout2它们都会往后走
  /*while (fscanf(fout1, "%d\n", &num1) != EOF 
    && fscanf(fout2, "%d\n", &num2) != EOF)
  {
    if (num1 < num2)
      fprintf(fin, "%d\n", num1);
    else
      fprintf(fin, "%d\n", num2);
  }*/
  int ret1 = fscanf(fout1, "%d\n", &num1);
  int ret2 = fscanf(fout2, "%d\n", &num2);
  //下面保证了谁读谁走；fout1和fout2都不为空再比较
  while (ret1 != EOF && ret2 != EOF)
  {
    if (num1 < num2)
    {
      fprintf(fin, "%d\n", num1);
      ret1 = fscanf(fout1, "%d\n", &num1);//更新字符
    }
    else
    {
      fprintf(fin, "%d\n", num2);
      ret2 = fscanf(fout2, "%d\n", &num2); //更新字符
    }
  }
  /*注意这样会导致少写一个数据
    //fout2完了，写剩下的fout1
  while (fscanf(fout1, "%d\n", &num1) != EOF)
  {
    fprintf(fin, "%d\n", num1);
  }
    //fout1完了，写剩下的fout2
  while (fscanf(fout2, "%d\n", &num2) != EOF)
  {
    fprintf(fin, "%d\n", num2);
  }*/
  //fout2完了，写剩下的fout1
  while (ret1 != EOF)
  {
    fprintf(fin, "%d\n", num1);
    ret1 = fscanf(fout1, "%d\n", &num1);//更新字符
  }
  //fout1完了，写剩下的fout2
  while (ret2 != EOF)
  {
    fprintf(fin, "%d\n", num2);
    ret2 = fscanf(fout2, "%d\n", &num2); //更新字符
  }
  //关闭文件 
  fclose(fout1);
  fclose(fout2);
  fclose(fin);
}
void MergeSortFile(const char* file)
{
  FILE* fout = fopen(file, "r");
  if (fout == NULL)
  {
    printf("打开文件失败\n");
    exit(-1);
  }
  int n = 10;
  int a[10];
  int i = 0;
  int num = 0;
  char subfile[20];
  int filei = 1;
  memset(a, 0, sizeof(int) * n);
  //从fout文件流里读，直至EOF
  while (fscanf(fout, "%d\n", &num) != EOF)
  {
    //每次循环读10个数据放在内存中(if里先放9个，else再放最后一个)
    if (i < n - 1)
    {
      a[i++] = num;
    }
    else
    {
      a[i] = num;
      //快排10个数据
      QuickSort(a, 0, n - 1);
      //生成文件名sub_sort1/2/3...
      sprintf(subfile, "%d", filei++);
      //写文件，subfile里存储生成的文件名
      FILE* fin = fopen(subfile, "w");
      if (fin == NULL)
      {
        printf("打开文件失败\n");
        exit(-1);
      }
      //写回小文件
      for (int i = 0; i < n; i++)
      {
        fprintf(fin, "%d\n", a[i]);
      }
      //关闭文件
      fclose(fin);
      //重置i
      i = 0;
      memset(a, 0, sizeof(int) * n);
    }
  }
  //互相归并到文件，实现整体有序
  char mFile[100] = "12";
  char File1[100] = "1";
  char File2[100] = "2";
  for (i = 2; i <= n; i++)
  {
    //读取File1和File2，归并出mFile
    _MergeFile(File1, File2, mFile);
    //拷贝迭代File1的文件名12/123/1234...
    strcpy(File1, mFile);
    //循环迭代File2的文件名3/4/5...
    sprintf(File2, "%d", i + 1);
    //循环迭代mFile的文件名123/1234/12345...
    sprintf(mFile, "%s%d",mFile, i + 1);
  }
  //关闭文件
  fclose(fout);
}

💦 性能测试

❓ 测试所有排序 && 怎么保证它是公平的 ❔

数组里放的数据都是一样的

//测试排序的性能对比
void TestOP()
{
  srand(time(0));
  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);
  int* a10 = (int*)malloc(sizeof(int) * N);
  int* a11 = (int*)malloc(sizeof(int) * N);
  int* a12 = (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];
    a10[i] = a1[i];
    a11[i] = a1[i];
    a12[i] = a1[i];
  }
  int begin1 = clock();
  InsertSort(a1, N);
  int end1 = clock();
  int begin2 = clock();
  ShellSort(a2, N);
  int end2 = clock();
  int begin2_1 = clock();
  ShellSortPro(a3, N);
  int end2_1 = clock();
  int begin3 = clock();
  SelectSort(a4, N);
  int end3 = clock();
  int begin3_1 = clock();
  SelectSortPro(a5, N);
  int end3_1 = clock();
  int begin4 = clock();
  HeapSort(a6, N);
  int end4 = clock();
  int begin5 = clock();
  BubbleSort(a6, N);
  int end5 = clock();
  int begin5_1 = clock();
  BubbleSortPro(a7, N);
  int end5_1 = clock();
  int begin6 = clock();
  QuickSort(a8, 0, N - 1);
  int end6 = clock();
  int begin6_1 = clock();
  QuickSortPro(a9, 0, N - 1);
  int end6_1 = clock();
  int begin6_2 = clock();
  QuickSortNonR(a10, 0, N - 1);
  int end6_2 = clock();
  int begin7 = clock();
  MergeSort(a11, N);
  int end7 = clock();
  int begin7_1 = clock();
  MergeSortNonR(a12, N);
  int end7_1 = clock();
  printf("InsertSort:%d\n", end1 - begin1);
  printf("ShellSort:%d\n", end2 - begin2);
  printf("ShellSortPro:%d\n", end2_1 - begin2_1);
  printf("SelectSort:%d\n", end3 - begin3);
  printf("SelectSortPro:%d\n", end3_1 - begin3_1);
  printf("HeapSort:%d\n", end4 - begin4);
  printf("BubbleSort:%d\n", end5 - begin5);
  printf("BubbleSortPro:%d\n", end5_1 - begin5_1);
  printf("QuickSort:%d\n", end6 - begin6);
  printf("QuickSortPro:%d\n", end6_1 - begin6_1);
  printf("QuickSortNonR:%d\n", end6_2 - begin6_2);
  printf("MergeSort:%d\n", end7 - begin7);
  printf("MergeSortNonR:%d\n", end7_1 - begin7_1);
  free(a1);
  free(a2);
  free(a3);
  free(a4);
  free(a5);
  free(a6);
  free(a7);
  free(a8);
  free(a9);
  free(a10);
  free(a11);
  free(a12);
}

💨 输出结果 (这里使用 Release 版本 && 10 万个数据)

这里测试 3 次

三、排序算法复杂度及稳定性分析

❗ 稳定性 (比较重要，注意不要死记，要结合思想来看) ❕

假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次

序保持不变，即在原序列中，r[i]=r[j]，且 r[i] 在 r[j] 之前，而在排序后的序列中，r[i] 仍在 r[j] 之前，则称这种排

序算法是稳定的；否则称为不稳定的。

❓ 稳定性的意义 ❔

假设有一考试，并规定前 6 名发奖状，如果分数相同，则按交卷时间的先后计算名次。此时排序稳定性的意义就有所体现了

四、概念选择题

1、快速排序算法是基于 ( ) 的一个排序算法

A. 分治法

B. 贪心法

C. 递归法

D. 动态规划法

📝 分析：快速排序是一种分治的算法，其次递归不是一种算法

2、对记录（54, 38, 96, 23, 15, 72, 60, 45, 83）进行从小到大的直接插入排序时，当把第8个记录45插入到有序表时，为找到插入位置需比较 ( ) 次？（采用从后往前比较）

A. 3

B. 4

C. 5

D. 6

📝 分析：

15 23 38 54 60 72 96 45

所以需要比较 5 次

3、以下排序方式中占用 O(n) 辅助存储空间的是 ( )

A. 简单排序

B. 快速排序

C. 堆排序

D. 归并排序

📝 分析：注意没有简单排序；归并排序的空间复杂度是 O(N)

4、下列排序算法中稳定且时间复杂度为 O(n²) 的是 ( )

A. 快速排序

B. 冒泡排序

C. 直接选择排序

D. 归并排序

📝 分析：

冒泡排序是稳定的算法，且时间复杂度是 O(N²)

直接选择排序是不稳定的，例如：

5 5 1

1 5 5

5、关于排序，下面说法不正确的是 ( )

A. 快排时间复杂度为 O(N*logN)，空间复杂度为 O(logN)

B. 归并排序是一种稳定的排序，堆排序和快排均不稳定

C. 序列基本有序时，快排退化成冒泡排序，直接插入排序最快

D. 归并排序空间复杂度为 O(N)，堆排序空间复杂度的为 O(logN)

📝 分析：堆排序没使用递归，没有辅助空间，所以它的空间复杂度为 O(1)

6、下列排序法中，最坏情况下时间复杂度最小的是 ( )

A. 堆排序

B. 快速排序

C. 希尔排序

D. 冒泡排序

📝 分析：堆排序 (归并) 最坏情况下和最好情况下时间复杂度最小的 —— O(N*lonN)

7、设一组初始记录关键字序列为 (65,56,72,99,86,25,34,66)，则以第一个关键字 65 为基准而得到的第一趟快速排序结果是 ( )

A. 34，56，25，65，86，99，72，66

B. 25，34，56，65，99，86，72，66

C. 34，56，25，65，66，99，86，72

D. 34，56，25，65，99，86，72，66

📝 分析：

我们前面已经了解到快速排序首次单趟的三种方法 —— hoare版本、挖坑版本、前后指针版本，注意在某些情况下需要都考虑到，因为三种版本得到的结果不一定都一样

结合情况此题选择 A 选项

数据结构和算法之排序总结下

💦 归并排序

💦 非比较排序

1、计数排序

2、基数排序

💦 文件排序 (拓展)

💦 性能测试

三、排序算法复杂度及稳定性分析

四、概念选择题

热门文章

最新文章

相关课程

相关电子书

相关实验场景

数据结构和算法之排序总结 下

💦 归并排序

💦 非比较排序

1、计数排序

2、基数排序

💦 文件排序 (拓展)

💦 性能测试

三、排序算法复杂度及稳定性分析

四、概念选择题

热门文章

最新文章

相关课程

相关电子书

相关实验场景

数据结构和算法之排序总结下