一种递归实现的快速排序精讲

简介：

快速排序是个“综合素质”较好的排序，比如javaSE中的Arrays.sort()实现原理，也是用的是快速排序思想。下面就看看一种快速排序的递归实现方式

要点：

1，分治思想，把问题划分成可以与本问题处理方式相同的若干子问题，使用递归来解决。

   如排序问题，可以

    （1）把原数组A[p,q]（原问题）划分成三个部分 ：较小部分A[p,m-1]  中间元素x=A[m]  较大部分A[m+1,q] 

          这样把部分当做一个整体看待是有序的A[p,m-1] <  A[m]  <  A[m+1,q]

    （2）同理，无论是较小部分还是较大部分都可以继续按（1）操作继续划分得更细，直到每个部分的元素

          被划分得只有单个元素，原数组之间每个元素就有序了

特征：

1，快速排序是原址排序，子问题解决的时候，不需要整体再次合并排序结果

2，递归调用在非常的数据的时候可能会发生栈溢出（递归深度太大）

难点：

   如何划分成相对有序的三个部分？

      思路：

         （1）在原数组的某个好识别的位置取出一个数做中间元素x（部分2）。（一般取数组末元素，如x=A[q]）

         （2）采取一个位置变量i来左划分界线，保证i上和i的左边都是小部分元素（部分1）。

            （i的初始位置应当在问题范围的前一个位置，因为此时还没开始划分）

         （3）除了x元素，循环取出原数组中的每个元素A[j]与x做比较

             遇到不大于中间元素x要收集到界线上：

                 原界线i右移一个，此时i指向的元素是不确定性质的元素，

                 不确定元素和已经遇到的确定的小部分元素A[j]交换位置。（不确定换确定）

             遇到大于中间元素的，界线i不动，j继续向右扫描（i和j之间的定是大部分元素,部分3）

         （4）让中间元素交换到真正位置。一遍循环后，可以分出 小部分 和 大部分，

              此时只要在界线的右一个（即大部分中的某个元素）与中间元素交换即可让划分的三个部分满足排序关系。

图片描述：

代码描述：

void quicklySort(int *arr , int start , int last){

    int mid;

    if(start<last){

        mid = partition(arr, start, last);//划分子问题

        quicklySort(arr, start , mid-1);//解决左边部分

        quicklySort(arr, mid+1, last);//解决右边部分

    }

}

int partition(int *arr, int start, int last){

    int x = arr[last];//取本段数组最后一个元素，稍后使其成为划分好的中间元素

    int i=0,j=0;

    i=start-1;//使用i来控制两个部分的分界，初始值在子问题范围的前一个

    for(j=start;j<= last-1; j++){

        if(arr[j]<= x){//如果j走过的值是属于较小部分

           ++i;//较小部分分界线多收集一个空间

           swap(arr[i],arr[j]);//把属于较小部分的值交换到这个空间（原址排序）

        }

        //如果是较大部分，让j继续向后滑行

    }

    swap(arr[i+1],arr[last]);//把选择参照的值交换到小部分和大部分之间

    return i+1;//返回划分好的中间位置

}