【数据结构】交换排序-快速排序：

时间：2024-01-22 12:50:58

先来数一下快排的整体思想（升序）：

先选出一个关键值，进行一次单趟排序，
这趟排序是怎样的排序呢？
只要确保关键值左边的比关键值小，右边的比关键值大就算一趟排序

单趟排序完成后，我们可以利用遍历二叉树的思想
在这里插入图片描述
最终完成排序，也就是快排

单趟排序：

既然主要部分是单趟排序，那么就有多种单趟排序的办法，这里我们只说最常用的三种

hoare：

hoare是快排的发明者，故hoare自己搞了一个单趟排序，
在这里插入图片描述
思想：
选出一个key值（最左边），
right先走，当 right 找到比 key 小的时候或遇到 left 时停止，
left再走，当 left 找到比 key 大的时候或遇到 right 时停止，
当没有相遇时，他们交换值，
相遇后，将key的值与left（或right，因为相遇时left == right）交换

此时完成单趟排序。

int PartSort1(int* a, int begin, int end)
{
	int left = begin;
	int right = end;
	int keyi = left;
	while (left < right)
	{
		while (left < right && a[right] >= a[keyi])
		{
			right--;
		}
		while (left < right && a[left] <= a[keyi])
		{
			left++;
		}
		//相遇前，left与right的值交换
		Swap(&a[left], &a[right]);
	}
	//相遇后
	Swap(&a[keyi], &a[right]);

	keyi = left;
	//为什么return呢，马上会讲解
	return keyi;
}

挖坑：

挖坑法的思想整体与hoare一致，不过有点差异。
在这里插入图片描述
思想：

将最左边作为关键值，同时作为坑的下标，
同理，right先走，遇到比关键值小的或相遇时停下，将right此时的值给坑，right变成新的坑
left再走，遇到比关键值大的或相遇时停下，将left此时的值给坑，left变成新的坑
当相遇时，将key值给坑

这就是一趟排序

//挖坑
int PartSort2(int* a, int begin, int end)
{
	int left = begin;
	int right = end;
	int key = a[left];
	int holei = left;
	
	while (left < right)
	{
	    // 右边找小，填到左边的坑
		while (left < right && a[right] >= key)
		{
			right--;
		}
		a[holei] = a[right];
		holei = right;
		// 左边找大，填到右边的坑
		while (left < right && a[left] <= key)
		{
			left++;
		}
		a[holei] = a[left];
		holei = left;
	}
	
	a[holei] = key;
	return holei;
}

前后指针：

前后指针的方法与前两者的思想不同。
在这里插入图片描述

分解成一步一步，看到最后发现prev与cur之间的就是比key大的，
最后将prev与key的值交换，完成单趟排序
在这里插入图片描述

这是我们最提倡的一种，根本思想就是：

cur的值大于key时，cur++；
当cur的值小于key时，prev++，将prev与cur的值交换，cur++

int PartSort3(int* a, int begin, int end)
{
	int prev = begin;
	int cur = begin + 1;
	int keyi = begin;
	while (cur <= end)
	{
		if (a[cur] < a[keyi])
		{
			prev++;
			Swap(&a[prev], &a[cur]);
		}
		cur++;
	}
	Swap(&a[prev], &a[keyi]);
	return prev;
}

这里解释一下为什么会返回一个key的下标，因为我们是单趟排序，有多种方案
用下图代码实现快排更为方便

void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
	{
		return;
	}

	int keyi = PartSort3(a, begin, end);
	//begin keyi end
	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi + 1, end);
}

完整代码（3种方式）：

#include "Sort.h"
#include "stack.h"

void Swap(int* e1, int* e2)
{
	int tmp = *e1;
	*e1 = *e2;
	*e2 = tmp;
}
//hoare
int PartSort1(int* a, int begin, int end)
{
	int left = begin;
	int right = end;
	int mid = (left + right) / 2;
	int midi = getmid(a, mid, left, right);
	Swap(&a[left], &a[midi]);

	int keyi = left;
	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[right]);

	keyi = left;
	return keyi;
}

//挖坑
int PartSort2(int* a, int begin, int end)
{
	int left = begin;
	int right = end;
	int mid = (begin - end) / 2;
	int midi = getmid(a, mid, left, right);
	Swap(&a[midi], &a[left]);

	int key = a[left];
	int holei = left;
	while (left < right)
	{
		while (left < right && a[right] >= key)
		{
			right--;
		}
		a[holei] = a[right];
		holei = right;
		while (left < right && a[left] <= key)
		{
			left++;
		}
		a[holei] = a[left];
		holei = left;
	}
	a[holei] = key;
	return holei;
}

//前后指针
int PartSort3(int* a, int begin, int end)
{
	int prev = begin;
	int cur = begin + 1;
	int keyi = begin;
	while (cur <= end)
	{
		if (a[cur] < a[keyi])
		{
			prev++;
			Swap(&a[prev], &a[cur]);
		}
		cur++;
	}
	Swap(&a[prev], &a[keyi]);
	return prev;
}

void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
	{
		return;
	}

	int keyi = PartSort3(a, begin, end);
	//begin keyi end
	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi + 1, end);
}

欢迎讨论哦

相关文章