[数据结构]-玩转八大排序（一）&&插入排序&&选择排序

前言

作者：小蜗牛向前冲

名言：我可以接受失败，但我不能接受放弃

如果觉的博主的文章还不错的话，还请点赞，收藏，关注👀支持博主。如果发现有问题的地方欢迎❀大家在评论区指正。

目录

一 排序的概念及其运用

1 排序的概念

2 排序运用

 3 常见的排序算法

二  常见排序算法的实现

1 插入排序

1.1直接插入排序：

1.2希尔排序

2 选择排序

2.1基本思想

2.2 直接选择排序:

2.3 堆排序

---

下面我就为大家刨析九大排序，看看这些排序各有什么特点。 

一 排序的概念及其运用

1 排序的概念

排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。
内部排序：数据元素全部放在内存中的排序。
外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。

2 排序运用

排序的运用是非常广泛的，打个比方，小张同学想要卖一个手机，他的预算是4000元左右，所以他打开某宝去查看，为了找到心仪的手机他就可以通过手机的价格，品牌，功能去筛选。而这些数据都是通过对手机相关信息排序的来的。

 3 常见的排序算法

常见的排序可以分为四大类：

插入排序：直接排序，希尔排序

选择排序：选择排序，堆排序

交换排序：冒泡排序，快速排序

归并排序：归并排序

下面我们就开始一一认识他们吧！

二  常见排序算法的实现

1 插入排序

直接插入排序是一种简单的插入排序法，其基本思想是：把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列。实际中我们玩扑克牌时，就用了插入排序的思想

1.1直接插入排序：

当插入第i(i>=1)个元素时，前面的array[0],array[1],…,array[i-1]已经排好序，此时用array[i]的排序码与array[i-1],array[i-2],…的排序码顺序进行比较，找到插入位置即将array[i]插入，原来位置上的元素顺序后移


其实直接插入排序的思想是将数据分为二组，一组有序，另一组无序，在无序的一组中取数据，插入到有序数组中即可。

代码实现：

//打印数据
void print(int* a,int n)
{
	for (int i = 0;i < n;++i)
	{
		printf("%d ", a[i]);
	}
}
 
//插入排序
void InsertSort(int* a, int n)
{
	//假设[0,end]有序，将end+1的位置插入有有序中，保证[0,end+1]有序
	for (int i = 0;i < n-1;++i)
	{
		int end = i;
		int tmp = a[end + 1];
		//开始比较插入
		while (end >= 0)
		{
			//挪动数据
			if (a[end] > tmp)
			{
				a[end + 1] = a[end];
				--end;
			}
			else
			{
				break;
			}
		}
		//到达次位置后end+1的位置，就一定是比end位置数要大的数
		a[end + 1] = tmp;
	}
 
}

下面我们测试一组数据看是否可以排序。

 

 直接插入排序的特性总结：
1. 元素集合越接近有序，直接插入排序算法的时间效率越高
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)，它是一种稳定的排序算法
4. 稳定性：稳定 

1.2希尔排序

 希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数gap，把待排序文件中所有记录分成个gap组，所有距离为gap的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工作。当到达gap==1时，所有记录在统一组内排好序

 （该动图来自@五分钟学算法）

希尔排序的核心其实就先进行预排序，最后进行插入排序。

其实希尔排序的gap有二种取值形式：gap = gap/3+1或者gap = gap/2。

代码实现：

//希尔排序
void ShellSort(int* a, int n)
{
	//gap>1是预排
	//gao==1就是插入排序
	int gap = n;
	while (gap > 1)
	{
		gap = gap / 3 + 1;//或者gap = gap/2;
		//在[o,end]内插入end+gap,使得[0.end+gap]变的有序
		for (int i = 0;i < n - gap;++i)
		{
			int end = i;
			int tmp = a[end + gap];
			while (end >= 0)
			{
				if (a[end] > tmp)
				{
					//后挪动数据
					a[end + gap] = a[end];
					end -= gap;//找到分组成员
				}
				else
				{
					break;
				}
			}
			a[end + gap] = tmp;
		}
	}
}

我们继续用一些数据验证一下：

希尔排序的特性总结：
1. 希尔排序是对直接插入排序的优化。
2. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。
3. 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些书中给出的希尔排序的时间复杂度都不固定

4. 稳定性：不稳定

 《数据结构(C语言版)》--- 严蔚敏

 《数据结构-用面相对象方法与C++描述》--- 殷人昆

 在这里我们可以记一个大概的时间复杂度:O(n^1.3)

2 选择排序

2.1基本思想

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

2.2 直接选择排序:

在数组a[n]中，我们从以升序举例，直接选择排序的核心思想：我们默认开始第一个元素是最小数，从第二个元素开始遍历数组，选出最小数放在，最小数处，然后就可以选择第二小数（从第三个元素开始，此时我们默认第二个元素是第二小数），继续遍历选出第二小数，依次类推，直到选完n-1个数。

 其实末尾可以稍微优化一下代码，同时选出最大数和最小数继续排序。

