八大排序详解

最编程 2024-09-29 15:21:54

...

文章目录

目录
- 1. 排序的概念及其运用
- - 1.1 排序的概念
  - 1.2 排序的运用
  - 1.3 常见的排序算法
- 2. 常见排序算法的实现
- - 2.1 插入排序
  - - 2.1.1 基本思想
    - 2.1.2 直接插入排序
    - 2.1.3 希尔排序
  - 2.2 选择排序
  - - 2.2.1 基本思想
    - 2.2.2 直接选择排序
    - 2.2.3 堆排序
  - 2.3 交换排序
  - - 2.3.1 基本思想
    - 2.3.2 冒泡排序
    - 2.3.3 快速排序
  - 2.4 归并排序
  - 2.5 非比较排序
- 3. 排序算法复杂度及稳定性分析

稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。

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

外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。

1.2 排序的运用

排序的运用

1.3 常见的排序算法

常见的排序算法

2. 常见排序算法的实现

2.1 插入排序

2.1.1 基本思想

直接插入排序是一种简单的插入排序法，其基本思想是：把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列。

实际中我们玩扑克牌时，就用了插入排序的思想

2.1.2 直接插入排序

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

//时间复杂度 O(N^2)
//最坏情况：逆序（除了逆序之外，其他情况都达不到 O(N^2)，只需要移动几个数，不用把所有数据都往后移一位；但是冒泡排序必须要保证这一段全是有序才会跳出循环；所以虽然它们时间复杂度的量级相同，但是在给一组随机数时，直接插入排序会比冒泡排序快很多）（冒泡几乎每次都是最坏情况；直接插入几乎每次都不是最坏情况）
//最好情况：顺序有序或者接近有序 O(N)
void InsertSort(int* a, int n)
{
	for (int i = 0; i < n - 1; i++)
	{
		// [0, end] end + 1
		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;
	}
}

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

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

2.1.3 希尔排序

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

希尔排序

//预排序 -- 目标：接近有序  gap > 1
//插入排序 -- 目标：有序    gap == 1
//O(N^1.3)
void ShellSort(int* a, int n)
{
	int gap = n;

	while (gap > 1)
	{
		//gap /= 2;
		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 + gap];

				while (end >= 0)
				{
					if (tmp < a[end])
					{
						a[end + gap] = a[end];
						end -= gap;
					}
					else
					{
						break;
					}
				}

				a[end + gap] = tmp;
			}
		}
	}
}

预排序的三层循环可以简化成两层：

void ShellSort(int* a, int n)
{
	int gap = n;

	while (gap > 1)
	{
		//gap /= 2;
		gap = gap / 3 + 1;

		//gap组数据，交替完成分组插入排序
		for (int i = 0; i < n - gap; i++)
		{
			int end = i;
			int tmp = a[end + gap];

			while (end >= 0)
			{
				if (tmp < a[end])
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}

			a[end + gap] = tmp;
		}
	}
}

希尔排序的特性总结：

希尔排序是对直接插入排序的优化。
当 gap > 1时都是预排序，目的是让数组更接近于有序；当 gap == 1时，数组已经接近有序了，这样就会很快。这样整体而言，可以达到优化的效果，我们实现后可以进行性能测试的对比。
希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些书中给出的希尔排序的时间复杂度都不固定，我们暂时记为O(N^1.3)
稳定性：不稳定

希尔排序的时间复杂度

2.2 选择排序

2.2.1 基本思想

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

2.2.2 直接选择排序

在元素集合 a[i] - a[n-1]中选择关键码最大(小)的数据元素
若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个（第一个）元素交换
在剩余的 a[i] - a[n-2]（a[i+1] - a[n-1]）集合中，重复上述步骤，直到集合剩余1个元素

我们也可以稍微对它进行一下优化：一次遍历就把最大和最小的数选出来，分别放在头和尾

void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

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

	while (begin < end)
	{
		//选出最小值和最大值的位置
		int mini = begin, maxi = begin;

		for (int i = begin + 1; i <= end; i++)
		{
			if (a[i] < a[mini])
			{
				mini = i;
			}

			if (a[i] > a[maxi])
			{
				maxi = i;
			}
		}

		Swap(&a[begin], &a[mini]);

		//解决maxi和begin重叠的问题
		if (maxi == begin)
		{
			maxi = mini;
		}

		Swap(&a[end], &a[maxi]);
		++begin;
		--end;
	}
}

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

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

