面试常被问到排序算法总结（插入+选择+交换+归并排序）

绝地灬酷狼 2023-01-09 15:31 115阅读 0赞

排序算法总结

谈及排序算法，大家知道常见的排序算法都有哪些呢？

下面来总结一下常见的排序算法：

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70

  • 插入排序

基本思想：

把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列

  • 直接插入排序

插入排序思想：给已经有序的序列中插入新的数据
假设：第一个数据有序
插入过程：从有序序列的最后一个位置向前遍历，找到第一个小于待插入数据的位置，待插入元素之前的数据后移覆盖，待插入数据放在当前位置的下一个

  1. void insert_sort(int* arr, int n)
  2. {
  3.     int temp;
  4.     int j;
  5.     //1,找到待插入元素 从数组第二个元素开始
  6.     for (int i = 1; i < n; i++)
  7.     {
  8.         temp = arr[i];//2,temp存放插入元素
  9.         j = i - 1;//记录待插入元素的前一个元素位置
  10.         //3,待插入元素之前的数据比它大的后移覆盖
  11.         while (j >= 0 && arr[j] > temp)
  12.         {
  13.             arr[j + 1] = arr[j];
  14.             j--;
  15.         }
  16.         //4,空位（待插入位）赋值
  17.         arr[j + 1] = temp;//因为下一位置插入，所以j+1
  18.     }
  19. }

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

  1. 元素集合越接近有序，直接插入排序算法的时间效率越高**

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

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

4. 稳定性：稳定 比如9 2 3 5 5 排序后 2 3 5 5 9 值相同元素相对位置没有改变

  • 希尔排序

希尔排序为直接插入排序算法的优化

基本思想是：

先选定一个整数（步长step,也可以认为是分组间隔），把待排序文件中所有记录分成个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工 作。当到达=1时，所有记录在统一组内排好序。

希尔排序：
（1）插入排序的优化
（2）步长：初始设置为 元素个数/2
（3）经过步长次排序：每次排完，步长减1
（4）每次排序都已步长为间隔给所有元素分组，组内插入排序（插入交换）

  1. void shell_sort(int* arr, int n)
  2. {
  3.     int step = n / 2;//初始化步长为n/2
  4.     int temp;
  5.     int j;
  6.     //1,找到待插入元素 从数组第二个元素开始
  7.     while (step >= 1)
  8.     {
  9.         for (int i = step; i < n; i++)
  10.         {
  11.             temp = arr[i];//2,temp保持待插入元素
  12.             j = i - step;//记录待插入元素的前步长个元素位置
  13.             //3,待插入元素之前的数据比它大的后移覆盖
  14.             while (j >= 0 && arr[j] > temp)
  15.             {
  16.                 arr[j + step] = arr[j];
  17.                 j -= step;
  18.             }
  19.             //4,空位（待插入位）赋值
  20.             arr[j + step] = temp;//因为j-step操作，所以j+step
  21.         }
  22.         step = step -1;
  23.     }
  24. }

**希尔排序的特性总结：

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

2. 当step > 1时都是预排序，目的是让数组更接近于有序。当step == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。

