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

184 阅读 0 评论 122 点赞

我是靠谱客的博主瘦瘦皮卡丘，这篇文章主要介绍关于递归思想于快速排序的一些思考（C++），现在分享给大家，希望可以做个参考。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
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