图解数据结构---“内部排序”综述

港控/mmm° 2022-05-18 09:17 248阅读 0赞

# **《图解数据结构---“内部排序”综述》** #

## **一、为什么我们要进行排序？** ##

**在当今社会里，我们经常面临要在浩如烟海的信息中查找某条信息。要使这种查找操作有效、快速，就必须按照某种合理的次序存储信息。**例如，如图书馆的书籍及文献资料不是分门别类地存储，我们如何能迅速找到自己所需借阅的资料？又比如，英文字典若不是按照字母顺序排列词条，我们如何快速查找所需单词？

![1351683246_1766.jpg][]

**图书馆书籍按类存放**

![1351683262_6730.jpg][]

**字典按字母顺序排列词条**

## **二、我们什么情况下需要排序？** ##

很多情况下，是否使用排序是一个重要的策略问题。《孙子兵法》阐述，战争的最高境界是：**不战而屈人之兵**；那么排序的最高境界就是：**不排序**。

> 1. **为了方便取得数据**：那么Hash才是最佳的选择，因为如果使用好的解决Hash冲突方法，能够做到1+a/2 时间内取得数据，其中a为Hash表的填装因子。这远远好于二分查找带给你的logn时间复杂度。当然，你别想在Hash表找最大值，最小值，或者最大的10个数之类的问题，如果你需要这些操作，Hash不应该是你的选择。但通常情况下，人们存放用户数据的时候，往往关心的是如何取出而已。这种单纯的存取关系下，Hash绝对是最好的选择！

> 2. **非重复关键字数据**：其实现实生活中这种情况是非常多见的，例如电话号码、身份证数据，他们往往可以成为关键字，而且排序往往是有意义的。如电话号码中0826可能是某个特定的地区，身份证511可能有特定的含义，对这些数据的如果是有序的，往往可以从中取得有用的信息。

> 3.**大规模频繁变更数据排序**：有时候我们存了相当大规模的数据， 而且随时可能有新的数据插入进来，或者旧的数据需要更新值，而我们又需要这个数据集是有序的，于是我们会经常调用排序算法来排序。这个大规模数据的情况下，性能往往是关键而敏感的，于是我们开始疯狂的优化排序算法。我们开始尝试各种混合优化排序方法，以期能够提升整个程序的性能。
> 
>   
>

## **三、排序的一些基本概念** ##

> **1.排序**：就是要整理文件中的记录，使之按关键字递增(或递减)次序排列起来。

> **其确切定义**：输入：n个记录R1，R2，…，Rn，其相应的关键字分别为K1，K2，…，Kn。
> 
>             输出：Ril，Ri2，…，Rin，使得Ki1≤Ki2≤…≤Kin。(或Ki1≥Ki2≥…≥Kin)。

> > >    因此，排序算法就是要确定1,2，…，n的一种排列i1,i2，…，in，使文件中的记录一次排列整理后按关键字有序。

> **2.稳定排序**
> 
> 假设待排序序列中有两个元素相等，而且在排序前和排序后两个相等的元素的相对位置不变，即有 a = b，排序前a在b前面，那么排序后，a还是要在b前面，则称这样的**排序为稳定的**。
> 
> 排序算法的稳定性是要看具体的算法实现，比如一般情况下，直接选择排序，快速排序，希尔排序，堆排序都不是稳定排序算法，基数排序，计数排序，归并排序，插入排序，冒泡排序都是稳定排序算法。

> > 快速排序：A = \{ 2， 2， 1\}，排序后A = \{1，2，2\}→**不稳定**
> 
> > 希尔排序：A = \{1，2，5，4，4，7\}，排序后（k = 2）；A = \{1， 2， 4， 4， 5， 7\} →**不稳定**
> 
> > 堆排序：A = \{ 2，2，1\}，排序后A = \{1，2，2\}→**不稳定**
> 
> > 直接选择排序： A = \{ 4， 4， 2， 5\},排序后 A = \{2，4，4， 5\}→**不稳定**
> 
> >