3. 希尔排序的时间复杂度不好计算，需要进行推导，推导出来平均时间复杂度： O(N^1.3—N^2）

4. 稳定性：不稳定 分组后的交换会破坏相对位置关系

  • 选择排序

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

  • 直接选择排序

算法步骤：

1，在元素集合array[i]—array[n-1]中选择关键码最大(小)的数据元素

2，若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个（第一个）元素交换

3，在剩余的array[i]—array[n-2]（array[i+1]—array[n-1]）集合中，重复上述步骤，直到集合剩余1个元素

我们在空间【0，n-1】选取最小值，与第一个元素交换，逐渐缩小空间，保证交换后头部的元素逐步有序

  1. void select_sort(int* arr, int n)
  2. {
  3.     //从未排序的序列中找最值，存放到未排序的起始位置
  4.     //未排序的区间[start,end]
  5.     int start = 0;
  6.     int end = n - 1;
  7.     while (start < end)
  8.     {
  9.         //找到最小值位置
  10.         int minidx = start;
  11.         for (int i = start + 1; i <= end; i++)
  12.         {
  13.             if (arr[i] < arr[minidx])   //if (arr[i] <= arr[minidx]):不稳定  相同元素 =导致更新，相对位置变化
  14.                 minidx = i;
  15.         }
  16.         //把最小值位置存未排序开始的位置
  17.         int temp = arr[start];
  18.         arr[start] = arr[minidx];
  19.         arr[minidx] = temp;
  20.         //剩余未排序空间[start+1,end]
  21.         ++start;
  22.     }
  23. }

可以将上述过程进一步优化：减少遍历次数

每次从未排序区间找一个最大值和最小值 将最小值放在头部，最大值放在尾部

但需要特别注意：特殊处理 100 9 2 3 最大值就位于开始位置，找到最小值更新到开始位置后 2 9 100 3
由于最大值位置索引没有更新，再执行最大值放尾部 3 9 100 2 出现bug

需要判断最大值位置是否处于头部，如果处于头部，需要将最大值位置此时更新为原来最小值的位置

  1. void select_sort2(int* arr, int n)
  2. {
  3.     //从未排序的序列中找最值，存放到未排序的起始位置
  4.     //未排序的区间[start,end]
  5.     int start = 0;
  6.     int end = n - 1;
  8.     while (start < end)
  9.     {
  10.         //找到最小值位置
  11.         int minidx = start;
  12.         int maxidx = start;
  13.         for (int i = start + 1; i <= end; i++)
  14.         {
  15.             if (arr[i] < arr[minidx])   //if (arr[i] <= arr[minidx]):不稳定  相同元素 =导致更新，相对位置变化
  16.                 minidx = i;
  17.             if (arr[i] > arr[maxidx])
  18.                 maxidx = i;
  19.         }
  20.         //把最小值位置存未排序区间开始的位置
  21.         int temp = arr[start];
  22.         arr[start] = arr[minidx];
  23.         arr[minidx] = temp;
  25.         //特殊处理 100 9 2 3  最大值就位于开始位置，找到最小值更新到开始位置后 2 9 100 3  
  26.         //由于最大值位置索引没有更新，再执行最大值放尾部 3 9 100 2  出现bug
  28.         //判断一下最大值位置是否位于起始位置
  29.         if (maxidx = start)
  30.         {
  31.             maxidx = minidx;//由于交换 此时最大值位置存放最小值，需要更新最大值位置为最小值位置，才可以找到最大值
  32.         }
  33.         //把最大值位置存未排序区间尾部的位置
  34.         int tmp = arr[end];
  35.         arr[end] = arr[maxidx];
  36.         arr[maxidx] = tmp;
  37.         //剩余未排序空间[start+1,end-1]
  38.         start++;
  39.         end--;
  40.     }
  41. }

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

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

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

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

4. 稳定性：不稳定 产生位置交换

  • 堆排序

队排序用大二叉树的知识，即完全二叉树实现大小堆

实现从小到大排序 ——->维护大堆

实现从大到小排序 ——->维护小堆

  1. //向下调整
  2. void shiftdown(int* arr, int n, int curpos)
  3. {
  4.     int child = 2 * curpos + 1;
  5.     while (child < n)
  6.     {
  7.         if (child + 1 < n&&arr[child + 1] > arr[child])//找孩子中最大值
  8.             child++;
  9.         if (arr[child] > arr[curpos])
  10.         {
  11.             //大的值向上，当前值向下调整
  12.             int tmp = arr[curpos];
  13.             arr[curpos] = arr[child];
  14.             arr[child] = tmp;
  16.             //更新当前位置
  17.             curpos = child;
  18.             child = 2 * curpos + 1;
  19.         }
  20.         else
  21.             break;
  22.     }
  23. }
  25. void heap_sort(int* arr, int n)
  26. {
  27.     //建大堆
  28.     for (int i = (n - 2) / 2; i >=0; i--)
  29.     {
  30.         shiftdown(arr,n,i);
  31.     }
  32.     //堆中最后一个元素
  33.     int end = n - 1;
  34.     while (end > 0)
  35.     {
  36.         //交换堆顶和最后一个元素
  37.         int temp = arr[0];
  38.         arr[0] = arr[end];
  39.         arr[end] = temp;
  41.         //除去最后一个元素 继续维护大堆
  42.         shiftdown(arr,end,0);
  43.         end--;
  45.     }
  46. }

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

  1. 堆排序使用堆来选数，效率就高了很多。**

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

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

4. 稳定性：不稳定 子节点与父节点交换

  • 交换排序

其中以交换排序中的冒泡排序和快速排序将经常出现在面试题中，本次博客重点分享这两种算法

交换排序的基本思想是：所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，

交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。

  • 冒泡排序

冒泡排序是大家比较熟悉的一种排序算法，这里不再做过多解释

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 1

  1. #include<iostream>
  2. using namespace std;
  4. //冒泡排序  相邻元素比较，每一次遍历范围：0-未排序数据的最后一个位置
  5. void bubble_sort(int* arr, int n)
  6. {
  7.     for (int i = 0; i < n; i++)
  8.     {
  9.         int flag = 1;//标记一轮冒泡排序中是否发生交换操作
  10.         for (int j = 0; j < n - i - 1; j++)
  11.         {
  12.             if (arr[j] > arr[j + 1])
  13.             {
  14.                 int temp = arr[j];
  15.                 arr[j] = arr[j + 1];
  16.                 arr[j + 1] = temp;
  17.                 flag = 0;
  18.             }
  19.         }
  20.         //如果没有发生交换，说明剩余元素全部有序 提前结束
  21.         if (flag == 1)
  22.         {
  23.             break;
  24.         }
  25.     }
  26. }

测试代码如下：

  1. #include<iostream>
  2. using namespace std;
  3. #include"sort.h"
  7. void print(int* arr, int n)
  8. {
  9.     for (int i = 0; i < n; i++)
  10.     {
  11.         cout << arr[i] << " ";
  12.     }
  13. }
  15. int main()
  16. {
  17.     int arr[10] = { 9,66,54,33,5,78,123,0,7,12 };
  18.     //int arr[10] = { 1,3,5,7,9,11,13,15,17,19 };
  19.     //int arr[10] = { 1,13,15,17,19,0,2,4,6,8 };
  20.     cout << "before sort:" << endl;
  21.     print(arr, 10);
  22.     cout << endl;
  23.     cout << "after sort:" << endl;
  24.     bubble_sort(arr, 10);
  25.     print(arr, 10);
  26.     return 0;
  27. }

测试结果如下：

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 2

冒泡排序的特性总结：

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

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

  3. 稳定性：稳定**

    • 快速排序

快速排序作为交换排序的一种算法，是许多家公司面试特别容易被问到的一个算法

首先我们要明白，快排为什么“快”？

这就要理解快排的算法思想，它是基于一种类似于二分法的划分，然后在通过划分结果分别再次划分，直至有序

在此过程中，我们可以采用递归的算法，也可以采用非递归的算法，后面我们将这两种实现方法都做一具体实现

划分的方法也各不相同，但目的都是一样的，根据基准值划分，保证在基准值一边大一边小

常见的划分方法有：

  • hoare法：

算法步骤：

选取一个基准值
从剩余元素中开始遍历
1，从后往前找到第一个小于基准值的数据 保证一边大，一边小
2，从前往后找到第一个大于基准值的数据
3，交换两个位置的值
4，从交换的位置，分别开始，继续执行第一步

结束：从相遇位置的数据和基准值进行交换

  1. int paration(int* arr, int begin, int end)
  2. {
  3.     //选择基准值
  4.     int mid = getmid(arr, begin, end);//优化：三数取中 -> 划分均衡
  5.     // 取中作为基准值  交换两个位置的值
  6.     int tmp = arr[begin];
  7.     arr[begin] = arr[mid];
  8.     arr[mid] = tmp;
  10.     int key = arr[begin];
  11.     int start = begin;
  12.     while (begin < end)
  13.     {
  14.         //从后往前找到第一个小于基准值的数据
  15.         while (begin < end&&arr[end] >= key)
  16.         {
  17.             end--;
  18.         }
  19.         //从前往后找到第一个大于基准值的数据
  20.         while (begin < end&&arr[begin] <= key)
  21.         {
  22.             begin++;
  23.         }
  24.         //交换两个位置的值
  25.         int tmp = arr[end];
  26.         arr[end] = arr[begin];
  27.         arr[begin] = tmp;
  28.     }
  29.     //从相遇位置的数据和基准值进行交换
  30.     int temp = arr[begin];
  31.     arr[begin] = arr[start];
  32.     arr[start] = temp;
  33.     return begin;//返回划分位置  保证一边大一边小
  34. }

在实际测试过程中，发现针对有序的数据采用这种划分方法，在递归调用的过程中，递归调用次数取决于数据量的大小，数据量过大将会导致，栈溢出

对此，本代码进行优化，具体如何优化呢？

首先分析，为什么有序的数据划分出现了问题，这是因为划分不均衡，导致数据划分在集中一侧

为了保证划分均衡，对于基准值的选择进行了优化

采用：三数取中，分别以一组数据的开头，中间，结尾，以其三个数的中间值作为基准值，无论一组数据是否有序，都可以使得划分均衡

  1. //优化：三数取中 -> 划分均衡
  2. int getmid(int* arr, int begin, int end)
  3. {
  4.     int mid = (end - begin) / 2;
  5.     if (arr[begin] < arr[end])
  6.     {
  7.         if (arr[begin] > arr[mid])
  8.             return begin;
  9.         else if (arr[mid] > arr[end])
  10.             return end;
  11.         else
  12.             return mid;
  13.     }
  14.     else
  15.     {
  16.         if (arr[end] > arr[mid])
  17.             return end;
  18.         else if (arr[mid] > arr[begin])
  19.             return begin;
  20.         else
  21.             return mid;
  22.     }
  23. }

三数取中，返回三个数的中间值作为基准值，从而后续进行划分

在划分过程中需要注意：

如果是递增排序：

则： 1，从后往前找到第一个小于基准值的数据 保证一边大，一边小
2，从前往后找到第一个大于基准值的数据

如果递减排序：

则： 1，从后往前找到第一个大于基准值的数据 保证一边大，一边小
2，从前往后找到第一个小于基准值的数据

注意到，二者都是先从后往前，然后再 从前往后，如果颠倒将无法保证划分结果任然是一边大，一边小

  • 挖坑法：

算法步骤：

选取一个基准值，保存基准值
从剩余元素中开始遍历
1，从后往前找到第一个小于基准值的数据 ，将数据挖出填入begin位置的坑里
2，从前往后找到第一个大于基准值的数据，将其填入上一步挖出所产生的的坑里

结束：从相遇位置的数据将基准值进行填入

  1. //挖坑法 划分
  2. int paration2(int* arr, int begin, int end)
  3. {
  4.     //选择基准值
  5.     int key = arr[begin];
  6.     while (begin < end)
  7.     {
  8.         //从后往前找到第一个小于基准值的数据
  9.         while (begin < end&&arr[end] >= key)
  10.         {
  11.             end--;
  12.         }
  13.         arr[begin] = arr[end];
  15.         //从前往后找到第一个大于基准值的数据
  16.         while (begin < end&&arr[begin] <= key)
  17.         {
  18.             begin++;
  19.         }
  20.         arr[end] = arr[begin];
  22.     }
  23.     //从相遇位置的数据将基准值进行填入
  24.     arr[end] = key;
  25.     return begin;//返回划分位置  保证一边大一边小
  26. }
  • 前后指针法

算法步骤

prev:上一个小于基准值的位置

cur: 下一个小于基准值的位置
当cur走到一个小于基准值的位置，则:
判断prev和cur是否连续:
如果连续:区间[prev,cur]的值都是不大于基准值，更新prev, cur
如果不连续:区间[prev, cur]的值，有大于基准值的，更新prev,数据交换，更新cur

  1. //前后指针法  划分
  2. int paration3(int* arr, int begin, int end)
  3. {
  4.     //选择基准值
  5.     int key = arr[begin];
  6.     int prev = begin;//上一个小于基准值的位置
  7.     int cur = begin + 1;//下一个小于基准值的位置
  8.     while (cur <= end)
  9.     {
  10.         if (arr[cur] < key&&++prev != cur)//不连续
  11.         {
  12.             //交换两个位置的值
  13.             int tmp = arr[prev];
  14.             arr[prev] = arr[cur];
  15.             arr[cur] = tmp;
  16.         }
  17.         cur++;
  18.     }
  19.     //交换两个位置的值
  20.     int tmp = arr[begin];
  21.     arr[begin] = arr[prev];
  22.     arr[prev] = tmp;
  23.     return prev;
  26. }

得到划分结果后，进行快排，包括递归和非递归两种形式：

  • 递归快排：（二分法思想）

    //递归法
    void quicksort(int* arr,int begin,int end)
    {

    1. if (begin >= end)
    2.     return;
    3. int div = paration3(arr, begin, end);
    4. quicksort(arr,begin,div-1);
    5. quicksort(arr, div + 1, end);

    }

  • 非递归快排：

分别借助，顺序表尾插，尾删的操作，以及队列尾进头出的数据结构完成非递归快排

主要通过借助数据结构保存划分结束后的分组情况

类似情况如下图：

20210121194140894.png

分组结果中，数据个数不超过两个的，单独一组，不在进行分组存储，如果超过两个的分组存储在数据结构中

左右两个边界，left和right

如果是顺序表，尾插操作，先插入right，再插入left，获取的时候，尾删操作，先获取尾部最后一个元素left，尾删后在获取最后一个元素right，保证先左后右的顺序，直至顺序表为空结束。

  1. //非递归法
  3. void quicksort2(int* arr, int n)
  4. {
  5.     //创建一个顺序表，保持划分的区间
  6.     SeqList sl;
  7.     SeqListInit(&sl);
  8.     //首先保存整个空间
  9.     // 尾插：先放右，在放左  【0，n-1】
  10.     SeqListPushBack(&sl, n - 1);
  11.     SeqListPushBack(&sl, 0);
  12.     int left, right;
  13.     while (!SeqListisEmpty(&sl))
  14.     {
  15.         //从尾部取出尾删  实现取出先左后右
  16.         left = SeqListBack(&sl);
  17.         SeqListPopBack(&sl);
  18.         right = SeqListBack(&sl);
  19.         SeqListPopBack(&sl);
  21.         int div = paration(arr, left, right);
  22.         if (left < div - 1)//区间长度超过2个元素
  23.         {
  24.             SeqListPushBack(&sl, div - 1);
  25.             SeqListPushBack(&sl, left);
  26.         }
  27.         if (div + 1 < right)
  28.         {
  29.             SeqListPushBack(&sl, right);
  30.             SeqListPushBack(&sl, div + 1);
  31.         }
  32.     }
  34. }

对于此，可以考虑使用队列先进先出的结构来实现

左边界left先进，最后左边界left先出

  1. //非递归法  队列
  3. void quicksort3(int* arr, int n)
  4. {
  5.     //创建一个队列，保持划分的区间
  6.     Queue q;
  7.     initQueue(&q);
  8.     //首先保存整个空间
  9.     // 队尾插入先左后右  【0，n-1】
  10.     queuePush(&q, 0);
  11.     queuePush(&q, n-1);
  12.     int left, right;
  13.     while (queueSize(&q)>0)
  14.     {
  15.         //从队头出
  16.         left = queueFront(&q);
  17.         queuePop(&q);
  18.         right = queueFront(&q);
  19.         queuePop(&q);
  20.         //划分 产生新的左右区间
  21.         int div = paration(arr, left, right);
  22.         if (left < div - 1)//区间长度超过2个元素，需要保存到队列
  23.         {
  24.             queuePush(&q, left);
  25.             queuePush(&q, div - 1);
  26.         }
  27.         if (div + 1 < right)
  28.         {
  29.             queuePush(&q, div + 1);
  30.             queuePush(&q, right);
  31.         }
  32.     }
  33. }

非递归即为数组划分结果的存储，直至划分结果为单独数据时即为有序

快速排序的特性总结：

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

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

  3. 稳定性：不稳定**

    • 归并排序

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 3

  • 递归式

首先根据合并两个有序序列的思想（合并两个有序链表）实现合并的代码，但合并的前提就是，两个序列必须有序

  1. //合并前提 两个数组有序
  2. void merge(int* arr,int left,int right)
  3. {
  4.     int mid = left+(right - left) / 2;
  5.     int len = right - left + 1;
  6.     //创建临时数组
  7.     int* temp = (int*)malloc(sizeof(int)*len);
  9.     int k = 0;        //临时数组下标
  10.     int p = left;    //左数组首元素下标
  11.     int q = mid + 1;//右数组首元素下标
  12.     //先有一半存入临时数组
  13.     while (p <= mid && q <= right)
  14.     {
  15.         if (arr[p] < arr[q])
  16.         {
  17.             temp[k++] = arr[p++];//谁小谁先放入临时数组中
  18.         }
  19.         else
  20.         {
  21.             temp[k++] = arr[q++];
  22.         }
  23.     }
  24.     //剩余元素排最后
  25.     while (p <= mid)
  26.     {
  27.         temp[k++] = arr[p++];
  28.     }
  29.     while (q <= right)
  30.     {
  31.         temp[k++] = arr[q++];
  32.     }
  33.     //拷贝回原数组
  34.     memcpy(arr+left,temp,sizeof(int)*len);
  35.     free(temp);
  36.     temp = NULL;
  37. }

在合并过程中，我们动态开辟空间进行临时合并数据存储，合并完成后拷贝回原数组，需要注意到，拷贝回原数组，原始数组的首地址需要变化，以左边界left作为偏移量，在后续递归过程中就可以看到为什么要有偏移量的操作了

针对需要排序的数组，首先通过递归调用的方式将其进行区间划分，直至区间仅剩单独元素停止继续划分

  1. //针对无序数组  先拆分直至有序  然后依次合并
  2. void Mergesort(int* arr, int l, int r)
  3. {
  4.     if (l == r) //区间只有一个元素,无需排序
  5.     {
  6.         return;
  7.     }
  8.     int m = l + (r - l) / 2;
  9.     Mergesort(arr, l, m);  //拆分左数组
  10.     Mergesort(arr, m+1, r); //拆分右数组
  11.     merge(arr, l, r);//合并
  12. }
  • 非递归式

与递归式相同，首先写出合并代码，为了方便后续非递归的实现，此时的中间索引mid，不在通过左右边界的关系来产生，而是作为参数传入

  1. //合并前提 两个数组有序
  2. void merge2(int* arr, int left,int mid, int right)
  3. {
  4.     int len = right - left + 1;
  5.     //创建临时数组
  6.     int* temp = (int*)malloc(sizeof(int)*len);
  8.     int k = 0;        //临时数组下标
  9.     int p = left;    //左数组首元素下标
  10.     int q = mid + 1;//右数组首元素下标
  11.     //先有一半存入临时数组
  12.     while (p <= mid && q <= right)
  13.     {
  14.         if (arr[p] < arr[q])
  15.         {
  16.             temp[k++] = arr[p++];//谁小谁先放入临时数组中
  17.         }
  18.         else
  19.         {
  20.             temp[k++] = arr[q++];
  21.         }
  22.     }
  23.     //剩余元素排最后
  24.     while (p <= mid)
  25.     {
  26.         temp[k++] = arr[p++];
  27.     }
  28.     while (q <= right)
  29.     {
  30.         temp[k++] = arr[q++];
  31.     }
  32.     //拷贝回原数组
  33.     memcpy(arr + left, temp, sizeof(int)*len);
  34.     free(temp);
  35.     temp = NULL;
  36. }

在进行非递归划分时，观察下图，根据拆分及合并顺序，推导得出左右边界的索引关系

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 4

20210124165242954.png

  1. //非递归  归并排序
  2. void Mergesort2(int* arr, int n)
  3. {
  4.     int step = 1;
  5.     while (step < n)
  6.     {
  7.         for (int idx = 0; idx < n; idx += 2 * step)
  8.         {
  9.             //找到两个待合并子区间
  10.             int begin = idx;
  11.             int mid = idx + step - 1;//第一个子区间结束位置
  12.             //判断是否存在第二个子区间
  13.             if (mid >= n - 1)
  14.             {
  15.                 continue;//不存在第二个子区间，直接跳过
  16.             }
  17.             int end = idx + 2 * step - 1;
  18.             //判断第二个子序列是否越界
  19.             if (end >= n)
  20.             {
  21.                 end = n - 1;
  22.             }
  23.             merge2(arr,begin,mid,end);
  24.         }
  25.         step *= 2;
  26.     }
  27. }

**归并排序的特性总结：

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

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

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

4. 稳定性：稳定

发表评论

表情：
评论列表 （有 0 条评论，115人围观）

还没有评论，来说两句吧...

相关阅读