排序算法

排序算法

排序的基本概念:

排序:给定一组记录的集合{r1, r2, ……, rn},其相应的关键码分别为{k1, k2, ……, kn},排序是将这些记录排列成顺序为{rs1, rs2, ……, rsn}的一个序列,使得相应的关键码满足ks1≤ks2≤……≤ksn(称为升序)或ks1≥ks2≥……≥ksn(称为降序)。
正序:待排序序列中的记录已按关键码排好序。
逆序(反序):待排序序列中记录的排列顺序与排好序的顺序正好相反。
:在排序过程中,将待排序的记录序列扫描一遍称为一趟。通常,一次排序过程需要进行多趟扫描才能完成

排序算法的稳定性:

假定在待排序的记录集中,存在多个具有相同键值的记录,若经过排序,这些记录的相对次序仍然保持不变,即在原序列中,ki=kj且ri在rj之前,而在排序后的序列中,ri仍在rj之前,则称这种排序算法是稳定的;否则称为不稳定的。

对于不稳定的排序算法,只要举出一个实例,即可说明它的不稳定性;而对于稳定的排序算法,必须对算法进行分析从而证明稳定的特性。

排序算法是否为稳定的是由具体算法决定的:
不稳定的算法在某种条件下可以变为稳定的算法,
而稳定的算法在某种条件下也可以变为不稳定的算法。

稳定性比较:
所有排序方法可分为两类,
(1)一类是稳定的,包括直接插入排序、起泡排序、和归并排序,基数桶式排序;
(2)另一类是不稳定的,包括直接选择排序、希尔排序、快速排序和堆排序。

排序的分类:

排序的分类——根据排序数据在内存中还是在外存中:
1.内排序:在排序的整个过程中,待排序的所有记录全部被放置在内存中
2. 外排序:由于待排序的记录个数太多,不能同时放置在内存,而需要将一部分记录放置在内存,另一部分记录放置在外存上,整个排序过程需要在内外存之间多次交换数据才能得到排序的结果。

排序的分类——根据排序过程中所进行的基本操作分类:
1. 基于比较:基本操作——关键码的比较和记录的移动,其最差时间下限已经被证明为O(nlog2n)。
2. 不基于比较:根据关键码的分布特征。比如,桶式排序,基数排序(多关键字排序)
基于比较的内排序
1. 插入排序
2. 交换排序
3. 选择排序
4. 归并排序
不基于比较的内排序
1. 分配排序
2.桶式排序
3.基数排序

算法简单性比较:
从算法简单性看,
(1)一类是简单算法,包括直接插入排序、直接选择排序和起泡排序,
(2)另一类是改进后的算法,包括希尔排序、堆排序、快速排序、归并排序和基数排序,这些算法相对比较复杂。

时空复杂度比较:

时间复杂度比较:(基本操作)(内排序在排序过程中的基本操作:⑴比较:关键码之间的比较;⑵移动:记录从一个位置移动到另一个位置。 )
在这里插入图片描述
空间复杂度比较:(辅助存储空间)(在数据规模一定的条件下,除了存放待排序记录占用的存储空间之外,执行算法所需要的其他存储空间。)
在这里插入图片描述

原文地址:https://www.cnblogs.com/study-hard-forever/p/12129978.html