数据结构：希尔排序

时间：2024-06-01 10:31:49

文章目录

  • 前言
  • 一、排序的概念及其运用
  • 二、常见排序算法的实现
    • 1.插入排序
    • 2.希尔排序
  • 总结

前言

排序在生活中有许多实际的运用。以下是一些例子：

  1. 购物清单：当我们去超市购物时，通常会列出一份购物清单。将购物清单按照需要购买的顺序排序，可以使购物过程更加高效和有序。

  2. 时间管理：在安排日程和任务时，将任务按照优先级排序可以帮助我们更好地管理时间。通过将任务按照重要性和紧急性进行排序，我们可以更好地掌控时间，确保重要的事情得到优先处理。

  3. 紧急情况应对：在紧急情况下，如自然灾害或事故，排序可以帮助救援人员更好地组织和协调救援工作。根据伤势的严重性和治疗的紧迫性对伤者进行排序，可以确保救援资源得到合理利用，最大程度地拯救生命。

  4. 选课/注册：在大学或学校的选课和注册过程中，学生通常需要按照自身的兴趣和要求对课程进行选择。将课程按照自己的优先级进行排序，可以确保能够在有限的选课时间内选到最理想的课程。

  5. 编辑和整理文件：在工作或学习中，我们经常需要整理和编辑文件。将文件按照名称、日期或其他标准进行排序，可以帮助我们更快地找到需要的文件，提高工作效率。

  6. 旅行规划：在计划旅行时，我们通常会按照时间和地点对行程进行排序。这样可以确保旅行过程中的交通和活动安排紧密合理，更好地利用旅行时间。

综上所述，排序在生活中的运用是非常广泛的。通过排序，我们可以更好地组织和安排工作、学习和生活，提高效率和质量。

一、排序的概念及其运用

1.排序的概念 

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

 2.常见排序算法

// 插入排序
void InsertSort(int* a, int n);
// 希尔排序
void ShellSort(int* a, int n);
// 选择排序
void SelectSort(int* a, int n);
// 堆排序
void AdjustDwon(int* a, int n, int root);
void HeapSort(int* a, int n);
// 冒泡排序
void BubbleSort(int* a, int n)
// 快速排序递归实现
// 快速排序hoare版本
int PartSort1(int* a, int left, int right);
// 快速排序挖坑法
int PartSort2(int* a, int left, int right);
// 快速排序前后指针法
int PartSort3(int* a, int left, int right);
void QuickSort(int* a, int left, int right);
// 快速排序 非递归实现
void QuickSortNonR(int* a, int left, int right)
// 归并排序递归实现
void MergeSort(int* a, int n)

二、常见排序算法的实现

1.插入排序

1.1插入排序基本思想

把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为 止，得到一个新的有序序列 。

 以下是插入排序动图演示： 

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

2.代码实现 

void InsertSort(int* a, int n)
{
	//  [0, n-1]
	for (int i = 0; i < n - 1; i++)
	{
		// [0, n-2]是最后一组
		// [0,end]有序 end+1位置的值插入[0,end]，保持有序
		int end = i;
		int tmp = a[end + 1];
		while (end >= 0)
		{
			if (tmp < a[end])
			{
				a[end + 1] = a[end];
				--end;
			}
			else
			{
				break;
			}
		}
		a[end + 1] = tmp;
	}
}
直接插入排序的特性总结：
1. 元素集合越接近有序，直接插入排序算法的时间效率越高
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)，它是一种稳定的排序算法
4. 稳定性：稳定

2.希尔排序

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

 首先进行预排序，让数组接近有序

gap越大，大的数可以越快跳到后面，小的数可以越快跳到前面

gap越小，跳的越慢，但是越接近有序，当gap==1时就是插入排序

void ShellSort(int* a, int n)
{
	int gap = 3;
	for (int j = 0; j < gap; j++)
	{
		for (int i = j; i < n - gap; i += gap)
		{
			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 + 1] = tmp;
		}
	}
}

 该代码的两层for循环嵌套可改写成一层for循环，时间复杂度不变

gap最后+1是确保 最后一个gap一定是1

gap

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

希尔排序的时间复杂度取决于选择的间隔序列。假设有n个元素需要排序，希尔排序的最坏时间复杂度为O(n^2)，而平均情况下的时间复杂度则为O(n^1.3)。这使得希尔排序相比于其他排序算法具有较好的性能。

总结

希尔排序（Shell Sort）是一种高效的排序算法，它是插入排序的一种改进。希尔排序通过将待排序的元素按照一定间隔分组，然后对每个分组进行插入排序，不断缩小间隔，直到间隔为1时完成最后一次排序，使整个序列基本有序。希尔排序的作用主要有以下几个方面：

1. 加快排序速度：相比于传统的插入排序，希尔排序可以显著减少比较和交换的次数，从而提高排序的速度。

2. 克服插入排序的缺点：插入排序在处理大规模或逆序序列时，移动元素的次数较多，效率较低。希尔排序通过分组排序和逐步缩小间隔的方式，可以有效地克服插入排序的这一缺点。

3. 高效处理部分有序序列：希尔排序在每一轮排序时，会将相距较远的元素进行比较和交换，从而可以快速将部分有序的序列整理成完全有序的序列。

总的来说，希尔排序可以提高排序效率，克服插入排序的缺点，并且在处理部分有序序列时表现出较好的性能。

相关文章