2.2.3 堆排序

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

void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

void AdjustDown(int* a, int n, int parent)
{
	int child = parent * 2 + 1;

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

//升序，建大堆还是小堆呢？大堆
//O(N * logN)
void HeapSort(int* a, int n)
{
	//a数组直接建堆 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;
	}
}

堆排序的特性总结：

堆排序使用堆来选数，效率就高了很多。
时间复杂度：O(N*logN)
空间复杂度：O(1)
稳定性：不稳定

2.3 交换排序

2.3.1 基本思想

所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。

2.3.2 冒泡排序

void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

//时间复杂度 O(N^2)
//最好情况：顺序有序或者接近有序 O(N)
void BubbleSort(int* a, int n)
{
	for (int j = 0; j < n - 1; j++)
	{
		int exchange = 0;

		for (int i = 1; i < n - j; i++)
		{
			if (a[i - 1] > a[i])
			{
				Swap(&a[i - 1], &a[i]);
				exchange = 1;
			}
		}

		if (0 == exchange)
		{
			break;
		}
	}
}

冒泡排序的特性总结：

冒泡排序是一种非常容易理解的排序
时间复杂度：O(N^2)
空间复杂度：O(1)
稳定性：稳定

2.3.3 快速排序

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

快速排序的单趟排序

void QuickSort(int* a, int left, int right)
{
	//区间只有一个值或者不存在就是最小子问题
	if (left >= right)
	{
		return;
	}

	int begin = left, end = right;
	int keyi = left;

	while (left < right)
	{
		// right先走，找小
		// = 是为了避免左右两边的值都和key相等，导致死循环
		while (left < right && a[right] >= a[keyi])
		{
			--right;
		}

		//left再走，找大
		while (left < right && a[left] <= a[keyi])
		{
			++left;
		}

		Swap(&a[left], &a[right]);
	}

	Swap(&a[left], &a[keyi]);
	keyi = left;

	//[begin, keyi - 1]keyi[keyi + 1, end]
	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi + 1, end);
}

L、R相遇位置的值一定是比key位置的值小：
相遇位置比key小

降序的实现：

void QuickSort(int* a, int left, int right)
{
	//区间只有一个值或者不存在就是最小子问题
	if (left >= right)
	{
		return;
	}

	int begin = left, end = right;
	int keyi = left;

	while (left < right)
	{
		// right先走，找大
		// = 是为了避免左右两边的值都和key相等，导致死循环
		while (left < right && a[right] <= a[keyi])
		{
			--right;
		}

		//left再走，找小
		while (left < right && a[left] >= a[keyi])
		{
			++left;
		}

		Swap(&a[left], &a[right]);
	}

	Swap(&a[left], &a[keyi]);
	keyi = left;

	//[begin, keyi - 1]keyi[keyi + 1, end]
	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi + 1, end);
}

时间复杂度：
快速排序的时间复杂度

当数组是有序或者接近有序时，就会出现最坏情况：O(N^2)

但是如果加上随机选key或者三数取中选key，最坏情况不会出现，所以这里不看最坏

这时的时间复杂度就变成了：O(N*logN)

随机选key：

void QuickSort(int* a, int left, int right)
{
	//区间只有一个值或者不存在就是最小子问题
	if (left >= right)
	{
		return;
	}

	int begin = left, end = right;
	
	//选[left, right]区间中的随机数做key
	int randi = rand() % (right - left + 1);
	randi += left;
	Swap(&a[left], &a[randi]);
	
	int keyi = left;

	while (left < right)
	{
		// right先走，找小
		// = 是为了避免左右两边的值都和key相等，导致死循环
		while (left < right && a[right] >= a[keyi])
		{
			--right;
		}

		//left再走，找大
		while (left < right && a[left] <= a[keyi])
		{
			++left;
		}

		Swap(&a[left], &a[right]);
	}

	Swap(&a[left], &a[keyi]);
	keyi = left;

	//[begin, keyi - 1]keyi[keyi + 1, end]
	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi + 1, end);
}

