快速排序(hoare法，刨坑法，前后指针法)及非递归实现

103 阅读 0 评论 68 点赞

我是靠谱客的博主虚心大象，这篇文章主要介绍快速排序(hoare法，刨坑法，前后指针法)及非递归实现，现在分享给大家，希望可以做个参考。

原理：
快速排序（Quicksort）是对冒泡排序的一种改进。
快速排序由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

单趟排序：将比key小和相等的放在左边，将比key大和相等的放到右边

单趟排序的变形

1.hoare法，2.刨坑法，3.前后指针法。

1. hoare法

最右边做key，左边先走；左边做key，右边先走。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
void Swap(int *a, int *b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

int HoareSort(int *a, int begin,int end)
{
	//end做key,左边先走，begin做key,右边先走

	int key = a[end];
	int keyindex = end;
	while (begin < end)
	{
		//begin找大
		while (begin < end && a[begin] <= key)
		{
			++begin;
		}
		while (begin < end && a[end] >= key)
		{
			--end;
		}
		Swap(&a[begin], &a[end]);
	}
	Swap(&a[begin], &a[keyindex]);
	return begin;
}

2. 刨坑法

key=6

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int PitSort(int *a, int begin, int end)
{
	int key = a[end];
	while (begin < end)
	{
		//begin找大
		while (begin < end && a[begin] <= key)
		{
			++begin;
		}
		a[end] = a[begin];//找到大扔到右边的坑里去
		while (begin < end && a[end] >= key)
		{
			--end;
		}
		a[begin] = a[end];//找到小就扔到左边的坑里去
	}
	a[begin]=key;
	return begin;
}

3. 前后指针法

1. 定义变量cur指向序列的开头begin，定义变量prev指向cur的前一个位置begin-1。
2. 当array[cur] < key时，++prev，当++prev != cur时，Swap(&array[cur],&array[prev])。
3. 当cur=end时，++prev，Swap(&array[prev],&array[end])。
图示如下：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//前后指针版本
int PrevCurSort(int *a, int begin, int end)
{
	int cur = begin;
	int prev=begin-1;
	int key = a[end];

	while (cur < end)//遇到key的位置就结束了
	{
		if (a[cur] < key && ++prev != cur)
			Swap(&a[cur], &a[prev]);
		++cur;
	}
	++prev;
	Swap(&a[prev],&a[end]);

	return prev;
}

最坏时间复杂度O(N^2)：数组有序，每次选key=a[end]。

改进方法：三数取中(key)；获得中间位置下标midindex，将a[midindex]与a[end]交换。可以把有序这种最坏的情况变成O(N*logN)。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//优化
int GetMidIndex(int *a, int begin, int end)
{
	int mid = (begin + end) >> 1;
	//begin mid end
	if (a[begin]>a[mid])
	{
		if (a[mid] > a[end])
			return mid;
		else if (a[begin] < a[end])//a[mid]<a[end]
			return begin;
		else
			return end;
	}
	else //a[begin]<a[mid]
	{
		if (a[mid] < a[end])
			return mid;
		else if (a[begin]>a[end])//a[mid] > a[end]
			return begin;
		else
			return end;
	}
}

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//前后指针版本
int PrevCurSort(int *a, int begin, int end)
{
	int midindex = GetMidIndex(a, begin, end);
	Swap(&a[midindex], &a[end]);

	int cur = begin;
	int prev=begin-1;
	int key = a[end];

	while (cur < end)//遇到key的位置就结束了
	{
		if (a[cur] < key && ++prev != cur)
			Swap(&a[cur], &a[prev]);
		++cur;
	}
	++prev;
	Swap(&a[prev],&a[end]);

	return prev;
}

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
void QuickSort(int *a, int begin, int end)
{
	if (begin >= end)
		return;

	//int keyindex = HoareSort(a, begin, end);
	//int keyindex = PitSort(a, begin, end);
	int keyindex = PrevCurSort(a, begin, end);

	QuickSort(a, begin, keyindex - 1);
	QuickSort(a, keyindex + 1, end);
}

复制代码

1
2
3
4
5
6
7
8
9
10
11
int main()
{
	int a[] = {6,1,2,7,6,9, 3, 4, 5, 10, 8};
	//BubbleSort(a, sizeof(a) / sizeof(int));
	//PartSort(a, 0, sizeof(a) / sizeof(int)-1);
	
	QuickSort(a, 0, sizeof(a) / sizeof(int)-1);
	PrintfArray(a, sizeof(a) / sizeof(int));
	system("pause");
	return 0;
}

非递归实现

为什么会有非递归：递归如果太深，会导致栈溢出。

递归的算法主要是在划分子区间，如果要非递归实现快排，只要使用一个栈来保存区间就可以了。一般将递归程序改成非递归首先想到的就是使用栈，因为递归本身就是一个压栈的过程。

方法：用栈代替递归，每次用递归的时候均入栈，每次运算的时候均出栈，栈为空则完成排序。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
// 非递归
void QuickSortNonR(int* a, int begin, int end)
{
	// 数据结构的栈来模拟递归
	Stack st;
	StackInit(&st);
	StackPush(&st, begin);
	StackPush(&st, end);
	while (!StackEmpty(&st))
	{
		int right = StackTop(&st);
		StackPop(&st);
		int left = StackTop(&st);
		StackPop(&st);
		int keyindex = PrevCurSort(a, left, right);
		//[left, keyindex-1] keyindex [keyindex+1, right]
		if (left < keyindex-1)
		{
			StackPush(&st, left);
			StackPush(&st, keyindex - 1);
		}
		if (keyindex+1 < right)
		{
			StackPush(&st, keyindex+1);
			StackPush(&st, right);
		}
	}


	StackDestroy(&st);
}