思路:

1.找一个支点元素pivot,一般选这组数的第一个

2.把大于pivot的数都放在它的右边,小于它的数都放在左边

3.分别对左右子序列进行1、2步操作(分治策略的体现)

示例:

19    97    09    17    01    08

Pivot

↑                                        ↑   

L                                       R

选择第一个元素(19)作为支点pivot,L和R是两个指针,相向移动(R先移动)R要找的是小于pivot的元素,L要找的是大于pivot的元素(因为他们不属于这里),然后二者交换

最后LR重合时,pivot更换到这个位置   

19    97    09    17    01    08

Pivot

         ↑                              ↑   

         L                             R

   

这时R找到了比pivot小的元素8,L找到了比pivot大的元素97,swap这两个

19    08    09    17    01    97

Pivot

        ↑                               ↑   

        L                              R

R向左移动,找到比pivot小的01,L向右移动,一直移动没找到比pivot大的,然后就与R重合了

19    08    09    17    01    97

Pivot

                                ↑↑   

                               LR

然后把重合位置的元素与pivot交换

01    08    09    17    19    97

                              Pivot

                                ↑↑   

                                LR

此时19就已经到了他应该在的正确位置了

接下来要做的事情就是对19左右两边的子数组递归进行上述操作

左边的子数组:

老规矩,第一个做pivot

01    08    09    17

Pivot

↑                       ↑

L                      R

01    08    09    17

Pivot

↑↑

L  R

R向左移动,没有找到,一直走,与L在初始位置重合,pivot就在这个地方,不用交换了。

(一定要R先走)

此时pivot:01就在自己合适的位置了,再对他左右子数组递归进行上述操作

因为左边没有东西,那就只对右边的子数组操作

同理,R也在L的初始位置与R重合了

08    09    17

Pivot

↑↑

L  R

以此类推,再处理 09   17

就把 01    08    09    17 排好了

到了第二层的右子数组:就 97 一个数字

不用排了,直接排好

所以最终结果就是:
01    08    09    17    19    97

(第一次排序直接就是这个结果,仅仅是巧合)

对一定要R先走的说明:

    当pivot取最左边的数字,就应该R先走,若pivot取最右边的数字,则L先走。

(无论升序降序都是这样)

代码:

//快速排序
#include <iostream>
using namespace std;
void quicksort(int*arr, int left, int right)
{
	if (left >= right)  //首先判断一下传递进来的left和right合不合理
	{
		return;
	}
	int i = left;
	int j = right;    //把left和right赋值给i,j作为他们的初始状态
	int pivot = arr[left];  //让最左边的元素作为支点pivot
	//不是0开始,要递归调用,比如pivot右边的子数组初始下标就不是0,所以不是arr[0]
	while (i < j)  //i与j碰到时,结束一次排序,所以i<j是循环条件
	{
		while (arr[j] >= pivot && i < j)
		{
			j--;  //j(R)要找的是小于pivot的数,所以当arr[j]>=pivot时,此数不用操作,j向左移动(别忘了i<j的限制条件)
		}
		while (arr[i] <= pivot && i < j)
		{
			i++;  //i(L)要找的是大于pivot的数,所以当arr[i]<=pivot时,此数不用操作,i向右移动(别忘了i<j的限制条件)

		}
		if (i < j)  //执行到这一语句,说明j和i都停下来了,若满足i<j则可以进行交换了
		{
			swap(arr[i], arr[j]);
		}
	}
	swap(arr[left], arr[i]); //支点回归它正确的位置。执行到这句的时候,即已经跳出循环了,即i和j相交了。此时交换pivot和arr[i](或arr[j])(此时是一个数)
	quicksort(arr, left, i - 1);  //递归pivot左边的子数组
	quicksort(arr, i + 1, right);  //递归pivot右边的子数组
}
int main()
{
	int a[8] = { 8,3,4,2,5,7,1,6 };
	quicksort(a, 0, 7);
	for (int k = 0; k < 8; k++)
	{
		cout << a[k] << ' ';
	}
	return 0;
}


输出:1 2 3 4 5 6 7 8 

若要进行从大到小的排序:

只需要对一小部分进行修改

//快速排序降序版本
//思路:与升序不同的是,L找的是小于pivot的数,R找的是大于pivot的数,大于pivot的全在左边,小于的全在右边
#include <iostream>
using namespace std;
void quicksort1(int* arr, int left, int right)
{
	if (left >= right)
	{
		return;
	}
	int i, j;
	i = left;
	j = right;
	int pivot = arr[left];
	while (i < j)
	{
		while (arr[j] <= pivot && i < j)
		{
			j--;
		}
		while (arr[i] >= pivot && i < j)
		{
			i++;
		}
		if (i < j)
		{
			swap(arr[i], arr[j]);
		}
	}
	swap(arr[left], arr[i]);
	quicksort1(arr, left, i - 1);
	quicksort1(arr, i + 1, right);
}
int main()
{
	int a[8] = { 8,3,4,2,5,7,1,6 };
	quicksort1(a, 0, 7);
	for (int k = 0; k < 8; k++)
	{
		cout << a[k] << ' ';
	}
	return 0;
}

输出:8 7 6 5 4 3 2 1

快速排序的时间复杂度:

平均:O(nlogn)

最快:O(nlogn)

最慢:O(n^2)

Logo

瓜分20万奖金 获得内推名额 丰厚实物奖励 易参与易上手

更多推荐