当前位置:   article > 正文

【数据结构】11.快速排序

【数据结构】11.快速排序

一、快速排序的思想

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

快速排序的实现有以下几种实现方式:

二、hoare版本

2.1 hoare 版本分析

在这里插入图片描述

2.2 honare 版本实现与代码剖析

//升序
//快速排序
void QuickSort(int* arr, int left, int right)
{
	//递归终止条件
	if (left >= right)
	{
		return;
	}
	int begin = left, end = right;
	//先排一趟
	int key = left;
	while (left < right)
	{
		//右面的值比key对应的值大
		while (left < right && arr[right] >= arr[key])
		{
			--right;
		}
		//左面的值比key对应的值小
		while (left < right && arr[left] <= arr[key])
		{
			++left;
		}
		swap(&arr[left], &arr[right]);
	}
	swap(&arr[left], &arr[key]);
	key = left;
	//这样子就会使得key对应的值到达正确的位置
	//开始用begin和end分别保存左右端点值
	//[left,key-1]  key  [key+1,right]
	QuickSort(arr, begin, key - 1);
	QuickSort(arr, key + 1, end);
}
  • 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
  • 32
  • 33
  • 34

在这里插入图片描述

2.2 honare 版本优化

我们知道快速排序的时间复杂度为O(N*logN),但是当数组本身有序或接近有序时的逆序就会导致时间复杂度变成O(N^2),因此我们可以对这种情况进行优化。

2.2.1 随机取key法

//随机取key法
	int randi = rand() % (right - left + 1);
	randi += left;
	swap(&arr[randi], &arr[left]);
	int key = left;
  • 1
  • 2
  • 3
  • 4
  • 5

2.2.2 三数取中法

int GetMideNum(int* a,int left,int right)
{
	int mid = (left + right) / 2;
	

	if (a[left] < a[mid])
	{
		if (a[mid] < a[right])
		{
			return mid;
		}
		else if (a[left] > a[right])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
	else // a[left] > a[mid]
	{
		if (a[mid] > a[right])
		{
			return mid;
		}
		else if (a[left] < a[right])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
}


int randi = GetMideNum(arr, left, right);
swap(&arr[left], &arr[randi]);
int key = left;
  • 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
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41

2.2.3 小区间递归优化

此外,除了时间复杂度的问题,还有空间复杂度的问题。我们知道快排的最后一层函数栈帧的建立就占了全部的50%。因此我们可以进行小区间优化,减少栈帧的浪费,这里可以采用小区间采用插入排序(当数据有序或接近有序时,插入排序处理的很快)。

if (right - left + 1 < 10)
{
	InsertSort(arr, right - left + 1);
}
  • 1
  • 2
  • 3
  • 4

三、前后指针法

3.1 前后指针法分析

在这里插入图片描述

3.2 前后指针法实现

//升序
//快速排序
void QuickSort(int* arr, int left, int right)
{
	if (left >= right)
	{
		return;
	}
	int begin = left, end = right;
	int cur = left+1, prev = 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]);
	key = prev;
	//[left,key-1]  key  [key+1,right]
	QuickSort(arr, begin, key - 1);
    QuickSort(arr, key + 1, end);
}
  • 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

四、非递归的快速排序排序

void QuickSortNonR(int* a, int left, int right)
{
	ST st;
	STInit(&st);
	STPush(&st, right);
	STPush(&st, left);

	while (!STEmpty(&st))
	{
		int begin = STTop(&st);
		STPop(&st);

		int end = STTop(&st);
		STPop(&st);

		// 单趟
		int keyi = begin;
		int prev = begin;
		int cur = begin + 1;

		while (cur <= end)
		{
			if (a[cur] < a[keyi] && ++prev != cur)
				Swap(&a[prev], &a[cur]);

			++cur;
		}

		Swap(&a[keyi], &a[prev]);
		keyi = prev;

		// [begin, keyi-1] keyi [keyi+1, end] 
		if (keyi + 1 < end)
		{
			STPush(&st, end);
			STPush(&st, keyi + 1);
		}

		if (begin < keyi-1)
		{
			STPush(&st, keyi-1);
			STPush(&st, begin);
		}
	}

	STDestroy(&st);
}
  • 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
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
声明:本文内容由网友自发贡献,转载请注明出处:【wpsshop】
推荐阅读
相关标签
  

闽ICP备14008679号