【数据结构】手撕排序NO.1----排序初识-Toy模板网

这篇具有很好参考价值的文章主要介绍了【数据结构】手撕排序NO.1----排序初识。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一. 前言

二. 排序的概念及运用

2.1 排序的概念

2.2 排序的运用

2.3 常见的排序算法

三. 冒泡and选择排序

3.1 冒泡排序

3.2 选择排序

四. 各大排序算法的复杂度和稳定性

一. 前言

从本期开始，我们的数据结构将迎来一个新的篇章：排序篇，啪叽啪叽【数据结构】手撕排序NO.1----排序初识,数据结构,数据结构,算法,排序算法,c语言,C++

排序是数据结构中非常重要的内容，在后续的内容中，我们会对各种各样的排序算法进行剖析和实现，敬请期待哦【数据结构】手撕排序NO.1----排序初识,数据结构,数据结构,算法,排序算法,c语言,C++

本期要点

对排序进行一个整体的认识

介绍一下两种最简单的排序

笼统地介绍一下各大排序算法的复杂度和稳定性

二. 排序的概念及运用

2.1 排序的概念

排序：所谓排序就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。排序算法，就是如何使得记录按照要求排列的方法。

稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。

内部排序：数据元素全部放在内存中的排序。

外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。

2.2 排序的运用

在日常生活中，我们可以找到许多和排序有关的场景。例如我们进入电脑磁盘右键就可以看到一个排序方式的选项，这是对我们电脑的磁盘文件进行排序，你可以根据需求选择不同排序方式进行排序【数据结构】手撕排序NO.1----排序初识,数据结构,数据结构,算法,排序算法,c语言,C++

【数据结构】手撕排序NO.1----排序初识,数据结构,数据结构,算法,排序算法,c语言,C++

又或者，随便打开一个网购网站/软件，例如京东，我们可以看到左上角就可以对商品的某一维度进行排序【数据结构】手撕排序NO.1----排序初识,数据结构,数据结构,算法,排序算法,c语言,C++

【数据结构】手撕排序NO.1----排序初识,数据结构,数据结构,算法,排序算法,c语言,C++

再或者，世界500强榜单也是经过排序后产生的【数据结构】手撕排序NO.1----排序初识,数据结构,数据结构,算法,排序算法,c语言,C++

【数据结构】手撕排序NO.1----排序初识,数据结构,数据结构,算法,排序算法,c语言,C++

总之，无论是在计算机的学习上还是现实生活中，排序都是非常重要的主题，其运用十分广泛，它无处不在

2.3 常见的排序算法

排序算法分为比较类排序和非比较类排序，如下图所示：

【数据结构】手撕排序NO.1----排序初识,数据结构,数据结构,算法,排序算法,c语言,C++

三. 冒泡and选择排序

本期我们先介绍一下我们的两个老朋友：冒泡排序和选择排序

3.1 冒泡排序

思想 : 在一个序列中，每次对序列中的相邻记录的键值大小进行比较，将较大(升序)或较小(降序)的记录向后移动。如此循环，大/小的记录会慢慢“浮”到序列的后端，整个过程就像是冒泡一样，顾称之为冒泡排序。
冒泡过程：以下是对某个序列进行冒泡排序的过程

【数据结构】手撕排序NO.1----排序初识,数据结构,数据结构,算法,排序算法,c语言,C++

可以看出，对于上面具有5个元素的无序数组，我们通过4趟的冒泡后就将其变为有序数组，每一趟冒泡后都可以使最大的数沉底。

动图演示：我们可以通过一下动图感受一下冒泡两两比较的过程：

【数据结构】手撕排序NO.1----排序初识,数据结构,数据结构,算法,排序算法,c语言,C++

循环控制：很明显，我们需要两层循环来控制冒泡排序的过程。内层循环控制当前趟的数据交换，外层循环控制冒泡排序的趟数。
外层循环结束条件：由于每一趟结束后都有一个数冒到序列后端，因此对于N个数的序列来说，一共需要N-1趟(只剩一个数不需要冒泡)。
```
	for (int i = 0; i < n - 1; i++) //外层循环，N-1趟
	{
        ;  
	}
```
内层循环结束条件：内层循环用于数据的比较。已知N个数据共需比较N-1次，由于每一趟结束后就有数据到正确的位置，下一趟需要比较的数据个数就会少1，因此每趟的比较次数随着趟数的增加呈递减趋势，初始为N-1次。
```
	for (int i = 0; i < n - 1; i++) //外层循环，N-1趟
	{
		for (int j = 0; j < n - 1 - i; j++) //内层循环，次数随趟数增加而递减，初始为N-1
		{
            ;
		}
	}
```

完整代码：

void swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
void BubblingSort(int* a, int n)
{

	for (int i = 0; i < n - 1; i++) //外层循环，N-1趟
	{
		for (int j = 0; j < n - 1 - i; j++) //内层循环，次数随趟数增加而递减，初始为N-1
		{
			if (a[j] > a[j + 1]) //升序排列，较大的往后移
			{
				swap(&a[j], &a[j + 1]); //交换
			}
		}
	}
}

改进优化：上面的代码还存在着改进空间，我们来看下面两个情景：

