排序算法2：直接选择排序与快速排序

目录

1.直接选择排序

1.1直接选择排序的优化

2.快速排序

2.1基准值的置位（Hoare版）

 2.2挖坑法

2.3lomuto前后指针

---

前言

前面我们进入了排序算的讲解。今天我们将继续学习几种重要的排序思想，好，咱们三连上车开始今天的内容。

1.直接选择排序

在元素的集合中选出最大值（最小值），存放在序列的起始位置，直到全部的待排序位置数据排完

1. 在元素集合中arr[i]-----arr[n-1]中选择值最大（小）数据
2. 若他不是这组元素中的最后一个数据，则将他与这组的最后一个元素交换。
3. 在剩余的arr[i]----arr[n-2](arr[i + 1]-----arr[n-1])的集合中，传重复上面的步骤，直到集合剩余最后一个元素！ 

 思路十分的简单，我们按照这样的思想来实现一下代码：

void SelectSort1(int* arr, int sz)
{
	for (int i = 0; i < sz; i++)
	{
		int begin = i;
		int min = begin;
		for (int j = begin + 1; j < sz; j++)
		{
			if (arr[min] > arr[j])
			{
				min = j;
			}
		}
		Swap(&arr[min], &arr[begin]);
	}
}

 

 我们这样就实现了排序的目的，但是大家也不难看出，直接这样的排序跟冒泡排序相差无几，同样的效率低下，想要扩大他的使用场景，就要将他进行进一步的优化。

1.1直接选择排序的优化

原来的直接选择排序在排序时只是将特定范围内的最小值与该范围内的第一个元素进行交换，那如果我们在寻找最小值的同时，也来寻找最大值来与最后面的元素进行交换，这样就可以大幅提高排序的效率了。

按照这个思路我们来实现这个代码：

void SelectSort(int* arr, int sz)
{
	int begin = 0;
	int end = sz - 1;
	while (end > begin)
	{
		int min = begin;
		int max = begin;
		//找特定范围中最小的值和最大值
		for (int j = begin + 1; j <= end; j++)
		{
			if (arr[min] > arr[j])
				min = j;
			if (arr[max] < arr[j])
				max = j;
		}
		//避免max与begin都在同一位置，begin和min进行交换后，max数据变成了最小的数据
		if (max == begin)
		{
			max = min;
		}
		Swap(&arr[min], &arr[begin]);
		Swap(&arr[max], &arr[end]);
		end--;
		begin++;
	}
}

直接选择牌序的优化就完成了！！ 

2.快速排序

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

2.1基准值的置位（Hoare版）

这里我们单独创建一个函数来查找排序区域的基准值位置:

int FindKey(int* arr, int left, int right)
{
	//从左边找比基准值大的数据
	//从右边找基准值较小的数据
	int key = left;
	left++;
	while (left <= right)
	{
		while (left <= right&&arr[left] < arr[key])
		{
			left++;
		}
		while (left <= right && arr[right] > arr[key])
		{
			right--;
		}
		if (left <= right)
		Swap(&arr[right--], &arr[left++]);//在遇到一定区域内的值都相等时，需要让基准值的位置向中间移，这样才能让区域越划越小
	}
		Swap(&arr[key], &arr[right]);
	return right;
}

找到基准值后，我们根据二叉树结构的性质，很容易就能够确定使用递归的思想来实现循环划分左右子区域的操作：

void QuickSort(int* arr, int left, int right)
{
	if (left >= right)
		return;
	//left and right----->找基准值mid
	//1.如何找基准值
	int keyi = FindKey(arr, left, right);
	//左子序列
	QuickSort(arr, left, keyi - 1);
	//右子序列
	QuickSort(arr, keyi + 1, right );
}

 所以Hoare版的快速排序我们就完成了，接下来我们来验证一下：

int FindKey(int* arr, int left, int right)
{
	//从左边找比基准值大的数据
	//从右边找基准值较小的数据
	int key = left;
	left++;
	while (left <= right)
	{
		while (left <= right&&arr[left] < arr[key])
		{
			left++;
		}
		while (left <= right && arr[right] > arr[key])
		{
			right--;
		}
		if (left <= right)
		Swap(&arr[right--], &arr[left++]);//在遇到一定区域内的值都相等时，需要让基准值的位置向中间移，这样才能让区域越划越小
	}
		Swap(&arr[key], &arr[right]);
	return right;
}
void QuickSort(int* arr, int left, int right)
{
	if (left >= right)
		return;
	//left and right----->找基准值mid
	//1.如何找基准值
	int keyi = FindKey(arr, left, right);
	//左子序列
	QuickSort(arr, left, keyi - 1);
	//右子序列
	QuickSort(arr, keyi + 1, right );
}

 

