算法描述

快速排序由冒泡排序演进而来，基于分治的算法思想。每次排序时选择一个元素作为“基准值”，经过一轮排序，通过某种划分算法将待排表分为左右两部分，其中左边的元素全都小于基准值，右边元素全都大于基准值。这样，基准值就被放在了它的最终位置。随后，再对左右两个子表递归进行上述操作，最终能够实现排序目的。

快速排序算法的性能取决于划分算法的优劣。以下将结合程序简单介绍快速排序算法的C++实现。

代码实现

#include <iostream>
#include <fstream>
using namespace std;
const int n = 8;        // 数组长度恒为8

/*** 划分算法，以传入的子数组首个元素为基准值，将子数组分为两部分。算法原理
为，从子数组的最后一个元素开始，将其与基准值比较;若其值大于基准值，则（维持
其位置不变）继续比较其左侧元素（high--)；若其值小于基准值，则将其复制到子数
组最左侧（并使low++）。重复上述比较直到两侧下标相遇（low == high),此时low
所指位置刚好是基准值在顺序排序中的最终位置，并将此位置下标返回。***/
// arr[]: 待排数组
// low, high: 用于界定子数组的下标
int partition(int arr[], int low, int high){
    int pivot = arr[low];   // pivot为基准值
    while(low < high){
        while(arr[high] >= pivot && low < high) --high;
        arr[low] = arr[high];
        while(arr[low] <= pivot && low < high) ++low;
        arr[high] = arr[low];
    }
    arr[low] = pivot;
    return low;
}
/*** 快排函数 ***/
// arr[]: 待排原数组
// low, high: 定界下标
void quick_sort(int arr[], int low, int high){
    if(low > high) return;
    int mid = partition(arr, low, high); // 接收来自划分算法的返回值
    quick_sort(arr, low, mid-1); // 分治
    quick_sort(arr, mid+1, high); // 分治
}

int main(){
    fstream inFile;
    inFile.open("in.txt");
    int *arr = new int[n];
    for(int i=0; i<n; ++i)
        inFile >> arr[i];

    quick_sort(arr, 0, n-1);
    for(int i=0; i<n; ++i)
        cout << arr[i] << " ";

    delete[] arr;
    inFile.close();
    return 0;
}

算法分析

（1）时间复杂度为O(nlogn)，空间复杂度为O(n)；快速排序是所有内部排序算法中平均性能最好的排序算法。

（2）快速排序算法不是一个稳定的排序方法。