C++实现快速排序，最简单的代码（详细解读）_快速排序c++代码

快速排序的过程是这样的：

假设我们现在对“6 1 2 7 9 3 4 5 10 8”这个10个数进行排序。首先在这个序列中随便找一个数作为基准数（不要被这个名词吓到了，就是一个用来参照的数，待会你就知道它用来做啥的了）。为了方便，就让第一个数6作为基准数吧。接下来，需要将这个序列中所有比基准数大的数放在6的右边，比基准数小的数放在6的左边，类似下面这种排列。

   3  1  2 5  4  6  9 7  10  8
1

方法其实很简单： 分别从初始序列“6 1 2 7 9 3 4 5 10 8”两端开始“探测”。先从右往左找一个小于6的数，再从左往右找一个大于6的数，然后交换他们。这里可以用两个变量i和j，分别指向序列次左边和最右边。我们为这两个变量起个好听的名字“哨兵i”和“哨兵j”。刚开始的时候让哨兵i指向序列的次左边（即下标为1），指向数字1。让哨兵j指向序列的最右边（即下标为9），指向数字8。

哨兵i从左往右依次寻找到第一个比基准大的数，哨兵j从右往左依次寻找到第一个比基准小的数，然后交换。

交换：注意：交换之前需要检查i是否小于j，只有i < j的时候才能交换。否则不交换，然后进入最后的基准的位置调整。

再继续往前寻找（哨兵i寻找比基准大，哨兵j寻找比基准小的），直到哨兵i，j相遇或者j < i。

交换：

继续找：

这里由于不满足i < j，因此3和9不会进行交换。退出循环。

现在我们发现以3和9的中间为界，除了基准6以外，比6小的都在左边，比6大的都在右边。因此，此时还需要调整基准的位置。

这里需要注意的是，当选择的基准在最左边时，需要和右指针也就是j做交换；
如果选择的基准在最右边，则基准和左指针i进行交换。

当我们第一次排序结束以后，就需要对原数组进行划分处理，以上一个基准为界，分为两个数组，如下

然后再对子数组进行上述的排序操作，这是一个递归的思想。

上代码：

int quick(int *arr,int leftbound,int rightbound)
{
	int leftptr = leftbound+1;
	int rightptr = rightbound;
	int pivot = arr[leftbound];
	while(leftptr <= rightptr)
	{
		
		while(leftptr <= rightptr && arr[leftptr] < pivot)
		{
			leftptr++;
		}
		while(leftptr <= rightptr&& arr[rightptr] >= pivot)
		{
			rightptr--;
		}

		if(leftptr < rightptr)
		{
			swap(arr,leftptr,rightptr);
		}
	}

	swap(arr,leftbound,rightptr);
	return rightptr;
}

void quick_sort(int *arr,int left,int right)
{
	if(right <= left)
	{
		return;
	}
	int mid = quick(arr,left,right);
	quick_sort(arr,left,mid-1);
	quick_sort(arr,mid+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

要点：

1. 每次进入做交换的循环之前，需要判断左指针的下标是否小于等于右指针的下标，若小于等于则进入循环，否则不进入循环。

2. 轴选在左侧，则判断左指针指向的值的时候，该值只有小于轴指向的数值的时候，左指针才会继续向右移，即左指针指向的值一定大于轴指向的值，不可以等于，否则排序会出错。然而，判断右指针的时候一定要包含轴的值。 反之，轴在右侧，则左指针的判断一定要包含轴，右指针则不能包含。

3. 左右指针的值做交换之前，需要判断左指针（下标）是否小于右指针（下标），小于则进行交换，否则（大于等于）则不进行交换。

4. 轴在左侧，则最后调整轴的位置的时候，需要将轴与右指针最后指向的位置的值做交换。轴在右侧的时候，则与左指针做交换。