排序5-快速排序

快速排序(正序)

利用分而治之的思想+挖坑填数排序, 选择一个基准数,

将小于基准数的元素全部放在基准数左边, 大于基准数的元素全部放在基准数右侧.

再对剩下的部分进行快速排序

快速排序c++实现(正序)

//快速排序(正序)
void quickSort(int arr[], int start, int end){
    int i = start;
    int j = end;
    //基准数
    int tmp = arr[start];
    if(i<j){
        while(i<j){
            //下标j不断左移, 从右到左寻找第一个小于tmp的数
            while(i<j && arr[j]>=tmp){
                j--;
            }
            //填坑, 将arr[j]的元素填入arr[i]位置
            if(i<j){
                arr[i] = arr[j];
                i++;
            }
            //下标i不断右移, 从左到右寻找第一个大于tmp的数 
            while(i<j && arr[i]<=tmp){
                i++;
            }
            //填坑, 将arr[i]的元素填入arr[j]位置
            if(i<j){
                arr[j] = arr[i];
                j--;
            }
        }

        //把基准数放到i&j重合的位置
        arr[i] = tmp;
        //对左半部分进行快排
        quickSort(arr,start,i-1);
        //右半快排
        quickSort(arr,i+1,end);

    }
}