当前位置：首页 > article >正文

排序算法上——插入，希尔，选择，堆排序

article 2024/10/18 13:40:10

前言：

常见排序方法如下：

本篇将介绍4种排序方法，分别为插入排序，希尔排序，选择排序，堆排序，并分别举例与讲解。

一. 插入排序

1.1 含义与动图分析

插入排序的思想是在有序区间的下一个位置插入一个新的元素，之后将该新区间重新排序，依次类推逐个完成整个区间的排序。

扑克整理手牌时就运用了这一思想。

动态理解：

1.2 问题分析

问题：

有序数组插入新元素并排序较为简单，关键在于我们要排序的数组常常区间为无序，那么如何使要插入元素之前的区间有序呢？

分析：

1.假定有序区间为[0,end]，那么需要在[end+1]处插入新元素。

2.因此end的最大值应该小于n-1，否则end+1会导致数组访问越界

3.由于最初的数组为乱序，因此我们可以通过逐次增加有序区间的方式进行插入排序。

1.3 测试实现

代码示例如下：

void InsertSort(int* arr, int n)
{
	//n-2
	for (int i = 0; i < n - 1; i++)
	{
		int end = i;
		int tmp = arr[end + 1];

		while (end >= 0)
		{
			if (arr[end] > tmp)
			{
				arr[end + 1] = arr[end];
				end--;
			}
			else {
				break;
			}
		}
		arr[end + 1] = tmp;
	}
}

时间复杂度分析：

最坏情况：数组降序排列
当我们对下标为i（0<i<n）的tmp数据进行插入时，会将其与前面i个数据比较i次，总比较次数即1+2+3+……(n-1)，为O(n2)
最好情况：数组升序排列
当我们对下标为i（0<i<n）的tmp数据进行插入时，只会与其前面一个数据比较一次，即总共(n-1)此，为O(n)

空间复杂度：O(1)

二. 希尔排序

在直接插入排序中我们发现，元素越无序，直接插入排序算法时间效率越低（因为比较次数越多）。特别是当数组为降序，我们要排升序，此时数组的相对无序程度达到了最大，时间复杂度也到了最大。

2.1 含义与图片分析

希尔排序，也称为递减增量排序算法，是插入排序的一种高效率的改进版本。它通过将待排序的序列分割成若干子序列，分别进行直接插入排序，从而达到整个序列有序的目的。希尔排序的核心在于间隔序列的选择，间隔序列通常是按某种规则递减至1的。

2.2 思路及相关结论

思路分析：

1.希尔排序的核心在于对数组进行预排序，值得注意的是，预排序只是让数组相对有序，而非达到真正的有序状态。

2.预排序的处理可以通过分组实现，假设数组元素个数为n，那么我们可以分为gap组，每组元素就要n/gap个（假设可以gap可以被n整除）

3. 其排序思路与插入排序基本相同，但是gap在每次排序之后，需要令gap逐次减小，当gap减小为1时，就相当于插入排序。

2.3 测试实现

//希尔排序时间复杂度：O（n^1.3)
void ShellSort(int* arr, int n)
{
	int gap = n;

	while (gap > 1)
	{
		gap = gap / 3 + 1;//保证最后一次gap一定为1
		for (int i = 0; i < n - gap; i++)
		{
			int end = i;//n-gap-1
			int tmp = arr[end + gap];
			while (end >= 0)
			{
				if (arr[end] > tmp)
				{
					arr[end + gap] = arr[end];
					end -= gap;
				}
				else {
					break;
				}
			}
			arr[end + gap] = tmp;
		}
	}
}

时间复杂度分析：

外层循环：gap每次除以2或3，O(log2n) 或者O(log3n) ，即O(logn)

内层循环：

假设⼀共有n个数据，合计gap组，则每组为n/gap（大致）个；在每组中，插⼊移动的次数最坏的情况下为 S=1 + 2 + 3 + ……+ (n/gap-1)，⼀共是gap组，因此：

总计最坏情况下移动总数为：gap ∗ S

gap取值有（以除3为例）：n/3 n/9 n/27 … 2 1

一一带入

当gap为n/3时，移动总数为： n
当gap为n/9时，移动总数为： 4n
最后⼀趟，数组已经已基本有序了，gap=1即直接插⼊排序，移动次数就是n
通过以上的分析，可以画出这样的曲线图：

因此，希尔排序在最初和最后的排序的次数都为n，即前⼀阶段排序次数是逐渐上升的状态，当到达某⼀顶点时，排序次数逐渐下降⾄n，⽽该顶点的计算暂时⽆法给出具体的计算过程

内外循环综合来看，外层循环总共log3n次，内层循环的每次排序次数暂时无法精确计算，所以其复杂度不好计算。

希尔排序时间复杂度不好计算，因为 gap 的取值很多，导致很难去计算，因此很多书中给出的希尔排序的时间复杂度都不固定。《数据结构(C语⾔版)》—严蔚敏书中给出的时间复杂度为：

总之希尔排序的时间复杂度综合来说是高于直接插入排序的，范围大概是O(n1.3)~O(n2)
总结：
- 希尔排序的时间性能优于直接插入排序的原因：

