【数据结构】一文带你全面了解排序（上）——直接插入排序、希尔排序、选择排序、堆排序

电玩女神 2023-10-13 17:34 7阅读 0赞

**目录**

一、排序的概念及其运用

1.1 排序的概念

1.2 常见的算法排序

二、常见排序算法的实现

2.1 插入排序

2.1.1 思想

2.1.2 直接插入排序

2.1.3 希尔排序（缩小增量排序）

2.2 选择排序

2.2.1 基本思想

2.2.2 直接选择排序

2.2.3 堆排序

--------------------

没有坚持的努力实质上并没有太大的意义！

--------------------

## 一、排序的概念及其运用 ##

### 1.1 排序的概念 ###

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

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

> 稳定的：直接插入排序、冒泡排序、归并排序
> 
> 不稳定的：希尔排序、选择排序、堆排序、快速排序

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

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

> 1G = 1024MB 1024MB = 1024\*1024KB 1024\*1024KB = 1024 \* 1024 \* 1024byte(10亿）

> （1） 直接插入排序、希尔排序、直接选择排序、桶排序、冒泡排序、快速排序、归并排序都是内部排序。 归并排序可以外部排序
> 
> （2）内部排序：数据在内存中，速度快、下标可以随机访问（因为是数组）；外部排序：数据在磁盘、速度慢、串行访问（文件）、数据量很大

>  **给一个10亿（4G内存）个整数的文件，但是只给1G的运行内存，请对文件的10亿个数据进行排序？**
> 
> **思想**：数据量大加载不到内存，想办法控制两个有序文件归并成一个更大的有序文件
> 
> **思路**：首先分成4等份，分别读到内存排序（这里不能使用归并排序，因为需要额外空间），排完序，写回到磁盘小文件，然再磁盘中，进行归并

### 1.2 常见的算法排序 ###

![ac5e36d724c94f89adddc4fa0c472598.png][]

> 冒泡排序<直接插入排序<堆排序<希尔排序<【越大越优】

## 二、常见排序算法的实现 ##

### 2.1 插入排序 ###

#### 2.1.1 思想 ####

直接插入排序是一种简单的插入排序法。

插入排序的基本思想：有一个有序区间，插入一个数据，依旧保持它有序。【插入的数据和区间的数据从后向前依次比较，如果在区间数据的前面就把区间的数据向后挪动一位，如果在该数据的后面，就直接插入到该位置。这样就不会存在覆盖数据的问题。】

#### 2.1.2 直接插入排序 ####

但是，一个没有顺序的区间，怎么进行排序。【可以把第一个数据看做一个有序区间，后面的第二个数据向第一个数据中插入，数据挪动的时候，会出现数据覆盖的问题，可以使用临时变量进行保存，此时前两个数据称为一个有效区间，后面的第三个数据进行插入，以此类推即可。】

//插入排序//升序
    void InsertSort(int* a, int n)
    {
    	int i = 0;
    	for (i = 0; i < n - 1; i++)
    	{
    		int end = i;//即将插入区间的最后一个元素下标
    		int tmp = a[end + 1];
    		while (end >= 0)
    		{
    			if (tmp > a[end])
    			{
    				//如果把a[end + 1] = tmp;写到这里，会遗漏一种情况，tmp的值是最小的，end=-1，不能进入循环，tmp的值没有赋值给a[0]
    				break;//插入完成，跳出循环
    			}
    			else
    			{
    				a[end + 1] = a[end];
    				end--;
    			}
    		}
    		//还有一种情况，当tmp的值是最小的，此时tmp的值是-1，还没有赋值给a[0],就不能进入循环了
    		a[end + 1] = tmp;
    	}
    }

> 第一层循环的n-1指的是最后一个元素的下标

时间复杂度为O(N^2);空间复杂度O(1);

> 1.  元素集合越接近有序，直接插入排序算法的时间效率越高 
> 
> 2.  时间复杂度： O(N^2) 【最坏的结果是逆序O(N^2),做好的结果是顺序有序或者接近有序O(N)】
> 
> 3.  空间复杂度： O(1) ，它是一种稳定的排序算法 
> 
> 4.  稳定性：稳定

#### 2.1.3 希尔排序（缩小增量排序） ####

> （1）希尔排序分为两部分排序：第一部分是：**预排序**【使其接近有序，因为直接插入排序在接近有序的时候，时间复杂度为O(N)】第二部分是：**直接插入排序**

代码实现：

void ShellSort(int* a, int n)
    {
    	int gap = n;
    	while (gap > 1)
    	{
    		gap = (gap / 3) + 1;
    		for (int j = 0; j < n - gap; j++)
    		{
    			int end = j;
    			int tmp = a[j + gap];
    			while (end >= 0)
    			{
    				if (a[end] < tmp)
    				{
    					break;
    				}
    				else
    				{
    					a[end + gap] = a[end];
    					end -= gap;
    				}
    			}
    			a[end + gap] = tmp;
    		}
    	}
    	
    }

> 第二层循环的n-gap也是最后一个元素的下标，但是一共有gap组，所以是n-gap

> **预排序**：大的数据更快的来到后面，更小的数据更快的来到前面 ，使其接近有序
> 
> 首先分组，取gap = 3，然后取第一个元素，第四个元素，第七个元素……（直到这个元素的下标大于数组的最后一个下标）分为一组；取第二个元素，第五个元素……分为一组；取第三个元素，第六个元素……分为一组；【gap是多少，就分为多少组】分完组之后，进行排序，分别使用**直接插入排序**对这gap组数据进行排序

> 如果**gap越小**，越接近有序；**gap越大**，大的数据可以更快的到最后，小的数据可以更快的到前面，但是它越不接近有序。

> **时间复杂度**：O(N\*log以3为底N的对数），平均是**O(N^1.3)**
> 
> 看预排序部分，如果gap很大，那么最里面的循环，可以忽略不计，就是O(N)，
> 
> 如果gap很小，数据已经非常接近有序了，那么就也是O(N)。
> 
> 看最外面的循环，N/3/3/3/3/3……/3=1 即3的x次方等于N，即log以3为底N的对数
> 
> **稳定性**：不稳定

### 2.2 选择排序 ###

#### 2.2.1 基本思想 ####

每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。

#### 2.2.2 直接选择排序 ####

遍历找出最大和最小的数的位置， 放在数组的两头位置【注意：这里是交换元素，否则就会覆盖数据】，然后遍历找出次小和次大的数字，放在数组的次头位置……一直到全数据元素排完。

**代码展示**：【优化后的】没有优化的是一次找一个元素

void SelectSort(int* a, int n)
    {
    	int left = 0;
    	int right = n - 1;
    	while (left < right)
    	{
    		int mini = left;
    		int maxi = left;
    		for (int i = left + 1; i <= right; i++)
    		{
    			if (a[mini] > a[i])
    			{
    				mini = i;
    			}
    			if (a[maxi] < a[i])
    			{
    				maxi = i;
    			}
    		}
    		Swap(&a[mini], &a[left]);//如果left_0是最大值，最大值此时换到mini_5的位置，/maxi最大位置本来是0，但是此时最大值被换到5的位置，那么此时最小值会被换到最后
    		if (left == maxi)
    		{
    			maxi = mini;
    		}
    		Swap(&a[maxi], &a[right]);
    		right--;
    		left++;
    	}
    }

> 注意：（第一次进行最小值进行交换的时候）如果left\_0是最大值，最大值此时换到mini\_5的位置，/maxi最大位置本来是0，但是此时最大值被换到5的位置，那么此时最小值会被换到最后

> 1.  直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用 
> 
> 2.  时间复杂度： O(N^2) 
> 
> 在最好的情况下、最差的情况下时间复杂度都为O(N)，因为无论有序、无序都要进行遍历找出最大和最小的元素下标
> 
> 3.  空间复杂度： O(1) 
> 
> 4.  稳定性：不稳定

直接选择排序是优于冒泡排序的，但是在数据有序或者接近有序的情况下，冒泡排序是优于直接选择排序的。

#### 2.2.3 堆排序 ####

详细内容见：[堆排序链接][Link 1]

堆排序 (Heapsort) 是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。**需要注意的是排升序要建大堆，排降序建小堆。**

> 1.  堆排序使用堆来选数，效率就高了很多。 
> 
> 2.  时间复杂度： O(N\*logN) 
> 
> 3.  空间复杂度： O(1) 
> 
> 4.  稳定性：不稳定

###  ###

[ac5e36d724c94f89adddc4fa0c472598.png]: https://img-blog.csdnimg.cn/ac5e36d724c94f89adddc4fa0c472598.png
[Link 1]: http://t.csdn.cn/kGhLl