【数据结构】手撕排序NO.1----排序初识,数据结构,数据结构,算法,排序算法,c语言,C++

对于情境1，我们只需一趟冒泡即可让数组有序，而如果按照上面的代码，我们依旧要进行4趟的冒泡，即有三趟是无效的。

而情境1就更夸张了，数组已经有序，我们却傻乎乎的做了4趟无效冒泡。无疑是非常浪费时间的。

考虑到这些情况，我们提出了优化方案：在每趟结束后判断一下当前趟是否发生了元素交换，如果没有，则说明序列已经有序了，及时止损，反之继续。优化后的代码如下：
void swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

void BubblingSort(int* a, int n)
{
	for (int i = 0; i < n - 1; i++) //外层循环，N-1趟
	{
        int flag=0; //标识每一趟是否发生交换 0：没有  1：有
		for (int j = 0; j < n - 1 - i; j++) //内层循环，次数随趟数增加而递减，初始为N-1
		{
			if (a[j] > a[j + 1]) //升序排列，较大的往后移
			{
				swap(&a[j], &a[j + 1]); //交换
                flag = 1;
			}
		}
        //判断是否已经有序
        if(flag == 0)
        {
            break; //有序则退出循环
        }
	}
}

时间/空间复杂度：结合上面的图片和代码我们可以看出，总共N-1趟，每趟N-1，N-2...次比较，共比较 (N-1) + (N-2) + (N-3) + (N-4) + (N-5) + ...... + 1次，时间复杂度为；而由于没有额外的辅助空间，空间复杂度为。
稳定性分析：由于我们是将较大的或较小的进行交换，当两个数相等时并不会进行交换，因而不会改变相同元素的先后次序，所以冒泡排序是稳定的排序。

3.2 选择排序

思想 : 每一次从待排序的数据元素中选出最小(升序)或最大(降序)的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。
选择过程：以下是对某个序列进行选择排序的过程：

【数据结构】手撕排序NO.1----排序初识,数据结构,数据结构,算法,排序算法,c语言,C++ 动图演示：我们一样通过动图感受一下选择排序的过程：

循环控制：类似的，我们需要两层循环来控制选择排序的过程。内层循环遍历序列找出最大/最小值，外层循环控制选择的次数。
外层循环结束条件：每一次遍历完都可以选出一个数换到起始位置，一共N个数，故要选N-1次(最后一个数不需要选择)
```
    for (int i = 0; i < n-1; i++) //外层循环，共要选择n-1次
	{
        ;
	}
```

内层循环结束条件：内层循环通过比较进行选数，一开始N个数需要比较N-1次，然后每趟结束后下一次选择的起始位置就往后移动一位，比较次数减1

    for (int i = 0; i < n-1; i++) //外层循环，共选择n-1次
	{
		for (int j = i + 1; j < n; j++) //内层循环，起始位置开始向后进行比较，选最小值
		{
            ;
		}
	}

完整代码：

void swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
void SelectSort(int* a, int n)
{
	for (int i = 0; i < n-1; i++) //外层循环，共选择n-1次
	{
		int mini = i; //记录最小值的下标，初始为第一个数下标
		for (int j = i + 1; j < n; j++) //内层循环，起始位置开始向后进行比较，选最小值
		{
			if (a[mini] > a[j]) //比最小值小，交换下标
			{
				mini = j;
			}
		}
		swap(&a[mini], &a[i]); //将最小值与起始位置的数据互换
	}
}

时间/空间复杂度：一共选了N-1次，每次选择需要比较N-1，N-2，N-3...次，加起来和冒泡一样时间复杂度为；没有用到辅助空间，空间复杂度为
稳定性分析：由于是选数交换，在交换的过程中很可能会打乱相同元素的顺序，例如下面这个例子：

我们发现，在第一趟交换中，黑5被交换到了红5后面，在整个排序结束后，黑5依然在红5的后方，与最开始的顺序不一致。由此我们可以得出，选择排序是不稳定的排序。

四. 各大排序算法的复杂度和稳定性

废话不多说，直接上表：

排序算法	时间复杂度(最好)	时间复杂度(平均)	时间复杂度(最坏)	空间复杂度	稳定性	数据敏感度
比较类排序
冒泡排序					稳定	强
选择排序					不稳定	弱
直接插入排序					稳定	强
希尔排序					不稳定	强
堆排序					不稳定	弱
快速排序					不稳定	强
归并排序					稳定	弱
非比较类排序
基数排序				$【数据结构】手撕排序NO.1----排序初识,数据结构,数据结构,算法,排序算法,c语言,C++$	稳定	弱
桶排序		$【数据结构】手撕排序NO.1----排序初识,数据结构,数据结构,算法,排序算法,c语言,C++$		$【数据结构】手撕排序NO.1----排序初识,数据结构,数据结构,算法,排序算法,c语言,C++$	稳定	强
计数排序	$【数据结构】手撕排序NO.1----排序初识,数据结构,数据结构,算法,排序算法,c语言,C++$	$【数据结构】手撕排序NO.1----排序初识,数据结构,数据结构,算法,排序算法,c语言,C++$	$【数据结构】手撕排序NO.1----排序初识,数据结构,数据结构,算法,排序算法,c语言,C++$		稳定	弱