在希尔排序开始时增量较大，分组较多，每组的记录数目少，n小，此时直接插入最好和最坏时间复杂度n2差距很小，故各组内直接插入较快，后来增量di逐渐缩小，分组数逐渐减少，而各组的记录数目逐渐增多，但由于已经按di-1作为距离排过序，使文件较接近于有序状态，所以新的一趟排序过程也较快。

gap越大，分组越快，相对有序性越差

gap越小，分组越慢，相对有序性越好。

当gap=1时，相当于插入排序。

三. 选择排序

3.1 含义与动图分析

思路：在整个数组内，每次选出最大的值和最小的值分别位于末尾和开头（升序情况，若为降序则与之相反），之后逐次缩小遍历选择空间。

动图图解：

3.2 测试实现

void SelectSort(int* arr, int n)
{
	int begin = 0;
	int end = n - 1;

	while (begin < end)
	{
		int mini = begin, maxi = begin;
		for (int i = begin+	1; i <= end; i++)
		{
			if (arr[i] > arr[maxi])
			{
				maxi = i;
			}
			if (arr[i] < arr[mini])
			{
				mini = i;
			}
		}
		//mini begin
		//maxi end
		Swap(&arr[mini], &arr[begin]);
		Swap(&arr[maxi], &arr[end]);
		++begin;
		--end;
	}
	
}

注意：上述代码存在问题！！！

在定义maxi和mini时，我们都初始化为了begin处，但当begin处的数据即为最大值时，排序就存在了问题。

分析：

mini正常完成交换之后，begin处的最大值也被交换了过去，那么此时end处的交换就会失败，并不能完成正常功能，因为maxi始终位于begin处，而此时begin处的值已经变为了最小值。

改进如下：

		//避免maxi begini都在同一个位置，begin和mini交换之后，maxi数据变成了最小的数据
		if (maxi == begin)
		{
			maxi = mini;
		}

此时就可以解决最大值位于begin处的情况。

完整代码如下：

void Swap(int* x, int* y)
{
	int tmp = *x;
	*x = *y;
	*y = tmp;
}

void SelectSort(int* arr, int n)
{
	int begin = 0;
	int end = n - 1;

	while (begin < end)
	{
		int mini = begin, maxi = begin;
		for (int i = begin + 1; i <= end; i++)
		{
			if (arr[i] > arr[maxi])
			{
				maxi = i;
			}
			if (arr[i] < arr[mini])
			{
				mini = i;
			}
		}
		//mini begin
		//maxi end
		//避免maxi begini都在同一个位置，begin和mini交换之后，maxi数据变成了最小的数据
		if (maxi == begin)
		{
			maxi = mini;
		}
		Swap(&arr[mini], &arr[begin]);
		Swap(&arr[maxi], &arr[end]);
		++begin;
		--end;
	}
}

四. 堆排序

4.1 基本思路分析

由于堆具有相对有序的特性，要么为大堆，要么为小堆，其相当于完成了希尔排序的预排序工作，因此可以利用建堆之后再向上或向下调整来进行排序。

4.2 测试实现

排升序，建大堆

分析：

1.此时我们常常有一个误区，认为小堆与升序类似，应该建立小堆。

2. 然而在排序的时候，时间消耗过于庞大，因为在挪动元素时，会把堆内的序列和关系打乱，因此应该建大堆，然后利用算法进行调整。

代码示例如下：

void AdjustDown(int* a, int n, int parent)
{
	// 先假设左孩子小
	int child = parent * 2 + 1;

	while (child < n)  // child >= n说明孩子不存在，调整到叶子了
	{
		// 找出小的那个孩子
		if (child + 1 < n && a[child + 1] > a[child])
		{
			++child;
		}

		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

void HeapSort(int* a, int n)
{
	// 向下调整建堆 O(N)
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(a, n, i);
	}

	// O(N*logN)
	int end = n - 1;
	while (end > 0)
	{
		Swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);
		--end;
	}
}

排降序，建小堆

思路于此相同，在此不做过多阐述。

代码示例如下：

void AdjustDown(int* a, int n, int parent)
{
    // 先假设左孩子小
    int child = parent * 2 + 1;

    while (child < n)  // child >= n说明孩子不存在，调整到叶子了
    {
        // 找出小的那个孩子
        if (child + 1 < n && a[child + 1] < a[child])
        {
            ++child;
        }

        if (a[child] < a[parent])
        {
            Swap(&a[child], &a[parent]);
            parent = child;
            child = parent * 2 + 1;
        }
        else
        {
            break;
        }
    }
}

void HeapSort(int* a, int n)
{
    // 向下调整建堆 O(N)
    for (int i = (n - 1 - 1) / 2; i >= 0; i--)
    {
        AdjustDown(a, n, i);
    }

    // O(N*logN)
    int end = n - 1;
    while (end > 0)
    {
        Swap(&a[0], &a[end]);
        AdjustDown(a, end, 0);
        --end;
    }
}

小结：本文主要讲解了四种排序方法，下篇将会继续讲解排序的其他方式，欢迎各位大佬前来斧正支持！！！