但是有人认为随机数不是很靠谱，它虽然解决了最坏情况的问题，但是它也很难取到中间这个数（key越靠近中间，高度就越靠近logN），因此我们可以采取三数取中法。

//三数取中 left mid right
//大小居中的值，也就是不是最大也不是最小的
int GetMidi(int* a, int left, int right)
{
	int mid = (left + right) / 2;
	
	if (a[left] < a[mid])
	{
		if (a[mid] < a[right])
		{
			return mid;
		}
		else if (a[left] > a[right])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
	else
	{
		if (a[mid] > a[right])
		{
			return mid;
		}
		else if (a[left] < a[right])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
}

void QuickSort(int* a, int left, int right)
{
	//区间只有一个值或者不存在就是最小子问题
	if (left >= right)
	{
		return;
	}

	int begin = left, end = right;

	//三数取中
	int midi = GetMidi(a, left, right);
	Swap(&a[left], &a[midi]);

	int keyi = left;

	while (left < right)
	{
		// right先走，找小
		// = 是为了避免左右两边的值都和key相等，导致死循环
		while (left < right && a[right] >= a[keyi])
		{
			--right;
		}

		//left再走，找大
		while (left < right && a[left] <= a[keyi])
		{
			++left;
		}

		Swap(&a[left], &a[right]);
	}

	Swap(&a[left], &a[keyi]);
	keyi = left;

	//[begin, keyi - 1]keyi[keyi + 1, end]
	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi + 1, end);
}

以上代码还可以继续优化：比如左区间只有10个数了，如果还继续用快排，就需要开很多次栈帧，消耗有点多（我们在讲二叉树时提到过，满二叉树最后一层的消耗就是50%），所以我们可以用直接插入排序进行优化。

int GetMidi(int* a, int left, int right)
{
	int mid = (left + right) / 2;

	if (a[left] < a[mid])
	{
		if (a[mid] < a[right])
		{
			return mid;
		}
		else<


																				
						
							上一篇：							
								ScrapeGraphAl 人工智能爬虫							
						
						
							下一篇：							
								CSS 预处理器 LESS							
						
					
															
						
							推荐阅读						
						
														
								
									
										第十三届 "蓝桥杯 "问题 Python c 组 D. 数字排序（持续更新）									
								
							
														
								
									
										C++ 排序算法									
								
							
														
								
									
										主流 NoSQL 和应用场景详解									
								
							
														
								
									
										word2vector 训练代码详解									
								
							
														
								
									
										Java 中的五种 I/O 模式详解--五、异步 I/O（Asynchronous I/O）									
								
							
														
								
									
										八大排序详解									
								
							
														
								
									
										详解YUV系列(三)-------YUV420									
								
							
														
								
									
										解密Android Bitmap转I420的难题，附图文详解YUV420数据格式									
								
							
														
								
									
										YUV420数据格式详解，以图文形式揭示 - 提示：加强阅读理解，配合图片观看更加易懂									
								
							
														
								
									
										详解YUV444、YUV422、YUV420的可视化解释

八大排序详解

文章目录

目录

1. 排序的概念及其运用

1.1 排序的概念

1.2 排序的运用

1.3 常见的排序算法

2. 常见排序算法的实现

2.1 插入排序

2.1.1 基本思想

2.1.2 直接插入排序

2.1.3 希尔排序

2.2 选择排序

2.2.1 基本思想

2.2.2 直接选择排序

2.2.3 堆排序

2.3 交换排序

2.3.1 基本思想

2.3.2 冒泡排序

2.3.3 快速排序

第十三届 "蓝桥杯 "问题 Python c 组 D. 数字排序（持续更新）

C++ 排序算法

主流 NoSQL 和应用场景详解

word2vector 训练代码详解

Java 中的五种 I/O 模式详解--五、异步 I/O（Asynchronous I/O）

八大排序详解

详解YUV系列(三)-------YUV420

解密Android Bitmap转I420的难题，附图文详解YUV420数据格式

YUV420数据格式详解，以图文形式揭示 - 提示：加强阅读理解，配合图片观看更加易懂

详解YUV444、YUV422、YUV420的可视化解释