> **3.被排序对象--文件**
> 
> **  **被排序的对象--文件由一组**记录**组成。

>   记录则由若干个**数据项(或域)**组成。其中有一项可用来标识一个记录，称为**关键字项**。该数据项的值称为关键字(Key)。

**     注意：****在不易产生混淆时，将关键字项简称为关键字。**

** **

> **4.排序运算的依据--关键字**

**   **    用来作排序运算依据的关键字，可以是**数字类型**，也可以是**字符类型**。

**关键字的选取应根据问题的要求而定。**

> **【例】**在高考成绩统计中将每个考生作为一个记录。每条记录包含准考证号、姓名、各科的分数和总分数等项内容。若要惟一地标识一个考生的记录，则必须用"准考证号"作为关键字。若要按照考生的总分数排名次，则需用"总分数"作为关键字。

> **5.就地排序**

若排序算法所需的辅助空间并不依赖于问题的规模n,也就是说辅助空间是O(1)，则称之为就地排序。

## **四、排序算法分析** ##

> **1.排序算法的基本操作**

大多数排序算法都有两个基本的操作：(1) 比较两个关键字的大小；

> > >                           (2)改变指向记录的指针或移动记录本身。

>   **注意**：第(2)种基本操作的实现依赖于待排序记录的存储方式。
> 
>   
>

> **2. 排序算法性能评价**
> 
> （1）评价排序算法好坏的标准

>     　① 执行时间和所需的辅助空间
> 
>     　② 算法本身的复杂程度

> （2） 排序算法的空间复杂度

> > 若排序算法所需的辅助空间并不依赖于问题的规模n，即辅助空间是O(1)，则称之为就地排序(In-PlaceSou)。

> > 非就地排序一般要求的辅助空间为O(n)。

> （3） 排序算法的时间开销

> > 大多数排序算法的时间开销主要是关键字之间的比较和记录的移动。有的排序算法其执行时间不仅依赖于问题的规模，还取决于输入实例中数据的状态。

## **五、常用排序算法汇聚** ##

> 内部排序按照所使用的策略可以分为5大类，分别是

![1351687733_8142.jpg][]

## **六、简述各类排序的特征** ##

![1351683321_1108.jpg][]

## **七、影响排序效果的因素** ##

> 因为不同的排序方法适应不同的应用环境和要求，所以选择合适的排序方法应综合考虑下列因素：

> > ①待排序的记录数目n；
> 
> > ②记录的大小(规模)；
> 
> > ③关键字的结构及其初始状态；
> 
> > ④对稳定性的要求；
> 
> > ⑤语言工具的条件；
> 
> > ⑥存储结构；
> 
> > ⑦时间和辅助空间复杂度等。

## **八、各类排序详述链接** ##

> **《[选择排序][Link 1]》：直接选择排序、堆排序**
> 
> **《[插入排序][Link 2]》：直接插入排序、希尔排序**
> 
> **《[交换排序][Link 3]》：冒泡排序、快速排序**
> 
> **《[分配排序][Link 4]》：箱排序、基数排序**
> 
> **《[归并排序][Link 5]》**

[1351683246_1766.jpg]: https://img-my.csdn.net/uploads/201210/31/1351683246_1766.jpg
[1351683262_6730.jpg]: https://img-my.csdn.net/uploads/201210/31/1351683262_6730.jpg
[1351687733_8142.jpg]: https://img-my.csdn.net/uploads/201210/31/1351687733_8142.jpg
[1351683321_1108.jpg]: https://img-my.csdn.net/uploads/201210/31/1351683321_1108.jpg
[Link 1]: http://blog.csdn.net/mazhaojuan/article/details/8126608
[Link 2]: http://blog.csdn.net/mazhaojuan/article/details/8122122
[Link 3]: http://blog.csdn.net/mazhaojuan/article/details/8122889
[Link 4]: http://blog.csdn.net/mazhaojuan/article/details/8127522
[Link 5]: http://blog.csdn.net/mazhaojuan/article/details/8125698