Java教程

数据结构复习之排序

本文主要是介绍数据结构复习之排序,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

目录

基本概念

插入排序

直接插入排序

希尔排序

交换排序

起泡排序

快速排序

 选择排序

简单选择排序

 堆排序

归并排序


基本概念

排序:将记录排列成某种顺序的序列。
(将任一个记录的任意序列重新排列成一个按关键码有序的序列。)

内排序:待排序的所有记录全部被放置再内存中。
外排序:待排序记录个数太多,不能同时放在内存内,一部分放在外存。

插入排序、交换排序、选择排序、归并排序

稳定性:稳定:经过排序,多个具有相同关键码的相对次序保持不变。

正序:待排序记录序列已经排好序。 逆序(反序):与排好的顺序正好相反。

插入排序

直接插入排序

插入排序中最简单的排序方法。
想想打牌!!!
从无序区的第一个记录插入有序区的合适位置中。

最好情况的时间复杂度:O(n)  最坏情况:O(n2)   平均时间复杂度:O(n2) 
只需要一个记录的辅助空间暂存待插记录。  稳定。

若待排记录基本有序,直接插入的效率很高。待排序记录个数较少时效率也高。

希尔排序

对直接插入排序的改进。
基本思想:分割整体成若干个子序列,再在子序列内分别进行直接插入排序,待整个序列基本有序时再对全体记录进行一次直接插入排序。

增量序列,d=n/2  ......依次递推,增量序列互质且递减,最后一个增量必须为1。

 时间性能在O(nlog2n)&O(n2)之间。只需一个记录的辅助空间。 不稳定

交换排序

起泡排序

交换排序中最简单的排序方法。
基本思想:两两比较相邻记录,若反序则交换,直到没有反序的记录为止。
对无序区从前向后依次将相邻记录比较,值较小的记录向前移,值较大的记录向后移。

执行时间取决于排序趟数。
最好:只执行一趟,O(n)  最坏:O(n2)  只需一个记录的辅助空间,稳定。

快速排序

先选一个轴值(比较基准),划分待排序的记录。左侧<=轴值,右侧>=轴值。重复,直到序列有序。
选取轴值最简单的时选取第一个记录,最后一个记录和中间记录。

 选择排序

简单选择排序

最简单的选择排序

基本思想:第i趟排序在待排序序列中选取最小的记录,并和第i个记录交换作为有序序列的第i个记录。
初始时有序区为空,不断重复上述步骤直到无序区只剩下一个记录。

 

待排序列为正序,移动0次,待排序列为逆序,移动3(n-1)次

最好=最坏=平均=O(n2),只需一个作为记录交换的暂存单元。 不稳定。

 堆排序

完全二叉树

小根堆:每个结点的值小于或等于左右孩子结点的值。
大根堆:每个结点的值大于或等于左右孩子结点的值。

一个完全二叉树如果是堆,则根结点(堆顶)一定是当前所有结点的最大者或最小者。以结点的编号作为下标,将堆用顺序存储结构存储。

运行时间主要消耗在初始建堆&重建堆时进行的堆的调整。
初始建堆O(nlog2n),第i次重建堆O(log2i)。
总的时间复杂度:O(nlog2n)
堆排序对排序的初始状态不敏感(相对于快速排序的最大优点)
只用一个用来交换的暂存单元,不稳定。

归并排序

将待排序序列划分为两个长度相等的子序列,分别对两个子序列排序,再合并。

 时间复杂度:O(nlog2n) ,空间复杂度:O(n), 稳定

//大概写了一点简单的,凑合看看8!

这篇关于数据结构复习之排序的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!