建设银行网站怎么登录密码,wordpress怎么建设网站,如何建立网站,建筑公司网站功能表前言#xff1a; 今天我们将讲解我们数据结构初阶的最后一部分知识的学习#xff0c;也是最为“炸裂”的知识---------排序算法的讲解#xff01;#xff01;#xff01;#xff01; 目录1.排序的概念及其运用1.1排序的概念1.2排序运用2.常见排序算法的实现2.1 插入排序2…前言 今天我们将讲解我们数据结构初阶的最后一部分知识的学习也是最为“炸裂”的知识---------排序算法的讲解 目录1.排序的概念及其运用1.1排序的概念1.2排序运用2.常见排序算法的实现2.1 插入排序2.1.1直接插入排序2.1.2希尔排序( 缩小增量排序 )2.2 选择排序2.2.1直接选择排序2.2.2堆排序2.3交换排序2.3.1冒泡排序2.3.2 快速排序(重点2.4 归并排序2.5 计数排序3.各种内部排序算法比较及运用3.1内部排序算法的比较3.2内部排序算法的运用4 选择题讲解1.排序的概念及其运用
1.1排序的概念 排序所谓排序就是使一串记录按照其中的某个或某些关键字的大小递增或递减的排列起来的操作。 稳定性假定在待排序的记录序列中存在多个具有相同的关键字的记录若经过排序这些记录的相对次序保持不变即在原序列中r[i]r[j]且r[i]在r[j]之前而在排序后的序列中r[i]仍在r[j]之前则称这种排序算法是稳定的否则称为不稳定的。 内部排序数据元素全部放在内存中的排序。常见的内部排序算法有【插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、计数排序等】 外部排序数据元素太多不能同时放在内存中根据排序过程的要求不能在内外存之间移动数据的排序。 1.2排序运用
要说起排序在我们日常生活的方方面面可以说都能看到。就拿我们平时网上买东西举例当我们挑选时我们总会按照个人的需求进行排序分类例如当我们买电脑时会看到下图 我们可以从很多的角度去选择我们心仪的可以根据价格销量等等看榜单的排名一定层度上能反映出大众都认可的东西
2.常见排序算法的实现
插入排序是一种非常直观的排序算法。其基本思想就是将一个待排序的记录按其关键字的大小插入前面以及排好序的子序列中直到全部记录插入完成。 由插入排序的思想可以引申出三个最重要的排序算法【直接插入排序折半插入排序和希尔排序】
2.1 插入排序
2.1.1直接插入排序
根据上面的插入排序思想不难得出一种最简单也是最直观的直接插入排序算法。假设在排序过程中待排序表L【1…n】在某次排序过程中的某一时刻状态如下 要将元素L[i]插入已有序的子序列L[1…i-1],需要执行以下操作 1查找出L[i] 在L[1…i-1]中的插入位置k。 2将L[k…i-1]中的所有元素依次向后移动一个位置。 3将L[i] 赋值到L[k]. 为了实现对 L [1… n ]的排序可以将 L (2)~ L ( n 依次插入前面已排好序的子序列初始 L [1]可以视为是一个已排好序的子序列。上述操作执行 n -1次就能得到一个有序的表。插入排序在实现上通常采用就地排序空间复杂度为 O (1))因而在从后向前的比较过程中需要反复把已排序元素逐步向后挪位为新元素提供插入空间。 我们通过举例来具体解释一哈步奏。假定初始序列为14, 33, 27, 10, 35, 19, 42, 44 1第一步将第一个元素 14 看作是一个有序的子序列 {14}将剩余元素逐个插入到此序列的适当位置 2第二步 将 33 插入到 {14} 中由于 33 14所以 33 应该插入到 14 的后面新的有序序列变为 {14,33} 3第三步将 27 插入到 {14, 33} 中由于 27 33 同时 27 14所以 27 应该插入到 14 和 33 的中间新的有序序列变为 {14, 27, 33} 4第四步将 10 插入到 {14, 27, 33} 中经过依次和 33、27、14 比较最终断定 10 应该插入到 14之前新的有序序列变为 {10, 14, 27, 33} 5第五步将 35 插入到 {10, 14, 27, 33} 中由于 35 33所以 35 应该插入到 33之后新的有序序列变为 {10, 14, 27, 33, 35} 6第六步 将 19 插入到 {10, 14, 27, 33, 35} 中经过依次和 35、33、27、14 比较最终断定 19应该插入到 14 和 27 之间新的有序序列变为 {10, 14, 19, 27, 33, 35} 7第七步将 42 插入到 {10, 14, 19, 27, 33, 35} 中由于 42 35所以 42 应插入到 35之后新的有序序列变为 {10, 14, 19, 27, 33, 35, 42} 8第八步 将 44 插入到 {10, 14, 19, 27, 33, 35, 42} 中由于 44 42所以 44 应插入到 42 之后新的有序序列变为 {10, 14, 19, 27, 33, 35, 42, 44}。 经过将各个待排序的元素插入到有序序列的适当位置最终得到的就是一个包含所有元素的有序序列。
接下来我们通过动画形象的演示 解释 1.从第一个元素开始该元素可以认为已经被排序 2.取出下一个元素在已经排序的元素序列中从后向前扫描 3.如果该元素已排序大于新元素将该元素移到下一位置 4.重复步骤3直到找到已排序的元素小于或者等于新元素的位置 5.将新元素插入到该位置后 6.重复步骤2~5。 代码如下
void InsertSort(int* a, int n)
{for (int i 0; i n-1; i){int end i;int tmp a[end 1];while (end 0){if (tmp a[end]){a[end 1] a[end];--end;}else{break;}}a[end 1] tmp;}
}性能分析 直接插入排序算法的性能分析如下 空间效率仅使用了常数个辅助单元因而空间复杂度为 O (1)。 时间效率在排序过程中向有序子表中逐个地插入元素的操作进行了 n -1趟每趟操作都分为比较关键字和移动元素而比较次数和移动次数取决于待排序表的初始状态
在最好情况下表中元素已经有序此时每插入一个元素都只需比较一次而不用移动元素因而时间复杂度为 O ( n )。
在最坏情况下表中元素顺序刚好与排序结果中的元素顺序相反逆序总的比较次数达到最大,总的移动次数也达到最大.
平均情况下考虑待排序表中元素是随机的此时可以取上述最好与最坏情况的平均值作为平均情况下的时间复杂度总的比较次数与总的移动次数均约为N^24。 因此直接插入排序算法的时间复杂度为 ON^2 稳定性由于每次插入元素时总是从后向前先比较再移动所以不会出现相同元素相对位置发生变化的情况即直接插入排序是一个稳定的排序方法。
适用性直接插入排序算法适用于顺序存储和链式存储的线性表。为链式存储时可以从前往后查找指定元素的位置。 注意大部分排序算法都仅适用于顺序存储的线性表 2.1.2希尔排序( 缩小增量排序 ) 希尔排序也称递减增量排序算法是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。 从前面的分析可知直接插入排序算法的时间复杂度为O(n^2)但若待排序序列为“正序”时其时间复杂度可以提升为O(n)。由此可见它更适用于基本有序的排序表和数据量不大的排序表。希尔排序正是基于以上两点分析对直接插入排序进行改造得来的 希尔排序法的基本思想是 先选定一个整数把待排序文件中所有记录分成个组所有距离为的记录分在同一组内并对每一组内的记录进行排序。然后取重复上述分组和排序的工作。当到达1时所有记录在统一组内排好序。 我们通过举例来说明次算法的结题思路 算法步骤 选择一个增量序列 t1t2……tk其中 ti tj, tk 1 按增量序列个数 k对序列进行 k 趟排序 每趟排序根据对应的增量 ti将待排序列分割成若干长度为 m 的子序列分别对各子表进行直接插入排序。仅增量因子为 1 时整个序列作为一个表来处理表长度即为整个序列的长度。 动画展示 代码如下
void ShellSort(int* a, int n)
{// gap 1 预排序// gap 1 直接插入排序int gap n;while (gap 1){// gap gap / 2; // gap gap / 3; // 9 8 不能保证最后一次一定是1gap gap / 3 1; // 9 8for (int i 0; i n - gap; i){int end i;int tmp a[end gap];while (end 0){if (tmp a[end]){a[end gap] a[end];end - gap;}else{break;}}a[end gap] tmp;}}
}希尔排序的特性总结 希尔排序是对直接插入排序的优化。当gap 1时都是预排序目的是让数组更接近于有序。当gap 1时数组已经接近有序的了这样就 会很快。这样整体而言可以达到优化的效果。我们实现后可以进行性能测试的对比。希尔排序的时间复杂度不好计算因为gap的取值方法很多导致很难去计算因此在好些树中给出的希尔排序的时间复杂度都不固定《数据结构(C语言版)》— 严蔚敏 《数据结构-用面相对象方法与C描述》— 殷人昆 稳定性当相同关键字的记录被划分到不同的字表时可能会改变它们之前的相对排序因此希尔排序是一种不稳定的排序算法。
适用性希尔排序算法仅适用于线性表为顺序存储的情况。
2.2 选择排序 选择排序的基本思想是 每一趟如第 i 趟在后面 n - i l ( i 1,2,…, n -1个待排序元素中选取关键字最小的元素作为有序子序列的第 i 个元素直到第 n - l 趟做完待排序元素只剩下1个就不用再选了。
2.2.1直接选择排序 选择排序是一种简单直观的排序算法无论什么数据进去都是 O(n²)的时间复杂度。所以用到它的时候数据规模越小越好。唯一的好处可能就是不占用额外的内存空间。 根据上面选择排序的思想可以很直观地得出简单选择排序算法的思想 假设排序表为 L [1… n ]第 i 趟排序即从 L [ i … n 中选择关键字最小的元素与 L ( i 交换每一趟排序可以确定一个元素的最终位置这样经过 n -1趟排序就可使得整个排序表有序。
算法步骤: 首先在未排序序列中找到最小大元素存放到排序序列的起始位置。 再从剩余未排序元素中继续寻找最小大元素然后放到已排序序列的末尾。 重复第二步直到所有元素均排序完毕。 动态图展示 代码如下
// 任何情况都是O(N^2) 包括有序或接近有序
void SelectSort(int* a, int n)
{int begin 0, end n - 1;while (begin end){int mini begin, maxi begin;for (int i begin 1; i end; i){if (a[i] a[mini]){mini i;}if (a[i] a[maxi]){maxi i;}}Swap(a[begin], a[mini]);if (maxi begin)maxi mini;Swap(a[end], a[maxi]);begin;--end;}
}直接选择排序的特性总结 空间效率仅使用常数个辅助单元故空间效率为 O (1)。 时间效率从上述伪码中不难看出在简单选择排序过程中元素移动的操作次数很少不会超过3( n -1次最好的情况是移动0次此时对应的表已经有序但元素间比较的次数与序列的初始状态无关始终是 n ( n -1)/2次因此时间复杂度始终是 O ( n^2)。 稳定性在第 i 趟找到最小元素后和第 i 个元素交换可能会导致第1个元素与其含有相同关键字元素的相对位置发生改变。因此简单选择排序是一种不稳定的排序方法。
2.2.2堆排序
在之前的博客中我们已经详细了解了堆排序的概念以及运用。具体大家可以阅读堆排序的详解
2.3交换排序
基本思想所谓交换就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置。
交换排序的特点是将键值较大的记录向序列的尾部移动键值较小的记录向序列的前部移动。
2.3.1冒泡排序
冒泡排序Bubble Sort也是一种简单直观的排序算法。它重复地走访过要排序的数列一次比较两个元素如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢浮到数列的顶端。
作为最简单的排序算法之一冒泡排序给我的感觉就像 Abandon 在单词书里出现的感觉一样每次都在第一页第一位所以最熟悉。冒泡排序还有一种优化算法就是立一个 flag当在一趟序列遍历中元素没有发生交换则证明该序列已经有序。但这种改进对于提升性能来说并没有什么太大作用。 冒泡排序的基本思想是 从后往前或从前往后两两比较相邻元素的值若为逆序即 A [ i -1] A [ i ])则交换它们直到序列比较完。我们称它为第一趟冒泡结果是将最小的元素交换到待排序列的第一个位置或将最大的元素交换到待排序列的最后一个位置关键字最小的元素如气泡一般逐渐往上漂浮直至水面或关键字最大的元素如石头一般下沉至水底。下一趟冒泡时前一趟确定的最小元素不再参与比较每趟冒泡的结果是把序列中的最小元素或最大元素放到了序列的最终位置…这样最多做 n -1趟冒泡就能把所有元素排好序。 所示为冒泡排序的过程第一趟冒泡时2749不交换1327不交换7613,交换9713交换6513交换3813交换4913交换。通过第一趟冒泡后最小元素已交换到第一个位置也是它的最终位置。第二趟冒泡时对剩余子序列采用同样方法进行排序以此类推到第五趟结束后没有发生交换说明表已有序冒泡排序结束。 算法步骤 比较相邻的元素。如果第一个比第二个大就交换他们两个。 对每一对相邻元素作同样的工作从开始第一对到结尾的最后一对。这步做完后最后的元素会是最大的数。 针对所有的元素重复以上的步骤除了最后一个。 持续每次对越来越少的元素重复上面的步骤直到没有任何一对数字需要比较。 动态图展示如下 代码如下
void BubbleSort(int* a, int n)
{for (int j 0; j n; j){int exchange 0;for (int i 1; i n-j; i){if (a[i - 1] a[i]){Swap(a[i - 1], a[i]);exchange 1;}}// 一趟冒泡过程中没有发生交换说明已经有序了不需要再处理if (exchange 0){break;}}
} 冒泡排序的性能分析如下 空间效率仅使用了常数个辅助单元因而空间复杂度为 O (1)。
时间效率当初始序列有序时显然第一趟冒泡后 flag 依然为 false 本趟冒泡没有元素交换从而直接跳出循环比较次数为 n -1移动次数为0从而最好情况下的时间复杂度为 O ( n )当初始序列为逆序时需要进行 n - l 趟排序第 i 趟排序要进行 n - i 次关键字的比较而且每次比较后都必须移动元素3次来交换元素位置。这种情况下:
冒泡排序总的比较次数为n(n-1)/2移动次数为n(n-1)/2次
从而最坏情况下的时间复杂度为 O ( n^2)其平均时间复杂度也为 O(n^2。 稳定性冒泡排序是一种稳定的排序方法。
注意冒泡排序中所产生的有序子序列一定是全局有序的不同于直接插入排序也就是说有序子序列中的所有元素的关键字一定小于或大于无序子序列中所有元素的关键字这样每趟排序都会将一个元素放置到其最终的位置上。
2.3.2 快速排序(重点
快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下排序 n 个项目要 Ο(nlogn) 次比较。在最坏状况下则需要 Ο(n2) 次比较但这种状况并不常见。事实上快速排序通常明显比其他 Ο(nlogn) 算法更快因为它的内部循环inner loop可以在大部分的架构上很有效率地被实现出来。
快速排序使用分治法Divide and conquer策略来把一个串行list分为两个子串行sub-lists。
快速排序又是一种分而治之思想在排序算法上的典型应用。本质上来看快速排序应该算是在冒泡排序基础上的递归分治法。 其基本思想为 任取待排序元素序列中的某元素作为基准值按照该排序码将待排序集合分割成两子序列左子序列中所有元素均小于基准值右子序列中所有元素均大于基准值然后最左右子序列重复该过程直到所有元素都排列在相应位置上为止。 1. hoare版本即左右指针法
思想 一趟排序过程就是一个交替搜索和替换的过程。任取待排序元素序列中的某元素作为基准值一般是两边的元素我们这里选择最左边然后我们把key放到合适的位置使得左边比key小右边比key大【升序】让最右边的元素先移动找比key小的左边找比key大的然后交换left和right的值直到left和right相遇即止相遇后交换key和leftright任意一个位置的值。 我们通过画图来进行了解
当第一次左右指针相遇后的位置时基准值就被交换到了中间接着呢继续对左右区间进行重复的操作首先直至左区间有序后会进行回调此时再去递归右区间当右区间也有序之后那整体也就有序了
注意 左边做key,可以让左边先走吗 不可以左边做key必须让右边先走右边(right)是找比key小的找到小的停下来即使相遇也能保证right位置的值小于key的
动图展示
代码如下
// Hoare
int PartSort1(int* a, int begin, int end)
{int mid GetMidIndex(a, begin, end);Swap(a[begin], a[mid]);int left begin, right end;int keyi left;while (left right){// 右边先走找小while (left right a[right] a[keyi]){--right;}// 左边再走找大while (left right a[left] a[keyi]){left;}Swap(a[left], a[right]);}Swap(a[left], a[keyi]);keyi left;return keyi;
} 大家分析上述代码会发现有缺陷的地方 1.待排序列呈现有序的情况如果key后面的每个数都比key小或大的话那left向后面找或right向前面找就会产生越界访问的问题为了防止这样情况的产生我们选择在if语句的判断部分加个逻辑与保证left小于right以免产生越界访问的问题。
2.快速排序除了对【有序序列】进行排序会退化之外还有一点就是它需要进行层层递归那既然是递归就需要调用函数既然要调用函数那就需要建立栈帧一旦建立栈帧会出现栈溢出的情况。
第一种方法就是三数取中三数取中就是为了让我们选取的key在序列中的位置尽量靠中间. 三数取中当中的三数指的是最左边的数、最右边的数以及中间位置的数。三数取中就是取这三个数当中值的大小居中的那个数作为该趟排序的key。这就确保了我们所选取的数不会是序列中的最大或是最小值了。
代码如下
// 三数取中
// begin mid end
int GetMidIndex(int* a, int begin, int end)
{int mid (begin end) / 2;if (a[begin] a[mid]){if (a[mid] a[end]){return mid;}else if (a[begin] a[end]){return begin;}else{return end;}}else // a[begin] a[mid]{if (a[mid] a[end]){return mid;}else if (a[begin] a[end]){return begin;}else{return end;}}
}
注意 当大小居中的数不在序列的最左或是最右端时我们不是就以居中数的位置作为key的位置而是将key的值与最左端的值进行交换这样key就还是位于最左端了所写代码就无需改变而只需在单趟排序代码开头加上以下两句代码即可
int midIndex GetMidIndex(a, begin, end);//获取大小居中的数的下标Swap(a[begin], a[midIndex]);//将该数与序列最左端的数据交换//以下代码保持不变...对于三数取中法是在开头优化 而第二种小区间优化法则是在结尾优化 小区间优化是为了让递归深度不要太深因为数据量过大以后我们递归的深度就会增加递归建立的栈帧数量会随着递归深度的增加而增加又因为栈空间本身就小很容易造成栈溢出的问题。当递归区间的数据量较小时我们不采用递归解决他们而是换成直接插入的方法来解决较小数据量的排序。
//小区间优化
if ((end - begin 1) 15)
{//在数据量少的时候改用直接插入排序InsertSort(a begin, end - begin 1);
}2.挖坑法
思想 1、选出一个数据一般是最左边或是最右边的存放在key变量中在该数据位置形成一个坑。 2、还是定义一个left和一个rightleft从左向右走right从右向左走。若在最左边挖坑则需要R先走若在最右边挖坑则需要L先走。 3、在走的过程中若R遇到小于key的数则将该数抛入坑位并在此处形成一个坑位这时left再向后走若遇到大于key的数则将其抛入坑位又形成一个坑位如此循环下去直到最终L和R相遇这时将key抛入坑位即可。选取最左边的作为坑位 经过一次单趟排序最终也使得key左边的数据全部都小于keykey右边的数据全部都大于key。
然后也是将key的左序列和右序列再次进行这种单趟排序如此反复操作下去直到左右序列只有一个数据或是左右序列不存在时便停止操作。
动态展示
代码如下
// 挖坑法
int PartSort2(int* a, int begin, int end)
{int mid GetMidIndex(a, begin, end);Swap(a[begin], a[mid]);int left begin, right end;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;
}3.前后指针法
思想 前后指针法的单趟排序的基本步骤如下 1、选出一个key一般是最左边或是最右边的。 2、起始时prev指针指向序列开头cur指针指向prev1。 3、若cur指向的内容小于key则prev先向后移动一位然后交换prev和cur指针指向的内容然后cur指针若cur指向的内容大于key则cur指针直接。如此进行下去直到cur指针越界此时将key和prev指针指向的内容交换即可。 经过一次单趟排序最终也能使得key左边的数据全部都小于keykey右边的数据全部都大于key。
然后也还是将key的左序列和右序列再次进行这种单趟排序如此反复操作下去直到左右序列只有一个数据或是左右序列不存在时便停止操作。
单趟的动图演示 上述递归实现的局限性可能在于 当数据量特别大时可能会导致栈溢出(栈涨的速度为logn也可能是我多虑了涨地其实挺慢的)。 为了解决上面可能出现的问题我们可以将递归实现转换为非递归实现我们知道任何递归的过程都可以转化为一个迭代的过程而转化的关键在于如何使用迭代来模拟整个递归的处理。 观察上面的递归处理过程我们可以看到每一次排序函数的调用都会再次重新调用两次新的排序函数然后系统会按照调用顺序一步一步地进行处理和返回而调用排序函数的关键在于必须将排序的范围告诉函数。
这个过程很像一个排队处理的过程于是我们可以使用队列进行递归的模拟而队列中的信息存储要处理的范围即可。当队列不为空时表示还有范围未处理队列为空时表示所有的范围都已经处理完毕也即确定了所有元素的位置完成了排序工作。 我们利用栈的相关思想来进行实现 void QuickSortNonR(int* a, int left, int right)
{
Stack st;
StackInit(st);
StackPush(st, left);
StackPush(st, right);
while (StackEmpty(st) ! 0)
{right StackTop(st);StackPop(st);left StackTop(st);StackPop(st);if(right - left 1)continue;int div PartSort1(a, left, right);// 以基准值为分割点形成左右两部分[left, div) 和 [div1, right)StackPush(st, div1);StackPush(st, right);StackPush(st, left);StackPush(st, div);
}StackDestroy(s);
}快速排序算法的性能分析如下 空间效率由于快速排序是递归的需要借助一个递归工作找来保存每层递归调用的必要信息其容量应与递归调用的最大深度一致。最好情况下为 O ( logzn )最坏情况下因为要进行 n - l 次递归调用所以栈的深度为 O ( n )平均情况下栈的深度为 O ( logn)。
时间效率快速排序的运行时间与划分是否对称有关快速排序的最坏情况发生在两个区域分别包含 n -1个元素和0个元素时这种最大限度的不对称性若发生在每层递归上即对应于初始排序表基本有序或基本逆序时就得到最坏情况下的时间复杂度为 O ( n^2)。
有很多方法可以提高算法的效率 一种方法是尽量选取一个可以将数据中分的枢轴元素如从序列的头尾及中间选取三个元素再取这三个元素的中间值作为最终的枢轴元素 或者随机地从序列的头尾及中间选取三个元素再取这三个元素的中间值作为最终的枢轴元素有随机吧从当前表中选取枢轴元素这样做可使得最坏情况在实际排序中几乎不会发生。 在最理想的状态下即 Partition (可能做到最平衡的划分得到的两个子问题的大小都不可能大于 n /2在这种情况下快速排序的运行速度将大大提升此时时间复杂度为 O (nlog2n)。好在快速排序平均情况下的运行时间与其最佳情况下的运行时间很接近而不是接近其最坏情况下的运行时间。快速排序是所有内部排序算法中平均性能最优的排序算法。 稳定性在划分算法中若右端区间有两个关键字相同且均小于基准值的记录则在交换到左端区间后它们的相对位置会发生变化即快速排序是一种不稳定的排序方法。例如表 L (3,2,2)经过一趟排序后 L (2,2,3)最终排序序列也是 L (2,2,3)显然2与2的相对次序已发生了变化。
注意在快速排序算法中并不产生有序子序列但每趟排序后会将枢轴基准元素放到其最终的位置上。
2.4 归并排序
归并排序与上述基于交换、选择等排序的思想不一样归并的含义是将两个或两个以上的有序表组合成一个新的有序表。假定待排序表含有 n 个记录则可将其视为 n 个有序的子表每个子表的长度为1然后两两归并得到「 n /27个长度为2或」的有序表继续两两归并…如此重复直到合并成一个长度为 n 的有序表为止这种排序方法称为2路归并排序。
两路归并核心步奏 作为一种典型的分而治之思想的算法应用归并排序的实现由两种方法 自上而下的递归所有递归的方法都可以用迭代重写所以就有了第 2 种方法 自下而上的迭代 以下为一个两路归并的例子 算法步骤 申请空间使其大小为两个已经排序序列之和该空间用来存放合并后的序列 设定两个指针最初位置分别为两个已经排序序列的起始位置 比较两个指针所指向的元素选择相对小的元素放入到合并空间并移动指针到下一位置 重复步骤 3 直到某一指针达到序列尾 将另一序列剩下的所有元素直接复制到合并序列尾。 递归版本
// 时间复杂度O(N*logN)
// 空间复杂度O(N)
// [begin, end]
void _MergeSort(int* a, int begin, int end, int* tmp)
{if (begin end)return;int mid (begin end) / 2;// [begin, mid] [mid1, end] 递归让子区间有序_MergeSort(a, begin, mid, tmp);_MergeSort(a, mid1, end, tmp);// 归并[begin, mid] [mid1, end]//...int begin1 begin, end1 mid;int begin2 mid1, 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, sizeof(int)*(end - begin 1));
}void MergeSort(int* a, int n)
{int* tmp (int*)malloc(sizeof(int)*n);if (tmp NULL){perror(malloc fail);exit(-1);}_MergeSort(a, 0, n - 1, tmp);free(tmp);tmp NULL;
}非递归版本
归并排序的非递归算法并不需要借助栈来完成我们只需要控制每次参与合并的元素个数即可最终便能使序列变为有序 当然以上例子是一个待排序列长度比较特殊的例子我们若是想写出一个广泛适用的程序必定需要考虑到某些极端情况 情况一 当最后一个小组进行合并时第二个小区间存在但是该区间元素个数不够gap个这时我们需要在合并序列时对第二个小区间的边界进行控制。 情况二 当最后一个小组进行合并时第二个小区间不存在此时便不需要对该小组进行合并。 情况三 当最后一个小组进行合并时第二个小区间不存在并且第一个小区间的元素个数不够gap个此时也不需要对该小组进行合并。 只要把控好这三种特殊情况写出归并排序的非递归算法便轻而易举了。
代码如下
void MergeSortNonR(int* a, int n)
{int* tmp (int*)malloc(sizeof(int)*n);if (tmp NULL){perror(malloc fail);exit(-1);}// 归并每组数据个数从1开始因为1个认为是有序的可以直接归并int rangeN 1;while (rangeN n){for (int i 0; i n; i 2 * rangeN){// [begin1,end1][begin2,end2] 归并int begin1 i, end1 i rangeN - 1;int begin2 i rangeN, end2 i 2 * rangeN - 1;printf([%d,%d][%d,%d]\n, begin1, end1, begin2, end2);int j i;// end1 begin2 end2 越界// 修正区间 -拷贝数据 归并完了整体拷贝 or 归并每组拷贝if (end1 n){end1 n - 1;// 不存在区间begin2 n;end2 n - 1;}else if (begin2 n){// 不存在区间begin2 n;end2 n - 1;}else if (end2 n){end2 n - 1;}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, tmp, sizeof(int)*(n));rangeN * 2;}free(tmp);tmp NULL;
} 动态图展示 2路归并排序算法的性能分析如下 空间效率 Merge (操作中辅助空间刚好为 n 个单元所以算法的空间复杂度为 O ( n )。 时间效率每趟归并的时间复杂度为 O ( n )共需进行「 logznl 趟归并所以算法的时间复杂度为 O ( nlogn ). 稳定性由于 Merge (操作不会改变相同关键字记录的相对次序所以2路归并排序算法是一种稳定的排序方法。 2.5 计数排序
思想 计数排序又称为鸽巢原理是对哈希直接定址法的变形应用。 顾名思义该算法不是通过比较数据的大小来进行排序的而是通过统计数组中相同元素出现的次数然后通过统计的结果将序列回收到原来的序列中。操作步骤
统计相同元素出现次数根据统计的结果将序列回收到原来的序列中 计数排序的特征 当输入的元素是 n 个 0 到 k 之间的整数时它的运行时间是 Θ(n k)。计数排序不是比较排序排序的速度快于任何比较排序算法。由于用来计数的数组C的长度取决于待排序数组中数据的范围等于待排序数组的最大值与最小值的差加上1这使得计数排序对于数据范围很大的数组需要大量时间和内存。 注计数排序只适用于数据范围较集中的序列的排序若待排序列的数据较分散则会造成空间浪费并且计数排序只适用于整型排序不适用与浮点型排序。 算法的步骤如下 1找出待排序的数组中最大和最小的元素 2统计数组中每个值为i的元素出现的次数存入数组C的第i项 3对所有的计数累加从C中的第一个元素开始每一项和前一项相加 4反向填充目标数组将每个元素i放在新数组的第C(i)项每放一个元素就将C(i)减去1
动态展示
代码如下
//计数排序
void CountSort(int* a, int n)
{int min a[0];//记录数组中的最小值int max a[0];//记录数组中的最大值for (int i 0; i n; i){if (a[i] min)min a[i];if (a[i] max)max a[i];}int range max - min 1;//min和max之间的自然数个数包括min和max本身int* count (int*)calloc(range, sizeof(int));//开辟可储存range个整型的内存空间并将内存空间置0if (count NULL){printf(malloc fail\n);exit(-1);}//统计相同元素出现次数相对映射for (int i 0; i n; i){count[a[i] - min];}int i 0;//根据统计结果将序列回收到原来的序列中for (int j 0; j range; j){while (count[j]--){a[i] j min;}}free(count);//释放空间
}计数排序算法的性能分析如下 计数排序在数据范围集中时效率很高但是适用范围及场景有限。时间复杂度O(MAX(N,范围))空间复杂度O(范围)稳定性稳定
3.各种内部排序算法比较及运用
3.1内部排序算法的比较 前面讨论的排序算法很多对各算法的比较也是爱考的内容。一般基于三个因素进行对比时空复杂度、算法的稳定性、算法的过程特征。 从时间复杂度看 简单选择排序、直接插入排序和冒泡排序平均情况下的时间复杂度都为 O ( n^2)且实现过程也较简单.
直接插入排序和冒泡排序最好情况下的时间复杂度可以达到 O ( n )
而简单选择排序则与序列的初始状态无关。 希尔排序作为插入排序的拓展对较大规模的排序都可以达到很高的效率但目前未得出其精确的渐近时间。 堆排序利用了一种称为堆的数据结构可在线性时间内完成建堆且在 O ( nlogn 内完成排序过程。
快速排序基于分治的思想虽然最坏情况下快速排序时间会达到 O ( n )但快速排序平均性能可以达到 O ( nlogn )在实际应用中常常优于其他排序算法。
归并排序同样基于分治的思想但由于其分割子序列与初始序列的排列无关因此它的最好、最坏和平均时间复杂度均为 O ( nlogn )。 从空间复杂度看 简单选择排序、插入排序、冒泡排序、希尔排序和堆排序都仅需要借助常数个辅助空间。
快速排序在空间上只使用一个小的辅助栈用于实现递归平均情况下大小为 O ( logn )当然在最坏情况下可能会增长到 O ( n )。
2路归并排序在合并操作中需要借助较多的辅助空间用于元素复制大小为 O ( n )虽然有方法能克服这个缺点但其代价是算法会很复杂而且时间复杂度会增加。 从稳定性看插入排序、冒泡排序、归并排序和基数排序是稳定的排序方法而简单选择排序、快速排序、希尔排序和堆排序都是不稳定的排序方法。平均时间复杂度为 O ( nlogn 的稳定排序算法只有归并排序对于不稳定的排序方法只要举出一个不稳定的实例即可。对于排序方法的稳定性小伙伴们应能从算法本身的原理上去理解而不应拘泥于死记硬背。
排序算法复杂度及稳定性分析
3.2内部排序算法的运用
通常情况对排序算法的比较和应用应考虑以下情况。 1选取排序方法需要考虑的因素 ①待排序的元素数目 n ②元素本身信息量的大小。 ③关键字的结构及其分布情况。 ④稳定性的要求。 ⑤语言工具的条件存储结构及辅助空间的大小等。 2排序算法小结 ①若 n 较小可采用直接插入排序或简单选择排序。由于直接插入排序所需的记录移动次数较简单选择排序的多因而当记录本身信息量较大时用简单选择排序较好。
②若文件的初始状态已按关键字基本有序则选用直接插入或冒泡排序为宜。
③若 n 较大则应采用时间复杂度为 O ( nlogn 的排序方法【快速排序、堆排序或归并排序】。快速排序被认为是目前基于比较的内部排序方法中最好的方法当待排序的关键字随机分布时快速排序的平均时间最短。堆排序所需的辅助空间少于快速排序并且不会出现快速排序可能出现的最坏情况这两种排序都是不稳定的。若要求排序稳定且时间复杂度为 O ( nlogn )则可选用归并排序。
④在基于比较的排序方法中每次比较两个关键字的大小之后仅出现两种可能的转移因此可以用一棵二叉树来描述比较判定过程由此可以证明当文件的 n 个关键字随机分布时任何借助于比较的排序算法至少需要 O ( nlogn / n 的时间。
⑥若 n 很大记录的关键字位数较少所可以分解时采用基数排序较好。
⑥当记录本身信息量较大时为避免耗费大量时间移动记录可用链表作为存储结构。
4 选择题讲解
1.有字符序列 FBJGEAIDCH现在打算对它按字母的字典顺序用希尔排序进行排序那么在第一趟后步长为5的序列为 A.CAEBFDIGJH B.AIDCHFBJGE C.ABDCEFIJGH D.BFJGEAIDCH
解答 希尔排序按照步长把元素进行小组划分每个小组元素进行插入排序。 所以如果步长为5则整个数组被会划分成5组数据 FA BI JD GC EH 所以一趟排序之后的结果为 ABDCEFIJGH 所以选C 2.下列排序方法中每一趟排序结束时都至少能够确定一个元素最终位置的方法是
① 选择排序 ② 归并排序 ③ 快速排序 ④ 堆排序
A.①④ B.①②④ C.①③④ D.①②③④
解析 选择排序每次选一个最值放在最终的位置 快速排序每次基准值的位置也可以确定 堆排序每次堆顶元素的位置也可以确定 所以这三种方法都可以每次至少确定一个元素的位置 而归并排序每次都需要对n个元素重新确定位置所以不能保证每次都能确定一个元素位置有可能每次排序所有元素的位置都为发生变化。 所以选C 3.以下哪种排序算法对[1, 3, 2, 4, 5, 6, 7, 8, 9]进行排序最快 A.直接插入排序 B.快速排序 C.归并排序 D.堆排序
解析 次序列接近有序所以如果是插入排序时间复杂度逼近O(n) 快排 逼近O(n^2) 归并和堆排仍然是nlogn 所以选A 4.对数字序列28 16 32 12 60 2 5 72进行升序的快速排序以第一个关键码为基准的方法一次划分后的结果为 A.2 5 12 16 28 60 32 72 B.2 16 5 12 28 60 32 72 C.2 16 12 5 28 60 32 72 D.5 16 2 12 28 32 60 72
解析 快速排序以基准值为中心对元素进行划分这里以28为基准值则小于28的和大于28的进行交换完成一次划分 首先32和5交换 28 16 5 12 60 2 32 72 然后60和2交换 28 16 5 12 2 60 32 72 最后28和最后一个小于28的元素进行交换 2 16 5 12 28 60 32 725.使用选择排序对长度为100的数组进行排序则比较的次数为 A.5050 B.4950 C.4851 D.2475
解析 选择排序每次都要在未排序的所有元素中找到最值 如果有n个元素则 第一次比较次数 n - 1 第二次比较次数 n - 2 … 第n - 1次比较次数 1 所有如果n 100 则比较次数的总和99 98 … 1 共4950次。 好了小伙伴们以上就是排序的全部知识内容了。如果对大家有帮助希望多多支持哟
