༺ 个人主页 · 纪念229 ༻

🏠我的博客主页🏠

༒专栏目录：《数据结构》༒

༒专栏目录：《算法》༒

༒专栏目录：《MySQL数据库》༒

༒专栏目录：《前端开发》༒

༒其它有趣的计算机知识༒

༺世上本没有路，走的人多了自然就有了༻

---

这篇文章讲述的是数据结构的一些排序，承接上篇文章，希望对你有所帮助

在有关数据结构排序的文章中我会写到八大排序(这些排序中有些排序我在其它问章中写过这里我就不赘述了)
其中有七个是比较排序，还有一个是非比较排序

---

---

注意本文写的排序指的是升序排序

1.直接选择排序

直接选择排序我知道的有两种一种是只有begin和min根据min下标遍历数组找最小值将最小值赋与begin（begin最开始下标是0）下标上的值交换接着begin++接着遍历直到begin小于下标n - 1为止
第二种就是我要介绍的时间复杂度更小有begin mini end maxi ，begin下标为0 end下标为n - 1先假设最大值和最小值都为下标为begin上的值然后利用下标i遍历数组找到最大值与最小值将其与begin和end上的值交换然后接着循环直到不符合begin < end 为止

代码展示

//直接选择排序
void SelectSort(int* arr, int n);

void SelectSort(int* arr, int n)
{
	int begin = 0;
	int end = n - 1;
	while (begin < end)
	{
		int maxi = begin;
		int mini = begin;
		for (int i = begin + 1; i <= end; i++)
		{
			if (arr[i] < arr[mini])
			{
				mini = i;
			}
			if (arr[i] > arr[maxi])
			{
				maxi = i;
			}
		}
		//找到最小的与begin交换
		//找到最大的与end交换
		//当begin上是maxi、end上是mini时互相交换两次，将maxi 赋值到 mini即可
		if (maxi == begin)
		{
			maxi = mini;
		}
		//有疑惑为啥不是maxi == begin && mini == end作为
		//如果恰好mini在这三个数据之间呢
		//也没事这种情况会把最大值换到中间又因为maxi的下标就在这执行后功能也能实现
		//最后一次排序
		Swap(&arr[mini], &arr[begin]);
		Swap(&arr[maxi], &arr[end]);
		//最后将begin++和end--实现利用maxi、mini来排序
		begin++;
		end--;
	}

}

代码讲解

int begin = 0;
int end = n - 1;

首先给出begin、end
作用将min 与max上的值放入其中之后begin++、end–这样就实现了排序

while (begin < end)
{
.......
}

循环结束说明排序完成

int maxi = begin;
int mini = begin;
for (int i = begin + 1; i <= end; i++)
{
		if (arr[i] < arr[mini])
		{
			mini = i;
		}
		if (arr[i] > arr[maxi])
		{
			maxi = i;
		}
}
//找到最小的与begin交换
//找到最大的与end交换
//当begin上是maxi、end上是mini时互相交换两次，将maxi 赋值到 mini即可
if (maxi == begin)
{
		maxi = mini;
}
//有疑惑为啥不是maxi == begin && mini == end作为
//如果恰好mini在这三个数据之间呢
//也没事这种情况会把最大值换到中间又因为maxi的下标就在这执行后功能也能实现
//最后一次排序
Swap(&arr[mini], &arr[begin]);
Swap(&arr[maxi], &arr[end]);
//最后将begin++和end--实现利用maxi、mini来排序
begin++;
end--;

首先假设最小值和最大值都在下标begin上

然后根据下标i遍历将arr[i] 与arr[mini]和arr[maxi]比较
如果arr[i] < arr[mini]就把mini下标放在此时的下标i上arr[i] > arr[maxi]也是一样最后内循环结束如果max下标在begin上那么要将min赋值到max上（防止max下标在begin，min下标在end上将min上的值与begin上的值交换以及max上的值与end上的值交换时会发生二次交换）

接着将min下标上的值与begin下标上的值进行交换，将max下标上的值与end下标上的值交换平且将begin++、end–接着循环直到不符合begin < end为止

2.快速排序

快速排序就是找基准值递归

这里我讲的是递归方法的快速排序
下一章我会讲述非递归方法的快速排序

代码展示

//快速排序
void QuickSort(int* arr, int left, int right);//递归

