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

一、排序的概念及其运用

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 常见的算法排序

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

二、常见排序算法的实现

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 堆排序

详细内容见：堆排序链接文章来源地址https://uudwc.com/A/0r2Gw

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

1. 堆排序使用堆来选数，效率就高了很多。

2. 时间复杂度： O(N*logN)

3. 空间复杂度： O(1)

4. 稳定性：不稳定