//交换
void swop(int* a, int* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}
 
// 选择排序
void SelectSort(int* a, int n)
{
	//按照升序的方式排序
	//从数组中选择数，找出mini放在最小位置，找出maxi值放在最大位置
	int begin = 0;//指向最小位置处
	int end = n - 1;//指向最大位置处
	while (begin < end)
	{
		int maxi = begin, mini = begin;
		//遍历选数，交换,注意边界是end,而不是n
		for (int i = begin + 1;i <=end;++i)
		{
			//找最大值
			if (a[i] > a[maxi])
			{
				maxi = i;
			}
			//找最小值
			if (a[i] < a[mini])
			{
				mini = i;
			}
		}
		//交换
		swop(&a[begin], &a[mini]);
		//修正mini
		if (maxi == begin)
			maxi = mini;
		swop(&a[end], &a[maxi]);
		++begin;
		--end;
	}
}

我们继续测试一下：

 直接选择排序的特性总结：

1. 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)
4. 稳定性：不稳定

2.3 堆排序

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

这里应该在堆那篇博客中详细讲过了，有兴趣的小伙伴去看看（写文章-CSDN创作中心）。

 这里就直接上代码了。

typedef int HPDataType;
 
//定义堆
typedef struct heap
{
	HPDataType* a;
	int size;
	int capacity;
}HP;
 
//交换
void swop(int* a, int* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}
 
//向下调整法
void ADjustDown(HPDataType* a, int n, int parant)
{
	int minChild = parant * 2 + 1;
	//找出最小的孩子
	while (minChild < n)
	{
		if (minChild + 1 < n && a[minChild] > a[minChild + 1])
		{
			minChild++;
		}
		if (a[minChild] < a[parant])
		{
			//交换
			swop(&a[parant], &a[minChild]);
			parant = minChild;
			minChild = parant * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
//思路：依次选择数，从后往前排
// 升序------大堆
// 降序------小堆
//堆排
void HeapSort(int* a, int n)
{
	//从下调整建堆
	for (int i = (n - 2) / 2;i >= 0;--i)
	{
		ADjustDown(a, n, i);
	}
	//交换，选数
	int i = 1;
	while (i < n)
	{
		swap(&a[0], &a[n - i]);
		ADjustDown(a, n - i, 0);
		++i;
	}
}

注意上面代码建的是小堆，所以排序是降序。 

这里我们测试一下 

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

虽然我们知道代码的时间复杂度，但为了更好理解各个排序算法优点我们可以写个代码来直观感受一下

代码如下：

void TestOP()
{
	srand(time(0));
	const int N = 100000;
	int* a1 = (int*)malloc(sizeof(int) * N);
	int* a2 = (int*)malloc(sizeof(int) * N);
	int* a3 = (int*)malloc(sizeof(int) * N);
	int* a4 = (int*)malloc(sizeof(int) * N);
	int* a5 = (int*)malloc(sizeof(int) * N);
	int* a6 = (int*)malloc(sizeof(int) * N);
	for (int i = 0; i < N; ++i)
	{
		a1[i] = rand();
		a2[i] = a1[i];
		a3[i] = a1[i];
		a4[i] = a1[i];
		a5[i] = a1[i];
		a6[i] = a1[i];
 
	}
	int begin1 = clock();
	InsertSort(a1, N);
	int end1 = clock();
	int begin2 = clock();
	//ShellSort(a2, N);
	int end2 = clock();
	int begin3 = clock();
	//SelectSort(a3, N);
	int end3 = clock();
	int begin4 = clock();
	//HeapSort(a4, N);
	int end4 = clock();
	int begin5 = clock();
	//QuickSort(a5, 0, N - 1);
	int end5 = clock();
	int begin6 = clock();
	//MergeSort(a6, N);
	int end6 = clock();
	printf("InsertSort:%d\n", end1 - begin1);
	printf("ShellSort:%d\n", end2 - begin2);
	printf("SelectSort:%d\n", end3 - begin3);
	printf("HeapSort:%d\n", end4 - begin4);
	printf("QuickSort:%d\n", end5 - begin5);
	printf("MergeSort:%d\n", end6 - begin6);
	free(a1);
	free(a2);
	free(a3);
	free(a4);
	free(a5);
	free(a6);
}
 
int main()
{
	testheap();
	return 0;
}

 我们生成了10万个随机数发现，用clock函数既然代码排序完成所需要的时间。堆排和希尔排序是较优的，而直接插入选择排序是效率是最差的。

好了第一期的排序就为大家分享到这里。

下期预告

玩转八大排序&&冒泡排序&&快速排序