算法解析之快速排序

快速排序

算法思路：
1、找到一个关键值（一般是第一个或者中值），将小于关键值的序列放在左边，大于关键值的序列放在右边
2、将左右两个序列分别使用1过程（递推过程）
3、最终各个序列退化至单个元素，递归开始回归，整个序列有序

C++

//核心代码
template <typename T>
//给关键值找到合适的位置，并返回所在的位置
int partition(T arr[],int low,int high){
    //选取第一个值作为关键值（中轴值）
    int keyValue = arr[low];
    //j为最终的中轴索引值
    int j = low;
    for (int i = low + 1; i <= high; i++) {
        if(arr[i] < keyValue){
            swap(&arr[++j], &arr[i]);
        }
    }
    swap(&arr[low], &arr[j]);
    return j;
}

template <typename T>
void quickSort(T arr[],int low,int high){
    //回归条件
    if (high>low) {
        //1步骤
        int q = partition(arr, low,high);
        //2步骤
        quickSort(arr, low, q-1);
        quickSort(arr, q+1, high);
    }
}