八大排序之快速排序_排序方法快慢顺序

快速排序（英语：Quicksort），又称划分交换排序（partition-exchange sort），简称快排。

基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

通俗的说，就是先选一个标准值，比标准值小的放在左边，比标准值大的放在右边，再将标准值放在中间（这个位置一定是标准值的最终位置）。然后再分别对左右两边的数据进行同样的操作。

快速排序有三种方法：hover（左右指针法），挖坑法，快慢指针法。虽然有三种方法，但这三种方法的核心思想都是一样的。

hover（左右指针法）

首先说明，这里虽然叫指针，但实际还是通过下标来处理
步骤：

• 选择最后一个元素为基准值
• begin从前面开始走，找到比基准值大的元素
• end从后面开始走，找到比基准值小的元素
• 将这两个元素交换，直到begin == end结束
• 将基准值放在中间位置
• 基准值左右两边的数据重复此过程

	int arr[10] = { 5, 2, 6, 8, 1, 9, 0, 3, 7, 4 };
1

代码如下：

	int Partition_01(int arr[], int left, int right)
	{
		int begin = left;
		int end = right;
		while (begin < end)
		{
			while (begin < end && arr[begin] <= arr[right])
			{
				begin++;
			}
			while (begin < end && arr[end] >= arr[right])
			{
				end--;
			}
			Swap(arr + begin, arr + end);
		}
		Swap(arr + begin, arr + right);
		return begin;
	}
	void __QuickSort(int arr[], int left, int right)
	{
		if (left == right)
		{
			return;
		}
		if (left > right)
		{
			return;
		}
		int div = Partition_01(arr, left, right);
	
		__QuickSort(arr, left, div - 1);
		__QuickSort(arr, div + 1, right);
	}
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

挖坑法

挖坑法和左右指针法思想都差不多
步骤：

• 将最后一个元素（基准值）先保存起来，然后把这个位置当做一个坑
• begin从前面找一个比基准值大的元素a，将a放入上述坑中，a原来的位置就是新坑
• end开始从后面找一个比基准值小的元素b，将b放入上述坑中，b原来的位置就是新坑
• 直到begin == end结束
• 最后将基准值放入中间的坑中
• 基准值左右两边的数据按照同样的方法进行操作

	int arr[10] = { 5, 2, 6, 8, 1, 9, 0, 3, 7, 4 };
1

代码如下：

	int Partition_02(int arr[], int left, int right)
	{
		int begin = left;
		int end = right;
		int priot = arr[right];
	
		while (begin < end)
		{
			while (begin < end && arr[begin] <= priot)
			{
				begin++;
			}
			arr[end] = arr[begin];
			while (begin < end && arr[end] >= priot)
			{
				end--;
			}
			arr[begin] = arr[end];
		}
		arr[begin] = priot;
		return begin;
	}
	void __QuickSort(int arr[], int left, int right)
	{
		if (left == right)
		{
			return;
		}
		if (left > right)
		{
			return;
		}
		int div = Partition_02(arr, left, right);
	
		__QuickSort(arr, left, div - 1);
		__QuickSort(arr, div + 1, right);
	}
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

快慢指针

快慢指针思想：慢指针找一个比基准值大的数，快指针找一个比基准值小的数，将两者交换位置。
步骤：

• 快慢指针都从头开始
• 快指针找到比基准值小的数，将快慢指针交换位置，慢指针走一步
  这样就能保证，慢指针要么和快指针指向头一个元素，要么就指向比基准值大的元素
• 最后将基准值放在慢指针的位置
• 对基准值左右两边的数据重复上述过程

	int arr[10] = { 5, 2, 6, 8, 1, 9, 0, 3, 7, 4 };
1

代码如下：

	int Partition_03(int arr[], int left, int right)
	{
		int cur = left;
		int div = left;
		for (; cur < right; cur++)
		{
			if (arr[cur] < arr[right])
			{
				Swap(arr + cur, arr + div);
				div++;
			}
		}
		Swap(arr + div, arr + right);
		return div;
	}
	
	void __QuickSort(int arr[], int left, int right)
	{
		if (left == right)
		{
			return;
		}
		if (left > right)
		{
			return;
		}
		int div = Partition_03(arr, left, right);
	
		__QuickSort(arr, left, div - 1);
		__QuickSort(arr, div + 1, right);
	}
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

总结：

上述快排的三种方法都运用了分而治之的思想，也就是将一个大的问题分割成许多个规模相同的小问题来解决。这三种方法都用到了基准值，都是最后将基准值放在中间位置，确定了基准值的位置，然后将基准值两边的数据按照同样的方法进行操作。