//hoare版本
int _QuickSort1(int* arr, int left, int right)
{
	int keyi = left;
	++left;
	while (left <= right)
	{
		//right从右往左走找比基准值小的
		while (left <= right && arr[right] > arr[keyi])
		{
			right--;
		}
		//left从左往右找比基准值大的
		while (left <= right && arr[left] < arr[keyi])
		{
			left++;
		}
		//一次循环找到right中最小的与left中最大的,之后进行交换之后将left++、right--
		//若是left>right说明找完了数据已经排好
		if (left <= right)
		{
			Swap(&arr[left++], &arr[right--]);
			//交换取的是地址
		}
	}
	//最后将left与keyi里的值进行交换
	//并且与基准值交换的数一定比基准值小，原因是left经过了left它的目是找比基准值大的数进行交换越过的自然比基准值小
	Swap(&arr[keyi], &arr[right]);
	return right;
	//因为基准值与right交换所以基准值下标为right及要返回right
}


//lomuto前后指针法
int _QuickSort(int* arr, int left, int right)
{
	int keyi = left;
	int prev = left, cur = prev + 1;
	while (cur <= right)
	{
		//判断基准值与arr[cur]的大小如果比基准值小就将prev++并且将prev里的值与cur里面的值交换
		//为啥++prev != cur，因为这样会自己交换自己
		//这样写就可以保证prev的值都是小于基准值的值
		if (arr[cur] < arr[keyi] && ++prev != cur)
			//为啥cur不遍历下标0因为基准值不要和自己比较
		{
			Swap(&arr[prev], &arr[cur]);
		}
		cur++;
	}
	//遍历完后将基准值与prve里的值交换此时基准值在下标prev上即返回prev的下标即可
	Swap(&arr[keyi], &arr[prev]);
	return prev;
}




//快速排序
void  QuickSort(int* arr, int left, int right)
{
	if (left >= right)
	{
		return;
	}
	//快速排序就是排序找基准值递归
	//找基准值
	int keyi = _QuickSort(arr, left, right);
	//将左右两边继续递归运行 左序列[left, keyi - 1] 右序列[keyi + 1, right] 
	QuickSort(arr, left, keyi - 1);
	QuickSort(arr, keyi + 1, right);
}

具体讲解

if (left >= right)
{
	return;
}

递归方法找基准值首先判断是否left >= right如果是那么就说明基准值找完了排序完毕直接返回

int keyi = _QuickSort(arr, left, right);
//将左右两边继续递归运行 左序列[left, keyi - 1] 右序列[keyi + 1, right] 

如果不是那么就找基准值顺便排序
找基准值有两个方法hoare版本和lomuto前后指针法

hoare版本

//hoare版本
int _QuickSort1(int* arr, int left, int right)
{
	int keyi = left;
	++left;
	while (left <= right)
	{
		//right从右往左走找比基准值小的
		while (left <= right && arr[right] > arr[keyi])
		{
			right--;
		}
		//left从左往右找比基准值大的
		while (left <= right && arr[left] < arr[keyi])
		{
			left++;
		}
		//一次循环找到right中最小的与left中最大的,之后进行交换之后将left++、right--
		//若是left>right说明找完了数据已经排好
		if (left <= right)
		{
			Swap(&arr[left++], &arr[right--]);
			//交换取的是地址
		}
	}
	//最后将left与keyi里的值进行交换
	//并且与基准值交换的数一定比基准值小，原因是left经过了left它的目是找比基准值大的数进行交换越过的自然比基准值小
	Swap(&arr[keyi], &arr[right]);
	return right;
	//因为基准值与right交换所以基准值下标为right及要返回right
}

首先默认下标left为下标keyi的基准值
之后加加left(因为基准值不用和自己比较)

while (left <= right)
{
.....
}

在规则范围内left <= right利用while循环使得right从右往左走找比基准值小的，left从左往右找比基准值大的一次循环找到right中最小的与left中最大的,之后进行交换之后将left++、right–接着继续循环
若是left>right说明找完了数据已经排好将下标为基准值的数据与right下标上数据交换，并且与基准值交换的数一定比基准值小，原因是left它的目是找比基准值大的数进行交换越过的自然比基准值小

return right;

最后返回right下标原因是基准值与下标right上的值交换后基准值就在下标right上及返回的就是基准值

	//将左右两边继续递归运行 左序列[left, keyi - 1] 右序列[keyi + 1, right] 
	QuickSort(arr, left, keyi - 1);
	QuickSort(arr, keyi + 1, right);

然后继续找基准值直到left >= right停下快速排序结束

为啥要多次递归找基准值原因是一次找基准值只能保证基准值左边的值都小于它右边的值都大与它并不能做到排序
多次找基准值的目的是将序列范围越来越小在此期间保证基准值左边的值都小于它右边的值都大直到每个小序列里只有一个值的时候就可以实现从小到大排序

---

文章到此就告一段落，希望对你有所帮助，感谢观看!