深入理解数据结构第五弹——排序（2）——快速排序

深入理解数据结构之快速排序超详细讲解！！！（新手小白无脑入即可）

朝九晚五ฺ

3761人浏览 · 2024-04-13 21:02:51

朝九晚五ฺ · 2024-04-13 21:02:51 发布

排序（1）：深入了解数据结构第四弹——排序（1）——插入排序和希尔排序-CSDN博客

前言：

在前面我们已经讲过了几种排序方式，他们的效率有快有慢，今天我们来学习一种非常高效的排序方式——快速排序

一、快速排序的思想

快速排序是一种常用的排序算法，属于比较排序的一种。它的基本思想是先选取一个基准数据，经过一趟排序，让比它小的分为一部分，比它大的分为另一部分，然后再对这两部分继续这种操作，直到他们有序

快速排序的具体步骤如下：

选择一个基准元素（通常是待排序数组的第一个元素、最后一个元素或者中间元素）。
将比基准元素小的元素放在基准元素的左边，比基准元素大的元素放在基准元素的右边，这一步称为分区操作。
对基准元素左右两部分分别递归地进行快速排序。

比如这样一组数据{ 4,7,1,9,3,6,5,8,3,2,0 }

1、首先我们先选择一个基准元素（我们以最左边的元素为基准元素为例）

2、对剩下的元素进行排序，比基准元素小的排在左边，比基准元素大的排在右边

3、对小的部分和大的部分重复上面两部操作，最后我们就可以得到一个有序的数组

这一步就可以清楚的看到其实快排的这种思想很像二叉树，所以很容易通过类似二叉树递归的那种思想来解决

二、快速排序的递归实现

快排的实现其实是很有意思的，在上面我们已经讲了快排的思想，其实就是不断的重复分区操作的过程，所以我们就可以设计一个递归来实现这种，同时，由于每一步都要进行分区，所以我们可以封装一个分区排序函数（PartSort函数）在前，重复这个过程

void QuickSort(int* a, int begin,int end)
{
	if (begin >= end)
	{
		return;
	}
	int keyi = PartSort3(a, begin, end);
	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi + 1, end);
}

其中参数a是数组指针，begin是传入数组的首元素位置，end是传入元素尾元素位置，过程图如下：

快排函数的主体就是上面那几步，接下来，我们重点讲解一下快排分区排序函数（PartSort函数）该如何实现，这一步也是非常有趣的，目前我们有三种方法来实现这个函数的功能：

1、霍尔排序

2、挖坑法

3、前后指针法

2.1 霍尔法

霍尔法是霍尔大佬（就是快排的发明者）自己刚开始用的排序方法，但是由于这种分部排序方法需要注意到的点太多，所以后来才又有了后面两种排序方法，现在我们先来学习一下霍尔大佬的这种方法

霍尔排序其实就是严格按照我们上面讲的快排的那种思想进行的，就是先选一个基准数，然后对后面数进行大致的判断，让比基准数小的位于基准数左侧，比基准数大的位于基准数右侧

霍尔实现这个过程的方法就是先选取最左边的元素作为基准元素，然后记录剩下元素左右位置，然后让左边向右移动，当遇到一个比基准元素大的数就停下来，右边向左移动，遇到一个小于基准元素的数停下来，然后让左右这两个数交换

然后再讲左右两部分分开再进行类似的操作

由图可见这是一种类似二叉树的操作，所以非常适合用递归来解决，具体代码如下：

int GetMid(int* a, int left, int right)
{
	int mid = (left + right) / 2;
	if (a[left] > a[mid])
	{
		if (a[right] > a[left])
			return left;
		else if (a[right] < a[mid])
			return mid;
		else
			return right;
	}
	else
	{
		if (a[right] < a[left])
			return left;
		else if (a[right] > a[mid])
			return mid;
		else
			return right;
	}
}
//1、hero 霍尔排序
//[left,right]
int PartSort(int* a, int left, int right)
{
	int mid = GetMid(a, left, right);
	Swap(&a[mid], &a[left]);
	int keyi = left;
	while (left < right)
	{
		while (left < right && a[left] <= a[keyi])
		{
			left++;
		}
		while (left < right && a[right] >= a[keyi])
		{
			right--;
		}
		Swap(&a[left], &a[right]);
	}
	Swap(&a[left], &a[keyi]);
	return left;
}

但前面我们也已经提到过了，霍尔排序有一些细节是一定要处理到位的，就比如

1、如果取左边数为基准元素，右边就要先开始移动（right - -），反之就左边先开始移动，否则就容易可能会出现溢出的现象

2、要注意当左右移动到的那个元素等于基准元素时是要跳过的，同时最后left==right时要将这个元素与基准元素交换

