m数据结构 day23 排序（一）总述7种排序算法

小鱼儿 2023-03-12 07:08 43阅读 0赞

### 文章目录 ###

*  总述：每种排序算法都有自己的价值和发光舞台
 *  排序的稳定性
 *  内排序，外排序：排序时数据记录是否全在内存中
 *   *  内排序算法的性能的影响因素
     *   *  时间性能：衡量排序算法好坏最重要的标志
         *  辅助空间：执行算法需要的其他空间，即除了存放待排序数据空间之外的空间
         *  算法本身的复杂性
 *  内排序的四个大类
 *   *  插入排序类
     *   *  直接插入排序， O ( n 2 ) O(n^2) O(n2)，但略优于简单选择排序
         *  希尔排序，直接插入排序的改进版， O ( n log ⁡ n ) O(n\\log n) O(nlogn)
     *  选择排序类
     *   *  简单选择排序, O ( n 2 ) O(n^2) O(n2)，但略优于冒泡
         *  堆排序：简单选择排序的改进版， O ( n log ⁡ n ) O(n \\log n) O(nlogn)
         *   *  优缺点
     *  交换排序类
     *   *  冒泡排序：最简单， O ( n 2 ) O(n^2) O(n2)
         *  快速排序：真正的高手，目前排序界绝对的王者，冒泡排序的改进版， O ( n log ⁡ n ) O(n \\log n) O(nlogn)
         *  先给他吹爆
         *   *  优缺点
     *  归并排序类
     *   *  归并排序， O ( n log ⁡ n ) O(n \\log n) O(nlogn)
         *   *  优缺点
 *  代码准备
 *   *  被排序的一个顺序表结构
     *  数组两个元素的交换

# 总述：每种排序算法都有自己的价值和发光舞台 #

排序算法的优秀与否的首要判定条件：速度！

排序的依据：关键字的大小关系

排序可以看做是**线性表的一种操作**。因为所有的排序，就算你对树和图的元素排序，排序结果一定是一个线性表。

排序是数据处理中一种非常频繁的操作，而且一般都**属于系统的核心部分**。

所有排序目前可以分为四个大类  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70 2]  
![在这里插入图片描述][20200515225702794.png]![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70 3]

# 排序的稳定性 #

如果针对主关键字的大小对数据记录排序，则排序结果是唯一的，确定的。

但是如果针对次关键字排序，由于不同数据的次关键字可能相同，所以次关键字相同的数据记录们的顺序，在排序前和排序后可能会变，也可能不变。

根据次关键字相同的记录们的顺序在排序前后是否相同，我们定义了稳定排序和不稳定排序。

![在这里插入图片描述][20200526212256904.png]  
说了半天，不如下面这张图表达的清楚，一看就明白了

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70 4]

# 内排序，外排序：排序时数据记录是否全在内存中 #

![在这里插入图片描述][20200526212559859.png]  
当然还是内排序用的多。

外排序考虑时间复杂度时，要复杂一些，除了比较和移动操作的次数之外，还需要考虑硬盘访问时间。

## 内排序算法的性能的影响因素 ##

### 时间性能：衡量排序算法好坏最重要的标志 ###

内排序中，主要有两种操作：

*  比较：关键字之前的比较，最起码的操作
 *  移动：把记录从一个位置移动到另一个位置。但是，移动操作可以通过改变记录存储方式来避免，去看具体的算法。

排序算法需要用的比较和移动越少越好

### 辅助空间：执行算法需要的其他空间，即除了存放待排序数据空间之外的空间 ###

### 算法本身的复杂性 ###

# 内排序的四个大类 #

这都是非常成熟的排序技术，已经广泛用于很多程序语言和数据库中（很多语言和数据库都封装了这些排序算法的代码）

所以我们学这些排序算法，说实话并不是为了学习怎么写他们的实现代码，而是为以后解决更多复杂而灵活的应用问题做准备。

## 插入排序类 ##

### 直接插入排序， O ( n 2 ) O(n^2) O(n2)，但略优于简单选择排序 ###

insertion sort

