如题所述
内排序:是在排序整个过程中,待排序的所有记录全部被放置在内存中;
外排序:由于排序的记录个数太多,不不能同时放置在内存,整个排序过程需要在内外存 之间多次交换数据才能进⾏
1、顺序表结构
2、数据交换函数
3、数据打印
冒泡排序(Bubble Sort) 一种交换排序,它的基本思想就是: 两两⽐比较相邻的记录的关键字,如果 反序则交换,直到没有反序的记录为⽌.
也可以反过来,每次都把最大的值放到末尾。
简单排序算法(Simple Selection Sort) 就是通过n-i次关键词比较,从n-i+1个记录中找出关键 字最小的记录,并和第i(1<=i<=n) 个记录进行交换.
总结一句话就是(划重点):从第一个位置开始比较,找出最小的,和第一个位置互换,开始下一轮。
(1)冒泡排序是比较相邻位置的两个数,而选择排序是按顺序比较,找最大值或者最小值;
(2)冒泡排序每一轮比较后,位置不对都需要换位置,选择排序每一轮比较都只需要换一次位置;
(3)冒泡排序是通过数去找位置,选择排序是给定位置去找数;
冒泡排序优缺点:优点:比较简单,空间复杂度较低,是稳定的;
缺点:时间复杂度太高,效率慢;
选择排序优缺点:优点:一轮比较只需要换一次位置;
缺点:效率慢,不稳定(举个例子5,8,5,2,9 我们知道第一遍选择第一个元素5会和2交换,那么原序列中2个5的相对位置前后顺序就破坏了)。
直接插入排序算法(Stright Insertion Sort)的基本操作是将一个记录插入到已经排好序的有序表 中,从而得到一个新的,记录数增1的有序表;
步骤1、将数据插入到有序表中与前一个比较,如果大于则不改变位置
2、如果插入数据小于前一个数据,则前面大的数据依次往后移动,然后找到合适位置插入该数据。
空间复杂度: O(1) 解读:在直接插⼊入排序中只使⽤用了了i,j,temp这三个辅助元素,与问题规模⽆无关,空间复杂度为O(1)
时间复杂度: O(n2)
希尔排序思想: 希尔排序是把记录按下标的一定增量分组,对每组使用直接插⼊排序算法排 序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减⾄1时,整个序列恰被分成 一组,算法便终止.
其实就是分治法升级版的插入排序,又称为缩小增量排序。我们不断减半增量,直到增量为1时,退化为普通插入排序。
希尔排序通过增量进行了分组(分治),比较的是L->r[j-increment]和L->[j],跨度是increment,如果摸到的是较小的牌,只需要移动1次,而插入排序需要移动increment次。
也就是说希尔排序的优势是,能让较小的牌更容易来到数组的前面部分,节约了移动次数。
需要注意的是:
由于多次插入排序,我们知道一次插入排序是稳定的,不会改变相同元素的相对顺序,但在不同的插入排序过程中,相同的元素可能在各自的插入排序中移动,最后其稳定性就会被打乱,所以希尔排序是不稳定的。
每个结点的值都大于或等于其左右孩子结点的值,称为大顶堆。
或者
每个结点的值都小于或等于其左右孩子结点的值,称为小顶堆。
如下图1为大顶堆:
下图为小顶堆:
我们用简单的公式来描述一下堆的定义就是:
大顶堆: arr[i] >= arr[2i] && arr[i] >= arr[2i+1]
小顶堆: arr[i] <= arr[2i] && arr[i] <= arr[2i+1]
1、用待排序序列构造一个大顶堆。
2、将其与末尾元素进行交换,此时末尾就为最大值。
3、然后将剩余n-1个元素重新构造成一个堆,这样会得到n个元素的次小值。
4、如此反复执行,便能得到一个有序序列了。
我们可以发现其实堆排序还是一种选择排序,用一句话概括思想:
利用堆结构特性,不断选出最大值,放到最后。
归并排序(Merging Sort) 就是利利⽤用归并的思想实现排序⽅方法. 它的原理理是假设初始序 列列含有n个记录,则可以看成n个有序的⼦子序列列. 每个⼦子序列列的⻓长度为1,然后两两合并.得 到[n/2]个⻓长度为2或1的有序⼦子序列列, 再两两归并. ......如此重复,直到得到⼀一个⻓长度为n 的有序序列列为此. 这种排序⽅方法称为2路路归并排序
归并排序是利用归并的思想实现的排序方法,该算法采用经典的分治策略。
将问题分成一些小的问题然后递归求解,而治的阶段则将分的阶段得到的各答案"修补"在一起。
进行合并时,我们需要一个额外的数组来进行辅助排序,再回填回原数组。
//6归并排序
首先设定一个分界值,通过该分界值将数组分成左右两部分。
将大于或等于分界值的数据集中到数组右边,小于分界值的数据集中到数组的左边。
此时,左边部分中各元素都小于或等于分界值,而右边部分中各元素都大于或等于分界值。
左边和右边的数据可以独立排序。对于左侧的数组数据,又可以取一个分界值,将该部分数据分成左右两部分,同样在左边放置较小值,右边放置较大值。右侧的数组数据也可以做类似处理。
重复上述过程,可以看出,这是一个递归定义。通过递归将左侧部分排好序后,再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后,整个数组的排序也就完成了。