快速排序

快速排序算法是对冒泡排序算法的一种改进算法，在当前所有内部排序算法中，快速排序算法被认为是最好的排序算法之一。

快速排序的基本思想：通过一趟排序将待排序的序列分割为左右两个子序列，左边的子序列中所有的数据都比右边子序列中的数据小，然后对左右两个子序列继续进行排序，直至整个序列有序。

算法步骤

1. 从数列中选出一个元素，作为“基准”（pivot）；
2. 重新排序数列，所有比基准值小的元素放在基准值前，所有比基准值大的元素放在基准值的后面（相等的数可以放到任意一边）。在这个分区完成之后，该基准就处于数列的中间位置，这个称为分区操作；
3. 递归地把小于基准值元素的子数列和大于基准值的子数列排序；

动图演示

代码实现

template <typename T>
//严蔚敏《数据结构》标准分割函数
int paritition1(T A[], int low, int high) {
    T pivot = A[low];
    while (low < high) {
        // 将小于等于pivot的元素放在左边
        while (low < high && A[high] >= pivot) {
            high--;
        }
        A[low] = A[high];
        
        // 将大于等于pivot的元素放在右边
        while (low < high && A[low] <= pivot) {
            low++;
        }
        A[high] = A[low];
    }
    A[low] = pivot;
    return low;
}

template <typename T>
void quickSort(T arr[], int low, int high) {
    if (low < high) {
        int pivot_index = paritition1(arr, low, high);
        quickSort(arr, low, pivot_index-1);
        quickSort(arr, pivot_index+1, high);
    }
}

int main(int argc, const char * argv[]) {
    int arr[] = {9, 8, 7, 1, 3, 5, 2, 4, 6};
    quickSort(arr, 0, 8);
    return 0;
}