数据结构排序（一.基本概念、插入排序和希尔排序实现）

是Nero哦

发布于 2024-01-18 18:51:09

970

发布于 2024-01-18 18:51:09

文章被收录于专栏：c/c++学习与分享

前段时间也是结束了二叉树的知识梳理（大家想必满脑子都是递归了）：二叉树链式结构的实现(二叉树的遍历以及各种常用功能函数的实现)

今天也要迈向全新的篇章了——排序。这次就先大概讲解一下排序，然后插入排序和希尔排序的介绍和实现

1.排序的概念和运用

1.1概念

排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减(升序或降序)的排列起来的操作。对于排序算法，稳定性是一个重要的特性。稳定性：描述了相同键值的元素在排序前后的相对位置是否保持不变，即在原序列中，有ri=rj，且ri在rj之前（i<j），而在排序后的序列中，ri仍在rj之前(次序保持不变)，则称这种排序算法是稳定的；否则称为不稳定的 内部排序：数据元素全部放在内存中的排序 外部排序：数据元素太多，无法一次性放入内存中，因此排序过程需要借助外部存储空间进行处理，根据排序过程的要求不能在内外存之间移动数据的排序

1.2运用

邮件和文件整理： 在办公室或个人生活中，整理文件或邮件时会按照日期、主题或重要性排序，这样可以更方便地管理和查找文件

成绩、学校排名：我们作为学生那肯定很熟悉了
音乐播放列表： 在音乐播放器或流媒体平台上，可以按照歌手、专辑、曲目或流行程度等因素对音乐进行排序，方便用户查找和播放喜欢的音乐

2.常见排序一览

3.直接插入排序

3.1基本思想

直接插入排序：它的基本思想是将待排序序列分为已排序和未排序两部分，然后逐步将未排序部分的元素插入到已排序部分的合适位置，最终完成整个序列的排序打扑克牌时，我们不就这样吗

直接插入排序的特性总结：

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

3.2具体实现

void InsertionSort(int* a, int n)//升序
{
	for (int i = 0; i <= n - 2; i++)
	{
		int end = i;//用来标记，<=end的都已经排好了，该end+1排了
		int tmp = a[end + 1];//保存一下，后面可能会被覆盖
		while (end >= 0)//用来把比tmp大的向后移，中间就有空位了
		{
			if (a[end] > tmp)
			{
				a[end + 1] = a[end];//要是>tmp那就向后移动，也是覆盖发生
			}
			else
			{
				break;
			}
			end--;//end往前走
		}
		a[end + 1] = tmp;//放到空位，
	}

}

int main()
{
	int a[10] = { 2,5,6,1,8,9,10,12,56,73 };
	for (int i = 0; i < 10; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
	InsertionSort(a, 10);
	for (int i = 0; i < 10; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
	return 0;
}

3.3过程示图

4.希尔排序

4.1思想、过程和性质

gap为间隔，隔几个间隔取一个元素放在同一个子序列内。

希尔排序：一种插入排序的改进版本，也被称为缩小增量排序。它通过将待排序的数组分割成若干个子序列，分别进行插入排序，然后逐步减小子序列的长度，最终将整个数组排序。当子序列长度到达1时，所有记录就排好序了（gap=1时就是插入排序了） 步骤：

选择一个增量序列（gap），通常为n/2、n/4、n/8…直到增量为1。
根据增量（gap，gap多大就能分几组）将数组分割成若干个子序列，对每个子序列进行插入排序(gap为t，一共n个数据。能分t组：每隔t个就取一个)
逐步减小增量，重复上述步骤，直到增量为1，此时对整个数组进行插入排序

这只是gap=3的过程，gap会继续减小再次经历次过程。直至gap=1是最后一次

希尔排序的特性总结：

希尔排序是对直接插入排序的优化。
当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就

会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。

希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算
稳定性：不稳定(分组在不同组，导致改变)

4.2代码实现

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>

void ShellSort(int* a, int n)
{
	int gap = n;
	while (gap > 1)//最外层循环用来减小gap
	{
		gap = gap / 3 + 1;//保证最后一个gap=1；1或2来除3是0
		for (int i = 0; i < n - gap; i++)//第二层循环用来使整个数组以子序列为单位进行插入排序
		{
			int end = i;//需要end最初指向各子序列的头
			int tmp = a[end + gap];//储存下一个需要排的
			while (end >= 0)//第三次循环是针对这个tmp，看插在哪内进行插入排序（找空位）
			{
				if (tmp < a[end])
				{
					a[end + gap] = a[end];//end处的值后移到子序列中的下一个
					end-=gap;
				}
				else
				{
					break;
				}
			}
			a[end + gap] = tmp;//放进空位
		}


	}
}

int main()
{
	int a[] = { 9,1,2,5,7,4,8,6,3,5,1,2,3,5,1,8,3 };
	printf("排序前：");
	for (int i = 0; i < sizeof(a) / sizeof(int); i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
	ShellSort(a, sizeof(a) / sizeof(int));
	printf("排序后：");
	for (int i = 0; i < sizeof(a) / sizeof(int); i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
	return 0;
}

结果：