### 希尔排序，直接插入排序的改进版， O ( n log ⁡ n ) O(n\\log n) O(nlogn) ###

Shell sort,1959年由D.L.Shell提出。

前面三种排序都是 O ( n 2 ) O(n^2) O(n2),计算机学界一度以为排序算法不可能突破 O ( n 2 ) O(n^2) O(n2)的时间复杂度，直到希尔排序的出现。

## 选择排序类 ##

### 简单选择排序, O ( n 2 ) O(n^2) O(n2)，但略优于冒泡 ###

selection sort

### 堆排序：简单选择排序的改进版， O ( n log ⁡ n ) O(n \\log n) O(nlogn) ###

heap sort

由Floyd和Williams在1964年共同发明，同时他们发明了"堆"这种数据结构。堆是一种特殊的完全二叉树。这个数据结构本身就很复杂，能想出这样的结构真的不容易。

![在这里插入图片描述][20200515223751260.png]

#### 优缺点 ####

*  缺点：不稳定，因为记录的比较和交换是跳跃式进行；不适合待排序序列个数较少的情况

## 交换排序类 ##

### 冒泡排序：最简单， O ( n 2 ) O(n^2) O(n2) ###

![在这里插入图片描述][20200515223023140.png]

### 快速排序：真正的高手，目前排序界绝对的王者，冒泡排序的改进版， O ( n log ⁡ n ) O(n \\log n) O(nlogn) ###

Quick sort

如果他不是王者，那就不能叫这个名字了，谁能忍受一个不是最快的算法叫自己快速xx？？

### 先给他吹爆 ###

![在这里插入图片描述][20200515224500198.png]![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70 5]

![在这里插入图片描述][20200515224907138.png]

#### 优缺点 ####

*  优点：空间复杂度也小， O ( log ⁡ n ) O(\\log n) O(logn)
 *  缺点：不稳定，因为关键字的比较和交换是跳跃进行的。

## 归并排序类 ##

### 归并排序， O ( n log ⁡ n ) O(n \\log n) O(nlogn) ###

Merging Sort

更直接简单地利用完全二叉树来排序。一般只要用到了完全二叉树的排序算法，效率都不会低。

#### 优缺点 ####

*  优点：效率高，稳定
 *  缺点：由于大量使用递归，所以占用内存高，空间复杂度是 O ( n + log ⁡ n ) O(n + \\log n) O(n\+logn)。

所以我们在使用归并排序的时候，应该尽量使用迭代的方法（空间复杂度只是 O ( n ) O(n ) O(n)，时间性能也有一定提升）实现，而不要用递归的方式实现。

# 代码准备 #

都是之后所有排序都要用的代码。

## 被排序的一个顺序表结构 ##

#define MAXSIZE 10
    typedef struct
    { 
    	int r[MAXSIZE + 1];//存储待排序数组，r[0]用做哨兵
    	int length;//顺序表的长度
    }SqList;

## 数组两个元素的交换 ##

/*交换L中数组r中下标i的元素和下标j元素的值*/
    void swap(SqList * L, int i, int j)
    { 
    	int temp = L->r[i];
    	L->r[i] = L->r[j];
    	L->r[j] = temp;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70]: /images/20230312/3181ae6644c54c599973de2169682272.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200515225355354.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200515225633847.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0,size_16,color_FFFFFF,t_70
[20200515225702794.png]: https://img-blog.csdnimg.cn/20200515225702794.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200515225744198.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0,size_16,color_FFFFFF,t_70
[20200526212256904.png]: https://img-blog.csdnimg.cn/20200526212256904.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200526212328734.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0,size_16,color_FFFFFF,t_70
[20200526212559859.png]: https://img-blog.csdnimg.cn/20200526212559859.png
[20200515223751260.png]: https://img-blog.csdnimg.cn/20200515223751260.png
[20200515223023140.png]: https://img-blog.csdnimg.cn/20200515223023140.png
[20200515224500198.png]: https://img-blog.csdnimg.cn/20200515224500198.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20200515224602449.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0,size_16,color_FFFFFF,t_70
[20200515224907138.png]: https://img-blog.csdnimg.cn/20200515224907138.png