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

发布时间:2024年01月07日

前段时间也是结束了二叉树的知识梳理(大家想必满脑子都是递归了):二叉树链式结构的实现(二叉树的遍历以及各种常用功能函数的实现)
今天也要迈向全新的篇章了——排序。这次就先大概讲解一下排序,然后插入排序和希尔排序的介绍和实现



1.排序的概念和运用

1.1概念

排序:所谓排序,就是使一串记录,按照其中的某个或某些关键字的大小,递增或递减(升序或降序)的排列起来的操作。对于排序算法,稳定性是一个重要的特性。

稳定性:描述了相同键值的元素在排序前后相对位置是否保持不变,即在原序列中,有r[i]=r[j],且r[i]在r[j]之前(i<j),而在排序后的序列中,r[i]仍在r[j]之前(次序保持不变),则称这种排序算法是稳定的;否则称为不稳定的

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

外部排序:数据元素太多,无法一次性放入内存中,因此排序过程需要借助外部存储空间进行处理,根据排序过程的要求不能在内外存之间移动数据的排序

1.2运用

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

请添加图片描述

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

2.常见排序一览

请添加图片描述


3.直接插入排序

3.1基本思想

直接插入排序:它的基本思想是将待排序序列分为已排序未排序两部分,然后逐步将未排序部分的元素插入到已排序部分的合适位置,最终完成整个序列的排序

打扑克牌时,我们不就这样吗

请添加图片描述

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

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

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时就是插入排序了)

步骤:

  1. 选择一个增量序列(gap),通常为n/2、n/4、n/8…直到增量为1。

  2. 根据增量(gap,gap多大就能分几组)将数组分割成若干个子序列,对每个子序列进行插入排序(gap为t,一共n个数据。能分t组:每隔t个就取一个)

  3. 逐步减小增量,重复上述步骤,直到增量为1,此时对整个数组进行插入排序

请添加图片描述

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

希尔排序的特性总结:

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

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

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

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;
}

结果:

请添加图片描述


这次排序就先起个头,下次接着带来选择排序的内容,感谢大家支持!!!

文章来源:https://blog.csdn.net/qq_74415153/article/details/135441869
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。