快速排序介绍
快速排序是目前在实践中非常高效的一种排序算法，它不是稳定的排序算法，平均时间复杂度为O(nlogn)，最差情况下复杂度为O(n^2)。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
傻瓜版
下面这个代码是我之前看过，觉得是很容易理解的版本：
void quick_sort(int arr[], int left, int right)
{
if (left < right){
int i = left, j = right, target = arr[left]; //以第一个位置作为划分依据
while (i < j){
while (i < j && arr[j] > target) //从右开始找到第一个比target小的
j--;
if (i < j)
arr[i++] = arr[j]; //把右边的一个数放到左边
while (i < j && arr[i] < target) //从左开始找到一个比target大的数
i++;
if (i < j)
arr[j] = arr[i]; //把左边的一个数放到刚才右边数的位置
}
arr[i] = target; //把target放到中间位置
quick_sort(arr, left, i - 1);
quick_sort(arr, i + 1, right);
}
}
搬运版
#include <iostream>
#include <vector>
#include <stdlib.h>
#include <assert.h>
using namespace std;
//[lo, hi) : 构造轴点，轴点前的所有元素都不大于轴点值，反之都不小于轴点值
int partition(vector<int>&nums, int lo, int hi){
assert(hi - lo >= 2); //partition给定的区间必须至少包含两个元素
int p = lo + rand() % (hi - lo);
swap(nums[lo], nums[p]); //首先把轴点放到lo位置
int mi = lo;
for(int i = lo + 1; i < hi; ++i){ //遍历，这里维护一个指针mi，使得mi所指及左侧均为小于轴点值
if(nums[i] < nums[lo])
swap(nums[++mi], nums[i]);
}
swap(nums[lo], nums[mi]); //将轴点值放到mi现在的位置，即分界点
return mi;
}
void quicksort(vector<int>&nums, int lo, int hi){
//将nums[lo, hi)内的所有元素进行排序
if(hi - lo < 2) return;
int mi = partition(nums, lo, hi);
quicksort(nums, lo, mi);
quicksort(nums, mi + 1, hi);
return;
}
int main(){
srand(time(NULL));
vector<int> tst;
for(int i = 0; i < 1000; i++){
tst.push_back(rand() % 1000);
}
for(auto x : tst) cout << x << " ";
cout << endl;
quicksort(tst, 0, tst.size());
for(auto x : tst) cout << x << " ";
cout << endl;
return 0;
}
