QuickSort的小思考

前言

！！！数据结构课刚好讲了排序，虽然我之前粗略的学了数据结构，也涉及到了排序，但是对于快速排序的理解太浅了。

然后在课上实现快排时，老是出错，调试也调不对，主要原因是没理解清楚。

虚假的代码

emmm！贴个我课上实现的错误代码吧！

# include <bits/stdc++.h>
using namespace std;

void quickSort(int arr[], int head, int end);
int getPivotPos(int arr[], int head, int end);

void testQuickSort()
{
	int n = 10;
	int arr[] = {46, 13, 55, 42, 94, 5, 17, 70, 82, 100};
	int expect [] = {5, 13, 17, 42, 46, 55, 70, 82, 94, 100};
	quickSort(arr, 0, 9);
	for (int i = 0; i <= n - 1; ++i) {
		if (arr[i] != expect[i]) {
			cout << "FALSE" << endl;
			return;
		}
	}
	cout << "TRUE" << endl;
}

int main()
{
	testQuickSort();
	return 0;
}

void quickSort(int arr[], int head, int end)
{
	if (head < end) {
		int curPos = getPivotPos(arr, head, end);
		quickSort(arr, head, curPos - 1);
		quickSort(arr, curPos + 1, end);
	}
}

int getPivotPos(int arr[], int head, int end)
{
	// 不妨每次去最后一个值
	// 对以基准值为比较对象进行分组
	// 左边小，右边大
	int  pivot = arr[end];
	int pivotPos = end;
	while (head < end) {
		while ((head < end) && arr[end] >= pivot) {
			end -= 1;
		} // 此时已经找到了一个值可能会小于基准值
		if (head < end) {
			int tmp = arr[end];
			arr[end] = pivot;
			arr[pivotPos] = tmp;
			pivotPos = end;
		}
		while ((head < end) && arr[head] <= pivot) {
			head += 1;
		}
		if (head < end) {
			int tmp = arr[head];
			arr[head] = pivot;
			arr[pivotPos] = tmp;
			pivotPos = head;
		}
	}
	return pivotPos;
}

其实问题主要出在getPivotPos这个函数里。这个函数的流程是：

1. 从最右边向左边寻找一个小于基准pivot的值，然后将它与基准值进行交换。（此时，基准值位于从右向左找到的第一个小于pivot的值的地方，而这个值位于原来的pivot值的地方）
2. 然后从左边向右边寻找一个大于基准pivot的值，将它与基准值进行交换。（此时，基准值就位于左边找到的第一个大于基准值的地方。）此时相当于把左边的第一个大于基准值的值和右边一个小于基准值的值进行了交换。
3. 返回此时基准值的位置

其实呢，思路是正确的，但是边界却没有考虑清楚。下面简单示例下（注意我代码的42，43两行）：

这是要交换数据的初始状态：max min 基准值

第一次交换：max 基准值 min

第二次交换：基准值 max min

返回基准值的坐标

石破天惊！！！就是因为，我的基准值是在最右边，并且是从最右边开始寻找的第一个小于基准值的值，交换后，然后再同左边进行交换后，它会导致两个值都在基准值的一侧，所以才会出现上述错误！！！

所以，只要将42，43两行改成：

int pivot = arr[head];
int pivotPos = head;

或者将下面进行交换（两个对应的while循环和if语句）的次序进行一下调整，就不会出现这种问题了！

---

emmm！再贴个改进后的代码凑凑数吧！

# include <bits/stdc++.h>
using namespace std;

void quickSort(int arr[], int head, int end);
int getPivotPos(int arr[], int head, int end);
void quickSort(int arr[], int head, int end)
{
    if (head < end) {
        int curPos = getPivotPos(arr, head, end);
        quickSort(arr, head, curPos - 1);
        quickSort(arr, curPos + 1, end);
    }
}
int getPivotPos(int arr[], int head, int end)
{
    // 不妨每次去最后一个值
    // 对以基准值为比较对象进行分组
    // 左边小，右边大
    int  pivot = arr[end];
    while (head != end) {
        while ((head < end) && arr[head] <= pivot) {
            head += 1;
        } // 此时已经找到了一个值可能会小于基准值
        if (head < end) {
            arr[end] = arr[head];
        }
        while ((head < end) && arr[end] >= pivot) {
            end -= 1;
        }
        if (head < end) {
            arr[head] = arr[end];
        }
    }
    arr[end] = pivot;
    return end;
}

void testQuickSort()
{
    // 10
    //46 13 55 42 94 05 17 70 82 100
    int n;
    cin >> n;
    int arr[n];
    for (int i= 0; i <= n - 1; ++i) {
        cin >> arr[i];
    }
    quickSort(arr, 0, n-1);
    for (int i = 0; i <= n - 1; ++i) {
        cout << arr[i] << " ";
    }

}

int main()
{
    testQuickSort();
}

还是对改进后的代码做个简单的说明吧！嗨！罗里吧嗦的！

1. 改进后的代码，我是默认每次最右边的值为基准值，所以我们要从最左边找到一个大于它的值，将其与这个大于它的值进行交换。但是为什么我们不要把原来大于基准值的位置给覆盖上基准值呢？

2. 因为此时我们已经确定了大于基准值的位置，我们目的也是将这个位置用基准值另一侧小于基准值的值进行覆盖，所以就可以暂时不覆盖。

3. 接着从基准值的最右边开始找到一个小于基准值的值，将这个较小值填入原来那个等待覆盖的地方。此时这个小于基准值的区域等待被基准值覆盖，但是我们还要进行迭代，它的位置被记住了，所以不用管

4. 然后重复上述1，3步骤，直至将数据分好块！此时数据已经分好块了，但是还有个位置被记录了下来，也就是等待被基准值覆盖的位置，进行覆盖即可，然后返回基准值的位置！完成！

小结一下吧！

其实快速排序的主要思想是：通过跨过多个数据进行数据的交换，从而达到少进行数据交换的目的。

主要算法步骤在于：

• 选定基准
• 将数据进行分块，基准左边的数据都小于/大于基准，右边的都大于/小于基准
• 重复n次，就能将数据都排好序

关键步骤就在于，我们将数据进行分块：直接想法就是从基准的右边找到一个小于基准的值，基准左边找到的一个大于基准的值进行交换，这样就不会导致交换后数据还在基准的同一侧！所以，基准选取后，第一个从哪里取要交换的值，这步其实也算是一个关键点吧！

ok，problem solve！