关于递归思想于快速排序的一些思考（C++）

int partition_array(int *arr ,int l,int r)
// 编程实现arr[l, r]分区：选定一个基准，左边比基准小，右边比基准大
// 返回基准所处位置
{
    int pivotkey;
    int static copykey;
    int m;
    m=(r+l)/2;
    if(arr[l]>arr[r])
        swap(arr, l ,r);
    if(arr[m]>arr[r])
        swap(arr, m, r);
    if(arr[l]<arr[m])
        swap(arr, l ,m);//进行三数取中
    copykey=pivotkey=arr[l];
    while(r>l)
    {
        while(r>l&&arr[r]>=pivotkey)
            r--;
        arr[l]=arr[r];
        while(r>l&&arr[l]<=pivotkey)
            l++;
        arr[r]=arr[l];
    }
    arr[l]=copykey;
    return l;

}
int* quick_sort(int *arr, int l, int r)
//  基于partition_array函数编程实现快速排序：自上而下的递归方法
//  函数参数：有序数组arr 初始l=0，r=n-1
//  函数返回值：返回从小到大排序后的数组
{
    int pivot;
    if(l<r)
    {
        pivot=partition_array(arr,l,r);

        quick_sort(arr ,l, pivot-1);
        quick_sort(arr,pivot+1,r);
    }
    return  arr;


}

• 一些想法
  • 快速排序，其实每次函数都是做同样意义的事，给出他的左右边界，利用双指引排好序，返回他的pivot。这里的pivot，也正是不断迫近终止条件的关键因素。
  • 无论是最大的那个数组，还是最小的那个数组。他们都是有着同一套行为指导。就像是镜中镜，虽然大小有区别，但是行为方式没有变化。
  • 首先他将处理左数组，通过递归，那面最小镜子面前的人，将数组处理好，带着数据去到上一级镜子那人，然后一样地根据上一级所限制的模式中，将数据再一次加工，然后带到上一级。左数组处理完了之后就是右数组
  • 其实排序的方式就是不断地选取枢纽pivot，将大于pivot的放在数组的右边，而小于pivot的放在数组的左边，然后两根索引，数组上不断地移动，最后有一个会到中间，而中间的这个位置就是留给pivotkey的，然后，返回pivot 方便不断地细分数组
  • 这里其实可以也可通过不断地交换low和high的所指的值来达到大右小左，这样就不用了暂存那个copykey

最后

以上就是瘦瘦皮卡丘为你收集整理的关于递归思想于快速排序的一些思考（C++）的全部内容，希望文章能够帮你解决关于递归思想于快速排序的一些思考（C++）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。