3、如果对于一个较为有序的函数，比如{1,2,4,5,7,3,9,8},快排的效率其实是偏低的，因为我们刚开始选的基准元素基本没啥作用，所以我们选择的基准元素要尽可能贴近中间值，所以就有了上述代码中的GetMid函数

2.2 挖坑法

鉴于霍尔法注意事项太多，且霍尔法较难理解，后面又有大佬总结出挖坑法这一思路相同，但更形象更容易理解的方法

挖坑法的思路如下：

先以左边元素为基准元素，然后将这个元素挖出，将这个位置理想化成一个坑，然后再从右边向左边移动，找到一个小于基准数的数后将它放入坑中，将这个位置作为新的坑，再从左边往右边去，找到一个大于基准数字的数，填入坑中，将这个位置作为新坑，直到最后将基准数字放入最后的坑中

挖坑法的思路要比霍尔法，简单很多，实现如下：

//2、挖坑法
int PartSort2(int* a,int left,int right)
{
	int mid = GetMid(a, left, right);
	Swap(&a[mid], &a[left]);
	int key = a[left];
	int hole = left;
	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 left;
}

2.3 前后指针法

前后指针法是一个更容易理解的很不错的方法，体现了后人的智慧

前后指针法的思路如下：

首先先将最左边元素作为基准元素，然后定义一个prev表示后指针，定义一个cur表示前指针，cur=prev+1，然后让前指针先走，当遇到一个小于基准元素的数时停下来，然后让后指针走一步，然后交换这两个数据，直到前指针把所有数据走完

实现上述过程的代码：

//3、前后指针法
int PartSort3(int* a, int left, int right)
{
	int mid = GetMid(a, left, right);
	Swap(&a[mid], &a[left]);
	int prev = left;
	int cur = prev + 1;
	int keyi = left;
	while (cur <= right)
	{
		if (a[cur] < a[keyi])
		{
			prev++;
			Swap(&a[prev], &a[cur]);
		}
		cur++;
	}
	Swap(&a[prev], &a[keyi]);
	return prev;
}

三、快排的非递归实现

这个由于篇幅问题，留在下一章进行讲解（其实是本人累了.......坐在这写一下午了，呜呜呜呜呜........)，这个明天写，嘿嘿

四、完整代码示例

上面我们就已经把快排的几种分部处理的方法和思想讲的很清楚了，接下来，我们就通过一个完整的代码实例来感受快排的魅力所在

对数组{ 4,7,1,9,3,6,5,8,3,2,0 }进行快排

Seqlish.h

//快速排序
void QuickSort(int* a, int begin, int end);

Seqlish.c

//快速排序
void PrintArray(int* a, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}
void Swap(int* e1, int* e2)
{
	int tmp = *e1;
	*e1 = *e2;
	*e2 = tmp;
}
int GetMid(int* a, int left, int right)
{
	int mid = (left + right) / 2;
	if (a[left] > a[mid])
	{
		if (a[right] > a[left])
			return left;
		else if (a[right] < a[mid])
			return mid;
		else
			return right;
	}
	else
	{
		if (a[right] < a[left])
			return left;
		else if (a[right] > a[mid])
			return mid;
		else
			return right;
	}
}
//1、hero 霍尔排序
//[left,right]
int PartSort(int* a, int left, int right)
{
	int mid = GetMid(a, left, right);
	Swap(&a[mid], &a[left]);
	int keyi = left;
	while (left < right)
	{
		while (left < right && a[left] <= a[keyi])
		{
			left++;
		}
		while (left < right && a[right] >= a[keyi])
		{
			right--;
		}
		Swap(&a[left], &a[right]);
	}
	Swap(&a[left], &a[keyi]);
	return left;
}
//2、挖坑法
int PartSort2(int* a,int left,int right)
{
	int mid = GetMid(a, left, right);
	Swap(&a[mid], &a[left]);
	int key = a[left];
	int hole = left;
	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 left;
}
//3、前后指针法
int PartSort3(int* a, int left, int right)
{
	int mid = GetMid(a, left, right);
	Swap(&a[mid], &a[left]);
	int prev = left;
	int cur = prev + 1;
	int keyi = left;
	while (cur <= right)
	{
		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);
	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi + 1, end);
}

test.c

//测试快速排序
void TestQuick()
{
	int a[] = { 4,7,1,9,3,6,5,8,3,2,0 };
	PrintArray(a, sizeof(a) / sizeof(a[0]));
	//QuickSort(a, 0, sizeof(a) / sizeof(a[0]) - 1);      //递归快排
	QuickSortNonR(a, 0, sizeof(a) / sizeof(a[0]) - 1);    //非递归快排

	PrintArray(a, sizeof(a) / sizeof(a[0]));
}

int main()
{
	TestQuick();
	return 0;
}

运行结果如下：