数据结构:第八章 - 排序 660次阅读 数据结构 2022-08-02 目录 [TOC] ![](https://picture-host-1304031833.cos.ap-beijing.myqcloud.com/SiYuan/SplitLine/SplitLine-01.gif) > * 本章节所有的排序算法都是非递减排序。 > * 注意:非递减不等于递增,因为可能出现相同关键字。 # 一、基本概念 ## (一)排序 将无序序列拍成有序序列,其中的每一项可能是单独数据元素,也可能是条记录(多个数据元素组成)。 * 数据元素按需排序。 * 记录,按主关键字或次关键字排序。 > 主关键字:唯一标识一条记录 > ## (二)稳定性 指待排序列中有两个或以上相同的关键字时,排序前、后这些关键字的相对位置是否发生变化。 * 无变化,则稳定。 * 发生变化,则不稳定。 > 若关键字不能重复,则排序结果是唯一的,那么算法的稳定性无关紧要。 > > 若关键字可以重复,则按需选择,稳定或不稳定算法。 > ## (三)排序算法的分类 1、插入类的排序 * 在一个已经有序的序列中,插入一个新的关键字。 * 直接插入排序、折半插入排序、希尔排序。 2、交换类的排序 * 交换类排序的核心是“交换”,即每一趟排序,都通过一系列的 “交换”动作,让一个关键字排到它最终的位置上。 * 起泡排序、快速排序。 3、选择类的排序: * 选择类排序的核心是“选择",即每一趟排序都选出一个最小(或最大)的关键字,把它和序列中的第一个(或最后一个)关键字交换,这样最小(或最大)的关键字到位。 * 简单选择排序、堆排序。 4、归并类的排序 * 归并就是将两个或两个以上的有序序列合并成一个新的有序序列,归并类排序就是基于这种思想。 * 二路归并排序。 5.基数类的排序 * 基数类的排序基于多关键字排序的思想,把一一个逻辑关键字拆分成多个关键字。 ![](https://picture-host-1304031833.cos.ap-beijing.myqcloud.com/SiYuan/SplitLine/SplitLine-01.gif) # 二、插入类排序 ## (一)直接插入排序 ### 1、算法思想 ![](https://picture-host-1304031833.cos.ap-beijing.myqcloud.com/SiYuan/%E6%8A%80%E6%9C%AF%E5%9F%9F/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/Unit8/DS.Unit8.%282.1.1_1%29.gif) 每趟将一个待排序的关键字按照其值的大小插入到已经排好的部分有序序列的适当位置上,直到所有排序关键字都被插入到有序序列中为止。 ### 2、算法执行过程 * 将无序序列的关键字按照前后顺序输出,并进入有序序列。 * 新关键字到有序序列中,按照顺序查找的方式找到其要插入的位置,并插入。 * 若新旧关键字相同,则新插入旧的后方。 * 从输出到插入到适当位置,算一趟排序。 ### 3、Code ```c void insertSort(int arr[], int n)//待排序关键字存储在arr[]中,默认为int,个数为n { int temp, i, j; for(i=1; i=0 && temp 旧,则进入高半区。 * 新 < 旧,则进入低半区。 (2)递归循环之关键字高低半区无其他数字,插入其对应位置。 ### 2、时间复杂度分析 折半插入排序适合关键字数较多的场景,与直接插入排序相比,折半插入排序在查找插入位置上面所花的时间大大减少。折半插入排序在关键字移动次数方面和直接插入排序是一样的,所以其时间复杂度和直接插入排序还是一样的。 折半插入排序的关键字比较次数和初始序列无关。因为每趟排序折半查找插入位置时,折半次数是一定的(都是在 low>high 时结束),折半一次就要比较一次,所以比较次数是一定的。 由此可知折半插入排序的时间复杂度最好情况为 $$O(nlog_2n)$$,最差情况为 $$O(n^2)$$,平均情况为 $$O(n^2)$$。 ## (三)希尔排序 ### 1、算法介绍 希尔排序又叫做缩小增量排序,其本质还是插入排序,只不过将待排序列按某种规则(增量的选取)分成几个子序列,分别对几个子序列进行直接插入排序。 > 即,先将整个记录表分割成若干部分,分别进行直接插入排序,然后再对整个记录表进行一次直接插入排序。 子序列:子序列内元素间的距离为待排序列元素间的距离,两者只互换存储位置。 ### 2、算法思想 ![](https://picture-host-1304031833.cos.ap-beijing.myqcloud.com/SiYuan/%E6%8A%80%E6%9C%AF%E5%9F%9F/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/Unit8/DS.Unit8.%282.3.2_1%29.gif) 把相隔某个“增量”的记录组成一个子表,对各个子表分别进行直接插入排序,当整个表中的元素已经呈“基本有序”时,再对全体记录进行一次直接插入排序。 > 初始增量是人为给定的,往后的可按照希尔的规定。 1. 确定初始增量。 2. 循环进行以下操作: 1. 将序列按照初始增量 n,划分成 n 个子序列。 2. 对各序列内进行直接插入排序,然后将所有序列合并。 3. 当增量不等于 1 时,除 2,返回进行 a 操作。 3. 当增量 n=1 时,对整个序列进行直接插入排序。 > “相隔某个增量”:指,从某元素的下一个元素开始直到以第“增量”个数字的元素,“某元素和第增量个元素”为一组。 > 给定了某趟排序完成的序列,找出增量的可能大小: > > * 以增量划分的子序列是有序的,则找出所有“元素间隔相同且有序”的子序列,即可知道本趟增量值。 ### 3、增量选取规则: * 希尔自己提出的: ⌊ n/2 ⌋、⌊ n/4 ⌋、...⌊ $$\frac{n}{2^k}$$ ⌋ 、... 2、1 即每次将增量除以 2 并向下取整,其中 n 为序列长度,此时时间复杂度为 $$O(n^2)$$。 > * 初始增量选择为序列长度的一半,往后每次选取时,除 2,得整数(若序列长度为奇数,则除后向下取整); > * 增量序列的最后一个值一定取 1; > * 增量序列中的值应尽量没有除 1 之外的公因子。 > * 帕佩尔诺夫和斯塔舍维奇提出的: $$2^k +1$$、... 65、33、17、9、5、3、1 其中,k 为大于等于 1 的整数,$$2^k +1$$ 小于待排序列长度,增量序列末尾的 1 是额外添加的。此时时间复杂度为 $$O(n^{1.5})$$。 ### 4、希尔排序 Code 两种实现方法 定义一个乱序一维数组。 ```c int[] arr = {8,9,1,7,2,3,5,4,6,0} ``` 初始增量为 gap = length / 2 = 5,意味着整个数组被分为 5 组,[8,3] [9,5] [1,4] [7,6] [2,0]。 对着 5 组分别进行直接插入排序,结果如下,可以看到,像 3,5,6 这些小元素都被调到前面了,然后缩小增量 gap = 5 / 2 = 2,数组被分为 2 组 [3,1,0,9,7] [5,6,8,4,2]。 对以上 2 组再分别进行直接插入排序,结果如下,可以看到,此时整个数组的有序程度更进一步,再缩小增量 gap = 2 / 2 = 1,此时,整个数组为 1 组[0,2,1,4,3,5,7,6,9,8]。 #### (1)交换法 交换法中,每次排序都存在交换两个逆序数据的行为。如[5,6,8,4]其中元素 4 要交换到前面需要先和元素 8 交换,再和元素 6 交换,最后和元素 5 交换,更换到最前面。 假设有大量数据,而最后一个数据为最小数据,因此要交换至最前面,那么就需要和每一个数据交换,会产生大量运算。而移位法不需要。 ```c void shellSort(int arr[],int n) { int temp; for(int gap=n/2; gap>0; gap/=2) { for(int i=gap; i=gap && arr[j-gap]>temp; j-=gap) arr[j]=arr[j-gap]; arr[j]=temp; } } } ``` #### (2)移位法 移位法将最小的那个数据只进行了一次插入,在找到本轮循环其所在位置插入即可,大大提高了排序的效率。 ```c void shellSort2(int[] arr) { // 增量gap,并逐步的缩小增量 for(int gap = arr.length/2 ; gap > 0 ; gap /= 2) { // 第gap个元素开始,逐个对其所在的组进行直接插入排序 for(int i = gap; i= 0 && temp < arr[j-gap]) { // 开始移动 arr[j] = arr[j-gap]; j -= gap; } // 当退出while循环后,就给temp找到了插入的位置 arr[j] = temp; } } } } ``` ![](https://picture-host-1304031833.cos.ap-beijing.myqcloud.com/SiYuan/SplitLine/SplitLine-01.gif) # 三、交换类排序 ## (一)冒泡排序 ### 1、算法介绍 冒泡排序又称起泡排序,通过一系列“交换动作完成”。 ### 2、算法思想 ![](https://picture-host-1304031833.cos.ap-beijing.myqcloud.com/SiYuan/%E6%8A%80%E6%9C%AF%E5%9F%9F/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/Unit8/DS.Unit8.%283.1.2_1%29.gif) 1. 按以下步骤循环 1. 将第一个关键字和第二个关键字比较,如果第一个大,则二者交换,否则不交换; 2. 将第二个和第三个按 1 比较,第三个和第四个比较…………。 3. 一直按这种方式进行下去,最终最大的那个关键字被交换到了最后,一趟起泡排序完成。 2. 当在一趟排序过程中没有发生关键字交换,则结束算法,得到有序序列。 ### 3、Code ```c void bubleSort(int arr[], int n) { int i, j, flag; int temp; for(i = n-1; i >= 1; --i) { flag = 0;//flag用来标记本趟排序是否发生了交换 for(j=1; j<=i; ++j) if(arr[j-1] > arr[j]) { temp = arr[j]; arr[j] = arr[j-1]; arr[j-1] = temp; flag = 1;//若未发生交换,则flag=0;若发生交换,则flag=1 } if(flag == 0)//一趟中没有关键字交换,则序列有序,排序结束 return; } } ``` ### 4、时间复杂度分析 (1)最坏情况 * 待排序列逆序,此时对于外层循环的每次执行,内层循环中 if 语句的条件 R[j] 通过多次划分操作实现,属于分支排序。 采用顺序结构存储。 ### 1、算法思想 ![](https://picture-host-1304031833.cos.ap-beijing.myqcloud.com/SiYuan/%E6%8A%80%E6%9C%AF%E5%9F%9F/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/Unit8/DS.Unit8.%283.2.1_1%29.gif) * 通过一次排序将整个无序表分成相互独立的两部分,其中一部分中的数据都比另一部分中包含的数据的值小。 * 然后继续沿用此方法分别对两部分进行同样的操作,直到每一个小部分不可再分,所得到的整个序列就成为了有序序列。 当初始序列有序时,若每次选择第一个数据记录为枢纽,将退化为冒泡排序。 ### 2、算法过程 以升序为例: * 每一趟选择当前所有子序列中的一个关键字(通常为第一个)作为枢轴,将子序列中比枢轴小的移到枢轴前边,比枢轴大的移动到枢轴后边。 * 当本趟所有子序列都被枢轴以上述规则划分完毕后会得到新的一组更短的子序列,他们成为下一趟划分的初始序列集。 * 每次排序,子序列都会以枢轴化为两个更短的子序列。 > 快速排序对每一个子序列的一次划分算作一趟排序,每一趟结束后有一个关键字到达最终位置。 ### 3、Code ```c void quickSort(int arr[], int low, int high) //对all[low]到all[high]的关键字进行排序 { int temp; int i = low, j = high; if(low < high) { temp = arr[low]; /*此循环完成一趟排序,即:将数组中小于temp的关键字放左边,大于temp的放右边*/ while(i < j) { while(j > i && arr[j] >= temp) --j;//从右往左扫描,找到一个小于temp的关键字 if(i < j) { arr[i] = arr[j];//放在temp左边 ++i;//i右移一位 } while(i < j && arr[i] < temp) ++i;//从左往右扫描,找到一个大于temp的关键字 if(i < j) { arr[j] = arr[i];//放在temp右边 --j;//j左移一位 } } arr[i] = temp;//将temp放在最终位置 quickSort(arr, low, i-1);//递归地对temp左边的关键字进行排序 quickSort(arr, i+1, high);//递归地对temp右边的关键字进行排序 } } ``` ### 4、时间复杂度分析 快速排序最好情况下的时间复杂度为 $$O(nlog_2n)$$,待排序列越接近无序,本算法效率越高。最坏情况下的时间复杂度为 $$O(n^2)$$,待排序列越接近有序,本算法效率越。平均情况下时间复杂度为 $$O(nlog_2n)$$。 快速排序的排序趟数和初始序列有关。 ![](https://picture-host-1304031833.cos.ap-beijing.myqcloud.com/SiYuan/SplitLine/SplitLine-01.gif) # 四、选择类排序 ## (一)简单选择排序 ### 1、算法思想 ![](https://picture-host-1304031833.cos.ap-beijing.myqcloud.com/SiYuan/%E6%8A%80%E6%9C%AF%E5%9F%9F/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/Unit8/DS.Unit8.%284.1.1_1%29.gif) 对于具有 n 个记录的无序表遍历 n-1 次,第 i 次从无序表中第 i 个记录开始,找出后序关键字中最小的记录,然后放置在第 i 的位置上。 * 从头至尾顺序扫描无序序列,找出最小的一个关键字,和第一个关键字交换。 * 剩余关键字继续这种选择和交换,最终使序列有序。 > 在形式上,序列被分为前后两部分,前边为有序序列,后边为无序序列,整体并未分隔开。 > > 每一次交换,都是与无序序列中的第一个关键字交换,交换完后归并至有序序列,且无序序列关键字减少 1 个,直至无序序列关键字为 0。 > ### 2、Code ```c void selectSort(int arr[],int n) { int i, j, k; int temp; for(i=0; i arr[j]) k = j; /*以下三句完成最小关键字与无序序列第一个关键字的交换,即顺序表转置*/ temp = arr[i]; arr[i] = arr[k]; arr[k] = temp; } } ``` ### 3、时间复杂度分析 通过本算法代码可以看出,两层循环的执行次数和初始序列没有关系,外层循环执行 n 次,内层循环执行 n-1 次,将最内层循环中的比较操作视为关键操作,其执行次数为(n-1+1)(n- 1)/2=n(n-1)/2,即时间复杂度为 $$O(n^2)$$。 ## (二)堆排序 ### 1、堆的含义 在含有 n 个元素的序列中,如果序列中的元素满足下面其中一种关系时,此序列可以称之为堆。 堆是一种数据结构,可将其看作一棵完全二叉树,此完全二叉树满足: * 任何一个非叶结点的值不大于(或不小于)其左右孩子结点的值。 * 若父亲大孩子小,则称其为大顶堆。 * 若父亲小孩子大,则称其为小顶堆。 同时,我们对堆中的结点按层进行编号,将这种逻辑结构映射到数组中就是下图。 若用公式表述堆的定义: * **大顶堆:arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]** * **小顶堆:arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]** ### 2、算法思想 逻辑思想: * 通过将无序表转化为堆,可以直接找到表中最大值或最小值,然后将其提取出来。 * 令剩余的记录再重建一个堆,取出其最大值或最小值,如此反复执行就可以得到一个有序序列,此过程为堆排序。 实际操作思想: 1. 将无需序列构建成一个堆,根据升序降序需求选择大顶堆或小顶堆。 2. 将堆顶元素与末尾元素交换,将最大元素"沉"到数组末端。 3. 重新调整结构,使其满足堆定义,然后继续交换堆顶元素与当前末尾元素,反复执行调整 + 交换步骤,直到整个序列有序。 > 取出堆顶元素后,放入有序序列,此时有序序列关键字加 1,无序序列关键字减 1。 ### 3、堆排序需解决的两个问题 从根结点到叶子结点的整个调整的过程,被称为“筛选”,即调整堆顺序。 n 个结点的完全二叉树,最后一个结点是 ⌊n/2⌋ 个结点的孩子。 #### (1)筛选 * 当前结点(假设为 a)的值与其孩子结点进行比较,若存在大于 a 值的孩子结点,则从中选出最大的一个与 a 交换。 * 当 a 来到下一层时重复上述过程,直到 a 的孩子结点值都小于 a 的值为止。 > 因交换后,可能破坏了下一层堆的结构,所以需要重复上述过程 > #### (2)如何将无序序列构造成初始堆? * 对第 ⌊n/2⌋ 个结点为根的子树筛选,使该子树成为堆。 * 之后向前依次对各结点( ⌊n/2⌋ -1 ~ 1)为根的子树进行筛选。 > 做筛选工作时,规律是从底层结点开始,一直筛选到根结点。 #### (3)输出堆顶元素后,如何将剩余二叉树调整成新的堆? * 当删除堆顶元素(根结点)后,将此时堆的最后一个元素(底层最右边的叶子结点)放置堆顶。 * 因破坏了堆的结构,需要对堆进行排序。 ### 4、基本操作 以大顶堆为例: (1)建堆 * 先将序列调整为一个大顶堆。 (2)插入结点 * 需在插入结点后保持堆的性质(即完全二叉树形态与父大子小性质),因此需要先将插入的结点 x 放在最底层的最右边,插入后满足完全二叉树的特点。 * 把 x 依旧向上调整到合适位置以满足父大子小的性质。 (3)删除结点 * 当删除堆中的一个结点时,原位置会出现一个孔,将堆底元素赋值到该孔,并筛选到合适位置,最后删除叶子结点。 ### 5、堆排序执行过程 1. 从无序序列所确定的完全二叉树的最后一个非叶子结点,从右至左,从下至上,对每个结点进行调整,最后将得到一个大顶堆。 2. * 将当前无序序列中的第一个关键字,反映在树中是根结点(假设为 a)与无序序列中最后一个关键字交换(假设为 b)。 * a 进入有序序列,到达最终位置。 * 无序序列中关键字减少 1 个,有序序列中关键字增加 1 个。 * 此时只有结点 b 可能不满足堆的定义,对其进行调整。 3. 重复第 2 步,直到无序序列中剩余 1 个关键字,排序结束,将其进入有序序列 4. 输出即得有序序列。 将原始序列调整为大(小)顶堆,进行层次遍历(左-> 右,上-> 下)为新序列。 > 新序列只满足堆的结构要求,每层中的结点不一定非要按序摆放。即,层内是无序的。 ### 6、Code ```c /* sift函数完成在数组arr[low]到arr[high]的范围内对在low上的结点进行调整 */ void sift(int arr[], int low, int high) { int i = low, j = 2*i + 1;//arr[j]是arr[i]的左孩子结点 int temp = arr[i]; while(j <= high) { if(j=0; --i)//建立初始堆 sift(arr, i, n-1); for(i=n-1; i>0; --i)//进行n-1次循环,完成堆排序 { /*以下3句换出了根结点中的关键字,将其放入最终位置*/ temp = arr[0]; arr[0] = arr[i]; arr[i] = temp; sift(arr, 0, i-1);//在减少1个关键字的无序序列中进行调整 } } ``` ### 7、时间复杂度分析 堆排序算法每次调整堆,相当于从一棵完全二叉树的根走到叶子结点的过程,时间复杂度为 $$O(log_2n)$$,初始建堆需要 n 次调整,每趟排序需要一次调整,有 n 趟排序,因此基本操作的执行次数为 $$2n*O(log_2n)$$,即时间复杂度为 $$O(nlog_2n)$$。 初始序列如何,对排序过程都没有影响,因此任何情况下堆排序的时间复杂度都是 $$O(nlog_2n)$$。 ![](https://picture-host-1304031833.cos.ap-beijing.myqcloud.com/SiYuan/SplitLine/SplitLine-01.gif) # 五、二路归并排序 ## (一)算法思想 ![](https://picture-host-1304031833.cos.ap-beijing.myqcloud.com/SiYuan/%E6%8A%80%E6%9C%AF%E5%9F%9F/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/Unit8/DS.Unit8.%285.1_1%29.gif) 先将所有的记录完全分开,然后两两合并,在合并的过程中将其排好序,最终能够得到一个完整的有序表。 ## (二)二路归并排序 对于含有 n 个记录的无序表,首先默认表中每个记录各为一个有序表(只不过表的长度都为 1),然后进行两两合并,使 n 个有序表变为⌈n/2⌉ 个长度为 2 或者 1 的有序表(例如 4 个小有序表合并为 2 个大的有序表),通过不断地进行两两合并,直到得到一个长度为 n 的有序表为止。 * 将原始序列看成 n 个只有 1 个关键字的子序列。 * 两两合并,形成若干有序二元组,若有没有归并对象的,保持原样。 * 上述两步递归操作,直至排序完成。 ## (三)Code ```c void mergeSort(int arr[],int low,int high) { if (low < high) { int mid = (low+high)/2; mergeSort(arr, low, mid);//归并排序前半段 mergeSort(arr, mid+1, high);//归并排序后半段 merge(arr, low, mid, high);//这里直接修改调用了线性表的merge(),功能是把A数组中low到mid和mid+1到high范围内的两段有序序列归并成一段有序序列 } } /*修改后的merge函数*/ void merge(int arr[], int low, int mid, int high) { int i, j, k; int n1 = mid - low + 1; int n2 = high - mid; int L[n1], R[n2]; for (i = 0; i < n1; i++) L[i] = arr[low + i]; for (j = 0; j < n2; j++) R[j] = arr[mid + 1 + j]; i = 0; j = 0; k = low; while (i < n1 && j < n2) { if (L[i] <= R[j]) arr[k] = L[i++]; else arr[k] = R[j++]; k++; } while (i < n1) arr[k++] = L[i++]; while (j < n2) arr[k++] = R[j++]; } ``` ![](https://picture-host-1304031833.cos.ap-beijing.myqcloud.com/SiYuan/SplitLine/SplitLine-01.gif) # 六、基数排序 ## (一)算法思想 ![](https://picture-host-1304031833.cos.ap-beijing.myqcloud.com/SiYuan/%E6%8A%80%E6%9C%AF%E5%9F%9F/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/Unit8/DS.Unit8.%286.1_1%29.gif) * 思想:多关键字排序。 * 实现方式:最高位优先、最低为优先。 * 最高位优先(计数排序):即先按最高位拍成若干子序列,再对每个子序列按次高位排序。 * 最低为优先(桶排序):每次排序全体关键字都参与,(不用分成子序列),对关键字进行“分配”与“收集”两种操作完成排序。 * 收集分配原则:按原始序列顺序,将其的每个数放到对应的桶中,若该桶没有关键字则不收集。 * 当不足位数的关键字前边补 0,使各个关键字位数相同。 ## (二)算法执行过程 此处的桶实际是一个**先进先出的队列**。 每个关键字都是整数数值,且其中的最大值由个位、十位和百位构成,以此为例: 1. 因数字范围 0~9,采用 10 个桶用于存放关键字,桶名为数字。 2. 进行第一趟分配和收集,本次按照个位。 3. 按照桶序,输出第一趟排序结果。 4. 在第一趟的排序基础上,进行第二趟分配和收集,本次按照十位。 5. 按照桶序,输出第二趟排序结果。 6. 在第二趟的排序基础上,进行第三趟分配和收集,本次按照百位。 7. 按照桶序,输出第三趟排序结果,此结果为最终的有序序列。 > 注意: > > 例子用纯数字来演示,所以只准备了 10 个桶。关键字每一位不一定都是数字,还有可能是: > > * 若某位为扑克牌的花色,需增加 4 个桶来存放花色; > * 若某位为英文字母,需增加 26 个桶来存放字母(不区分大小写情况下,否则 52 个桶); > * **…………………………………………** ![](https://picture-host-1304031833.cos.ap-beijing.myqcloud.com/SiYuan/SplitLine/SplitLine-01.gif) # 七、内部排序算法的优势分析 本章介绍了以下几种常见的排序算法: * 插入排序:直接插入排序、折半插入排序、2-路插入排序、表插入排序和希尔排序。 * 起泡排序(冒泡排序)。 * 快速排序(快排)。 * 选择排序:简单选择排序、堆排序。 * 归并排序:二路归并排序。 * 基数排序。 > 简单排序包含除希尔排序之外的所有插入排序,起泡排序和简单选择排序。 > ## (一)性能分析 | **排序方法** | **平均情况** | **最坏情况** | **辅助存储空间** | | -------------------- | -------------------- | -------------------- | ------------------------ | | 简单排序 | O( n2 ) | O( n2 ) | O( 1 ) | | 希尔排序 | O( nlog2n ) | O( n2 ) | O( 1 ) | | 快速排序 | O( nlog2n ) | O( nlog2n ) | O( log2n ) | | 堆排序 | O( nlog2n ) | O( nlog2n ) | O( 1 ) | | 归并排序 | O( nlog2n ) | O( nlog2n ) | O( n ) | | 基数排序 | O( d*n ) | O(d*n ) | O( d*n ) | > * 辅助存储空间,即为 空间复杂度。 > * 表格中的 n 表示无序表中记录的数量; > * 基数排序中的 d 表示进行分配和收集的次数。 1. 在上表表示的所有“简单排序算法”中,以直接插入排序算法最为简单,当无序表中的记录数量 n 较小时,选择该算法为最佳排序方法。 2. 所有的排序算法中单就平均时间性能上分析,快速排序算法最佳,其运行所需的时间最短,但其在最坏的情况下的时间性能不如堆排序和归并排序。 堆排序和归并排序相比较,当无序表中记录的数量 n 较大时,归并排序所需时间比堆排序短,但是在运行过程中所需的辅助存储空间更多(以空间换时间)。 3. 从基数排序的时间复杂度上分析,该算法最适用于对 n 值很大但是关键字较小的序列进行排序。 4. 在所有基于“比较”实现的排序算法中(以上排序算法中除了基数排序,都是基于“比较”实现),其在最坏情况下能达到的最好的时间复杂度为 O(nlog2n)。 ## (二)算法稳定性 本章所介绍的大多数算法都是在顺序存储结构的基础上实现的,基于顺序存储结构的局限性,排序算法在排序过程都需要进行大量记录的移动,影响算法本身的效率。 当无序表中记录的数量很大时,就需要采用静态链表替换顺序存储结构,例如:表插入排序、链式基数排序算法,是以修改指针代替大量移动记录的方式提高算法效率。 ### 1、不稳定算法 * 快速排序、希尔排序、堆排序。 * 简单选择排序:基于关键字交换的,用于顺序结构的算法。 ### 2、稳定算法 * 直接插入排序、折半查找排序、冒泡排序、二路归并排序、基数排序。 * 简单选择排序:基于关键字插入的,用于链式结构的算法。 > 关于简单选择排序,按照此算法来实现(同时也是绝大数学校所使用的算法),一定是不稳定的。并且对其的考察最多是稳定性分析。 ![](https://picture-host-1304031833.cos.ap-beijing.myqcloud.com/SiYuan/SplitLine/SplitLine-01.gif) # 八、排序算法中的“一趟” 总说:“趟”常见于国内教材对排序算法的解释,对于这些算法每“趟”都有不同的变化,是一个比较无聊的说法;国外教材中暂时没有见过类似于“趟”描述。 为了方便记忆、理解,进行下总结,对于国内教材,每种算法中每“趟”的所经历的步骤(或): > 前 6 个排序算法的“每趟 ”,较容易理解。 > > 快速排序与归并排序都都是基于分治法的递归排序,甚至于它们两者的过程近似于互补。因此意义与前边的不同,更加难理解。 1、直接插入排序、折半插入排序: * 将待排关键字插入到对应位置。 2、希尔排序 * 计算增量。 * 以增量分割序列。 * 对所有子序列进行插入排序。 * 将所有子序列汇总成总序列。 3、冒泡排序 * 按从前向后的顺序,除最后一个关键字外,其余每个关键字都与后一个关键字进行比较、交换操作。 * 当倒数第二和最后一个关键字操作完成,则该“趟”结束。 4、简单选择排序 * 从无序序列中挑出待排关键字,将其与无序序列第一位进行交换。 > 逻辑上的无序序列 > 5、堆排序 > 该算法的“趟 ”较为特殊,单指排序过程,并不包括建堆的过程,同时每趟结束待排关键字会跑到堆元素末尾,归为有序序列(逻辑上的,其实是数组末尾有序元素集)里的一员。 * 将堆顶元素与堆末尾元素交换交换。 * 整理堆元素(此时已不包括上一个待排关键字)。 6、基数排序 * 对多个关键字完成分配和收集。 7、快速排序 * 快排的“一趟”又称为“一次划分”。 * 排序过程中,对尚未确定最终位置的所有元素进行一遍处理。 > 2019 年 408 一道考题上对此排序算法“趟”的定义,只指针对那道题。 > 这里注意区分,我们平时讲的快速排序最坏情况下(初始情况完全有序),它的递归次数会达到最高(不是这里题目中的趟数) * **课本定义,对待排序列以枢轴进行一次分割成两子序列,一部分比另一部分小。** * **每趟结束后,至少有一个元素就位。** 此算法在进行完第一趟后,序列会以枢轴划分为两部分。 我们常会以为枢轴左、右两部分,“先左后右”或“两个序列同时进行”就是第二趟,但其实不然。 > 实际上的确有并行快速排序算法。(即,前后两部分同时进行) 第 i 趟排序指“ 对任意可分割待排序列分割成两个子序列就为一趟 ”,不需要看整个序列的未确定位置元素是否全部被处理。 > 天勤书 P246“注意”中写道,对每个子序列的一次划分算作一趟排序。 8、归并排序 对于归并排序,要将一个数组排序,可以先(递归地)将它分成两半分别排序,然后将结果(两个分别有序的数组)归并成一个更大的有序的数组。 实际上,真正在执行“排序”行为的是“**归并**”这个操作,归并排序就是**递归地执行“归并”操作**。 从逻辑理解上来看,归并算法的每趟只需要“将所有子序列从前到后两两合并”。(可参考下图图二来理解) 但,从算法的实现形式看,该算法又可分为 * 一种是比较符合直观逻辑的递归方法,称为自顶向下的归并排序。 * 另一种是迭代实现的方法,称为自底向上的归并排序。 所以对“趟”的理解又有所不同。 (1)自顶向下的归并排序(递归形式) **递归实现**的归并排序是自顶向下划分(也就是划分时由大到小,再把小规模逐步求解),之后自底向上合并。 可以看出将一个数组拆分成两个数组是一个二分的过程,所以可以用一个类似二叉树的结构图来进行。这棵二叉树从上往下看,是归并排序时递归拆分数组的过程,从下往上看,是归并操作对数组进行合并排序的过程。 所以,“趟”在递归中就无法很好的解释。 (2)自底向上的归并排序(非递归形式) 查看本文前面自顶向下的归并排序的示意图,递归的尽头都是将数组拆到只剩 1 个元素,所以 merge()方法也是从两个长度为 1 的数组开始归并,等凑出两个长度为 2 的数组,再将两个长度为 2 的数组归并,以此类推。 若传入的初始数组长度不是 2 的次幂,可能中间子数组的长度略有不同,比如待归并的两个子数组的长度是 3 和 2,但是整个程序的执行逻辑和过程都是一样的,都是从最小的 1 个元素开始归并,接着将得到的结果继续归并。 循着这样一个思路,我们也可以不通过递归调用来对元素进行分组,而是通过循环来对元素进行分组,只要 merge()方法所接受的数组长度从 1 开始,按照 1、2、4 这样一点点递增就可以了。执行逻辑如下图: > **非递归实现**的归并排序的划分是由小到大(注意对比着上一张图看),且没有奇数个元素的情况 对此,我们可以很明显的看出每“趟”就是两两合并的过程。 9、总结 像一些最基本的排序如插入排序、冒泡排序、选择排序的实现。在讨论“一趟”概念的时候并不需要考虑这么多。Why? 因为这些最基本的算法思想是**迭代**,什么是迭代?**是逐步求得结果并更新,**和**一趟**的概念较契合:每迭代处理一次**所有未排序元素**,就会求解出一个未排序元素最终位置。 而快排和归并接触到的写法多是递归形式的,利用了分治的思想,既然涉及分治,就无法避免划分和求解问题的顺序问题。 ![](https://picture-host-1304031833.cos.ap-beijing.myqcloud.com/SiYuan/SplitLine/SplitLine-01.gif) # 九、补充 ## (一)适用场景 对一个初始状态为递增的序列进行按递增顺序的排序(即原始序列有序),直接插入排序最省时,快速排序最费时。 ## (二)排序原理 ### 1、关键字是否在最终位置上 * 交换类和选择类的排序每趟结束都有一个关键字到位。 * 直接插入排序和折半插入排序,在最后一次前可能每个关键字都不在其最终的位置上。 ### 2、排序趟数与序列初态 **无关**:直接插入排序、折半插入排序、希尔排序、简单选择排序、归并排序、基数排序。 **有关**:冒泡排序、快速排序。 * 交换类排序:躺数和原始序列状态有关。 * 直接插入排序:每趟排序都是插入一个关键字,所以排序趟数固定为 n-1 (n 为关键字数)。 * 简单选择排序:每趟排序都是选出一个最小(或最大)的关键字,所以排序趟数固定为 n-1 (n 为关键字数)。 * 基数排序:每趟排序都要进行“分配”和“收集”,排序趟数固定为 d(d 为关键字位数)。 ### 3、排序过程中的比较次数与序列初态 **无关**:二路归并排序、简单选择排序、基数排序。 * 简单选择排序:每次从无序序列中挑出一个最小的,不管原始序列如何,比较次数皆为无序序列中关键字的个数,因此比较次数与初始序列无关。 **有关**:快速排序、直接插入排序、冒泡排序、堆排序、希尔排序。 * 序列初态越有序,比较次数越少。 ### 4、算法复杂度与序列初态 **无关**:一堆(**堆排序**)乌龟(**归并排序**)选(**选择排序**)基(**基数排序**)友。 其余都有关。 ### 5、排序算法特点 * 快速排序,每趟排序后将当前子序列划分为两部分的那个关键字(“枢轴")到达了其最终位置。 * 堆排序,每趟排序后,当前待排序列中的最大或者最小关键字到达其最终位置。 * 冒泡排序,每趟排序后,当前待排序列中的最大或者最小关键字到达其最终位置。 * 希尔排序是直接插入排序的改进,每趟排序后不能保证一定有关键字到达最终位置。 ## (三)排序过程求解妙招 若未告诉初始序列,只告诉排序结果,根据排序原理可解答。(假设两趟后结果) * 简单选择排序,两趟后应该选出两个最小的在最前面,或者两个最大的在最后面。 * 冒泡排序,两趟后应该有最大的两个数沉底,或者最小的两个数上浮。 * 直接插入排序,两趟后插入两个数,那么前三个数应该是有序的。 * 堆排序,两趟后应该选出两个最大或最小的数。 * 快速排序,第一趟结束后,整个序列会出现以下特点:在序列中一定存在这样一个关键字 a,比 a 大的关键字与比 a 小的关键字分别出现在 a 的两边。两趟后应该有三个。 * 二路归并排序:两趟后应形成长度为 4 的有序子序列。 ![](https://picture-host-1304031833.cos.ap-beijing.myqcloud.com/SiYuan/SplitLine/SplitLine-01.gif) # 参考资料 > **版权声明**:个人学习记录,本博客所有文章均采用 CC-BY-NC-SA 许可协议。转载请注明出处!若有侵权,请留言联系! > > * 2022 天勤计算机考研高分笔记-数据结构 > * 2022 王道计算机考研复习指导-数据结构 > * 解学武数据结构与算法教程(C 语言版):http://data.biancheng.net/ > * 关于“躺”的理解,全文转发:https://blog.csdn.net/kazzan/article/details/112517998 > * https://www.zhihu.com/people/zjing-ming/posts > * 部分动图来源:https://www.cnblogs.com/onepixel/p/7674659.html 如果您觉得文章对您有帮助,请点击文章正下方的小**红心**一下。您的鼓励是博主的最大动力! 1 最后一次更新于2022-10-23 数据结构
0 条评论