快速排序在实际的生活工作场景中运用广泛，这得益于他二叉树的结构性质，使其拥有了与堆排序相近甚至更快的速率。 

 2.2挖坑法

思路：创建左右指针。首先从右向左找比基准值小的数据，找到后立即放入左边的坑位，当前位置变为新的“坑”， 然后从左向右找比基准值大的数据，找到后立即放入右边的坑洞中，当前位置变为新的坑，结束循环后将最开始存储的分界值放入当前的“坑”中，返回当前“坑”的下标（即分界值下标）。

 挖坑法相较于Hoare的方法要简单，我们稍加理解就可以将代码写出来。

我们来看代码：

int _QuickSort(int* a, int left, int right)
{
	int mid = a[left];
	int hole = left;
	int key = a[hole];
	while (left < right)
	{
		while (left < right && a[right] >= key)
		{
			--right;
		}
		a[hole] = a[right];
		hole = right;
		while (left < right && a[left] <= key)
		{
			++left;
		}
		a[hole] = a[left];
		hole = left;
	}
	a[hole] = key;
	return hole;
}

本质上这时一种新的找基准值的方法，虽然相较于Hoare版的代码挖坑法的代码会更加的冗余，但是他的思想和实现方法更易于理解。

int _QuickSort(int* a, int left, int right)
{
	int mid = a[left];
	int hole = left;
	int key = a[hole];
	while (left < right)
	{
		while (left < right && a[right] >= key)
		{
			--right;
		}
		a[hole] = a[right];
		hole = right;
		while (left < right && a[left] <= key)
		{
			++left;
		}
		a[hole] = a[left];
		hole = left;
	}
	a[hole] = key;
	return hole;
}
void QuickSort(int* arr, int left, int right)
{
	if (left >= right)
		return;
	//left and right----->找基准值mid
	//1.如何找基准值
	int keyi = _QuickSort(arr, left, right);
	//左子序列
	QuickSort(arr, left, keyi - 1);
	//右子序列
	QuickSort(arr, keyi + 1, right );
}

 

经过验证，我们的代码就实现了！ 

2.3lomuto前后指针

创建前后指针，从左往右找比基准值小的进行交换，使得小的数据都排在基准值的左边。

 

前后指针法相比于前面的挖坑法和Hoare方法都要简单，但是思路着实不好想，这就需要我们积累新的方法了：

• 定义两个指针 prev和cur;
•  cur指向的位置的数据跟key的值比较；
• 若arr[cur] < arr[key],prev向后走一步并和cur交换；
• 若arr[cur] >= arr[key],cur继续向后

int Doublelomuto(int *arr, int left, int right)
{
	int prev = left, cur = left;
	int key = left;
	while (cur <= right)
	{
		if (arr[cur] < arr[key] && ++prev != cur)
		{
			Swap(&arr[prev], &arr[cur]);
		}
		cur++;
	}
	Swap(&arr[key], &arr[prev]);
	return prev;
}

最后我们来验证一下这个代码：

int Doublelomuto(int *arr, int left, int right)
{
	int prev = left, cur = left;
	int key = left;
	while (cur <= right)
	{
		if (arr[cur] < arr[key] && ++prev != cur)
		{
			Swap(&arr[prev], &arr[cur]);
		}
		cur++;
	}
	Swap(&arr[key], &arr[prev]);
	return prev;
}
void QuickSort(int* arr, int left, int right)
{
	if (left >= right)
		return;
	//left and right----->找基准值mid
	//1.如何找基准值
	int keyi = Doublelomuto(arr, left, right);
	//左子序列
	QuickSort(arr, left, keyi - 1);
	//右子序列
	QuickSort(arr, keyi + 1, right );
}

快速排序的三种版本的递归排序方法就实现完了。

好今天的学习就到这里，我们下期再见，拜拜！！