文章目录

---

前言

排序有多种算法，其中快速排序（以下简称快排）因时间复杂度明显优于其他算法，故在日常使用中较为频繁。快排算法多样，包含：左右指针法，挖坑法，前后指针法等。这篇文章主要讲解左右指针法。

一、思路

现有以一数组，假设我们排升序。

1.排单趟：

定义两个变量begin和end，一个在指向前一个指向后。用数组a[end]的值做key。再定义一个keyIndex=end；

注意：当相遇时，begin=end，但不是交换swap[&key,&a[begin]，key存储在另一个地址是一个局部变量！我们应该交换的是一开始存储的swap[&a(keyIndex),&a[begin])!!

当交换完后，此时单趟排序完成，有这样的效果：左边的比key小，右边的比key大！

计算时间复杂度：基本操作相当于begin和end将数组遍历了一遍，即O(N)；

以下为单趟排序代码：

int OneSort(int* a, int begin, int end)
{

	int mid = GetMidNum(a, begin, end);
	swap(&a[mid], &a[end]);

	int key = a[end];
	int keyIndex = end;//储存key的下标

	while (begin < end)
	{
		//找大
		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左边与key右边两个区间。

下一步我们用递归思想在这两个区间分别再找“key”重复单趟排序，直到分为不能再分的单个数据，或者超出数组界限begin大于end。

计算时间复杂度：在理想情况下，该递归过程类似于二叉树为O(logN)。

以下为第二部分代码：

void QuickSort(int* a, int left, int right)
{
	if (left >= right)
	{
		return;
	}

	int div = OneSort(a, left, right);
	QuickSort(a, left, div - 1);
	QuickSort(a, div + 1, right);
}

3.三数取中

通过上诉思想，固然可以将一个数组排成有序段，但却有个条件即以下为理想情况，即啊a[end]的值刚好在数组中间。

若是遇到特殊情况，a[end]每次取值不是最大就是最小，则整个算法的时间复杂度会到O(N^2)!!

为解决这个办法，我门采取三数取中思想，确保每次不选到最大或最小的值。

int GetMidNum(int* a, int begin, int end)
{
	assert(a);

	int mid = (begin + end) / 2;

	if (a[begin] > a[mid])
	{
		if (a[mid] > a[end])
			return mid;
		else if (a[begin] > a[end])//a[end]>a[mid]
			return end;
		else
			return begin;
	}
	else//a[mid]>a[begin]
	{
		if (a[end] > a[mid])
			return mid;
		else if (a[begin] > a[end])
			return begin;
		else
			return end;
	}
}

二、完整代码

#include<stdio.h>

void QuickSort(int* a, int left, int right);

int OneSort(int* a, int begin, int end);

int GetMidNum(int* a, int begin, int end);

void swap(int* p1, int* p2)
{
	int tem = *p1;
	*p1 = *p2;
	*p2 = tem;
}

int OneSort(int* a, int begin, int end)
{

	int mid = GetMidNum(a, begin, end);
	swap(&a[mid], &a[end]);

	int key = a[end];
	int keyIndex = end;//储存key的下标

	while (begin < end)
	{
		//找大
		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;
}

void QuickSort(int* a, int left, int right)
{
	if (left >= right)
	{
		return;
	}

	int div = OneSort(a, left, right);
	QuickSort(a, left, div - 1);
	QuickSort(a, div + 1, right);
}

int GetMidNum(int* a, int begin, int end)
{

	int mid = (begin + end) / 2;

	if (a[begin] > a[mid])
	{
		if (a[mid] > a[end])
			return mid;
		else if (a[begin] > a[end])//a[end]>a[mid]
			return end;
		else
			return begin;
	}
	else//a[mid]>a[begin]
	{
		if (a[end] > a[mid])
			return mid;
		else if (a[begin] > a[end])
			return begin;
		else
			return end;
	}
}


void test()
{
	int a[] = { 4,2,6,8,7,4,9,6,8,11 };
	int size = sizeof(a) / sizeof(a[0]);
	for (int i = 0; i < size; ++i)
	{
		printf("%d ", a[i]);
	}
	printf("\n");

	QuickSort(a, 0, size - 1);
	for (int i = 0; i < size; ++i)
	{
		printf("%d ", a[i]);
	}
}
int main()
{
	test();
	return 0;
}