快速排序是冒泡排序的进阶版本，在冒泡排序中，进行元素的比较和交换是在相邻元素之间进行的，元素每次交换只能移动一个位置，所以比较次数和移动次数较多，效率相对较低。而在快速排序中，元素的比较和父换是从网端向中间进行的，较大的元素一轮就能够交换到后面的位置，而较小的元素一轮就能交换到前面的位置，元素每次移动的距离较远，所以比较次数和移动次数较少，就像它的名字一样，速度更快。

设数组长度为N，详细过程为:

• 在一开始，排序范围是整个数组
• 排序之前，我们选择整个排序范围内的第一个元素作为基准，对排序范围内的元素进行快速排序
• 先从最右边向左看，依次将每一个元素与基准元素进行比较，如果发现比基准元素小，那么就与左边遍历位置上的元素（一开始是基准元素的位置)进行交换，此时保留右边当前遍历的位置。
• 交换后，转为从左往右开始遍历元素，如果发现比基准元素大，那么就与之前保留的右边遍历的位置上的元素进行交换，同样保留左边当前的位置，循环执行上一个步骤。
• 当左右遍历撞到一起时，本轮快速排序完成，最后在最中间的位置就是基准元素的位置了。
• 以基准位置为中心，划分左右两边，以同样的方式执行快速排序。

比如下面的数组:

首先我们选择第一个元素4作为基准元素，一开始左右指针位于两端:

此时从右往左开始看，直到遇到一个比4小的元素，首先是6，肯定不是，将指针往后移动:

此时继续让3和4进行比较，发现比4小，那么此时直接将3交换（其实直接覆盖过去就行了）到左边指针所指向的元素位置:

此时我们转为从左往右看，如果遇到比4大的元素，就交换到右边指针处，3肯定不是了，因为刚刚才缓过来，接着就是2:

2也没有4大，所以说继续往后看，此时7比4要大，那么继续交换:

接着，又开始从右往左看:

此时5是比4要大的，继续向前，发现1比4要小，所以说继续交换:

接着又转为从左往右看，此时两个指针撞到一起了，排序结束，最后两个指针所指向的位置就是给基准元素的位置了:

本轮快速排序结束后，左边不一定都是有序的，但是一定比基准元素小，右边一定比基准元素大。接着我们以基准为中心，分成两个部分再次进行快速排序:

这样，我们最后就可以使得整个数组有序了，当然快速排序还有其他的说法，有些是左右都找到了再交换，我们这里的是只要找到就丢过去。既然现在思路已经清楚了，我们就来尝试实现一下快速排序吧:

c++
void quickSort(int arr[], int start, int end) {
    if (start >= end) return;
    int left = start, right = end, pivot = arr[left];
    while (left < right) {
        while (left < right && arr[right] >= pivot) right--;
        arr[left] = arr[right];
        while (left < right && arr[left] <= pivot) left++;
        arr[right] = arr[left];
    }
    arr[left] = pivot;
    quickSort(arr, start, left - 1);
    quickSort(arr, left + 1, end);
}

int main() {
    int arr[] = {3, 5, 7, 2, 9, 0, 6, 1, 8, 4};
    quickSort(arr, 0, 9);
    for (auto x: arr) {
        printf("%d", x);
    }
    return 0;
}

这样，我们就实现了快速排序。我们还是来分析一下快速排序的稳定性，快速排序是只要遇到比基准小或者大的元素就直接交换，比如原数组就是2,2,1，此时第一个元素作为基准，首先右边1会被丢过来，变成:1,2,1，然后从左往右，因为只有遇到比基准2更大的元素才会换，所以说最后基准会被放到最后一个位置: 1,2,2，此时原本应该在前面的2就跑到后面去了，所以说快速排序算法，是一种不稳定的排序算法。