多种排序讲解

hello，各位小伙伴，本篇文章跟大家一起学习多种排序，感谢大家对我上一篇的支持，如有什么问题，还请多多指教！

文章目录

冒泡排序
选择排序
插入排序
希尔排序
堆排序
快速排序
提醒

冒泡排序

冒泡排序就是遍历数组，找到数组中最大或者最小的元素，然后放在数组开头或者结尾，然后不断遍历数组找次大的或者次小的元素，直至排序结束，光说无用，看代码演示：

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

// 冒泡排序
void BubbleSort(int* a, int n)
{
	int end = n - 1;
	while (end > 1)
	{
		for (int i = 0; i < end; i++)
		{
			if (a[i] > a[i + 1])//找最大的
				Swap(&a[i], &a[i + 1]);
		}
		end--;
	}
}

冒泡排序的平均时间复杂度为 (O(n²))

选择排序

顾名思义就是选择元素来排序，但是每次遍历数组只选择一个最大或者最小元素的话效率属实太慢了，所以优化一下，每次遍历数组选择最大和最小的元素，然后将最大和最小的元素放在正确的位置，看代码：

// 选择排序
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;
			else if (a[i] > a[maxi])
				maxi = i;
		}
		Swap(&a[begin], &a[mini]);
		if (maxi == begin) //代码1
			maxi = mini;  //代码2  
		Swap(&a[end], &a[maxi]);
		end--;
		begin++;
	}
}

由于特殊情况如：数组：6 5 4
此时min指向元素4(下标2)，max指向元素6(下标0)，若没有代码1和代码2，那么排序结果还是6 5 4，因为元素6和元素4交换了两次。小伙伴们可以在编译器里调试看一下。
选择排序的平均时间复杂度为 (O(n²))

插入排序

插入排序举个例子会更容易理解：3，1，2，4，5
我们要将元素3放置在元素2和元素4中间，因为2 < 3 < 4，这就是插入排序的原理，找一个元素，向后比较，若比该元素小，二者交换，若比该元素大或者到达数组末尾，则停止，从另一个元素开始比较，看代码(我写的是向前比较)：

// 插入排序
void InsertSort(int* a, int size)
{
	for (int i = 1; i < size; i++)
	{
		int index = i;
		int tmp = a[index];//找到要插入的元素
		while (index > 0)
		{
			if (tmp < a[index - 1])
			{
				a[index] = a[index - 1];//你比我小，你到前面的位置
				index--;
			}
			else
				break;
		}
		a[index] = tmp;//直至找到比我大的元素或者已经是数组的末尾，插入该元素
	}
}

插入排序的平均时间复杂度为 (O(n²))

希尔排序

简单来说，希尔排序就是在插入排序前进行预排序，但是：

希尔排序是一种改进的插入排序算法，它通过引入间隔（gap）来减少插入排序中元素的移动次数，从而提高排序的效率。虽然希尔排序可以看作是在插入排序前进行预排序，但具体实现上有所不同。
在希尔排序中，我们首先选择一个间隔序列（通常是 (n/2, n/4, n/8, …))，对数组进行分组，分别对每组进行插入排序。随着算法的进行，逐渐缩小间隔，直到间隔为1时，完成最后一次插入排序，此时数组已基本有序。

总的来说，希尔排序并不是简单地在插入排序前进行预排序，而是通过引入间隔和分组的方式，优化了插入排序的性能。

光说难懂，先看代码:

// 希尔排序
void ShellSort(int* a, int size)
{
	int gap = size;
	while(gap > 1)//循环直至gap==1
	{
		gap = gap / 3 + 1;//不断缩小gap的值，直至等于1
						 //(+1是为了控制gap最终会等于1)
		for (int i = 0; i < size - gap; i += gap)
		{
			int index = i;
			int tmp = a[index + gap];//分组后元素间隔为gap
			while (index >= 0)
			{
				if (tmp < a[index])
				{
					a[index + gap] = a[index];
					index -= gap;
				}
				else
					break;
			}
			a[index + gap] = tmp;
		}
	}
}

希尔排序的时间复杂度取决于间隔序列（gap sequence）的选择，通常情况下为 (O(n^1.5)) 到 (O(n^2)) 之间。

堆排序

堆排序顾名思义需要建立堆来进行排序，从小到大就建立大堆，从大到小就建立小堆，为什么呢？因为我们要通过堆顶元素来进行排序，所以顺序还是逆序取决于堆顶。话不多说，看代码：

void Swap(int* x, int* y)
{
	int tmp = *x;
	*x = *y;
	*y = tmp;
}
void HeapSort(int* a,int size)
{
	for (int i = (size - 1 - 1) / 2; i > 0; i--)
	{
		AdjustDown(a,size,i);
	}
	int end = size - 1;
	while(end)
	{
		Swap(&a[0], &a[end]);//将堆顶的数据放置末尾
		AdjustDown(a, end,0);//然后进行向下调整，将堆变回小堆
		end--;//忽略已经被放置好的元素
	}
}

由于是将堆顶元素放在末尾，所以从小到大就建立大堆，从大到小就建立小堆

堆排序的平均时间复杂度为 (O(n \log n))

快速排序

快速排序一听名字就知道排序很快，对的，确实很快
快速排序是要每一次排序找一个基准值(一般选择第一个元素作为基准值)，然后建立指针指向数组左右两端，右端指针先向左走(后面会解释)，找比基准值小于等于的元素或者遇到左端指针时停下，如果没有遇到左端指针，左端指针向右走，找比基准值大于等于的元素或者遇到右端指针时停下，如果没有遇到右端指针，两指针指向的元素进行交换，重复如此，直至两指针相遇，再将基准值插入两指针相遇的位置，因为该位置左边小于等于基准值，右边大于等于基准值。
在这里插入图片描述

这样我们就得到由基准值为中心，两段分好大小的数据，然后进行递归，直至要递归的数据只有基准值而无其他元素，也就是左端指针和右端指针指向同一个位置。
话不多说，看代码：

void Swap(int* x, int* y)
{
	int tmp = *x;
	*x = *y;
	*y = tmp;
}
void QuickSort(int* a, int left, int right)
{
	if (left >= right)
		return;
	int begin = left, end = right;
	int keyi = begin;
	while (left < right)
	{
		while (left < right && a[right] >= a[keyi])
		{
			right--;//向左走
		}

		while (left < right && a[left] <= a[keyi])
		{
			left++;//向右走
		}
		Swap(&a[left], &a[right]);交换数据
	}
	Swap(&a[keyi], &a[left]);//插入基准值
	//进行递归，要注意传参控制排序的起始位置和结束位置
	QuickSort(a, begin, left);//左段
	QuickSort(a, left+1, end);//右段
}