快速排序基于分治法的思想

对于快速排序的自我小结：
关键在于伪代码的理解，这同样是采用了分治法的思想


#include <iostream>

using namespace std;

//找到基准元素下标的函数
int FindPos(int arr[],int low,int high)
{
    //找到基准元素的值
    int val = arr[low];
    while(low<high)
    {

        //对于右边的值若是大于基准元素的值，
        //那么，右边元素位置下标向左移动一位
        // ,然后以右边第二个元素和基准元素比较
        while(low<high&&arr[high]>=val)
            //下标减减就代笔位置向左边移动一位
            --high;
        //当右边的元素小于基准元素的时候，将较小的值赋给基准元素位置的变量
        arr[low]=arr[high];

        //如果交换下标之后，钙元素的的值小于基准元素
        //那么较小元素的下标向右移动一位
        //总之基准元素的下标不变
        while(low<high&&arr[low]<=val)

            ++low;


        arr[low]=arr[high];

    }
    arr[low]=val;

    //这个地方low或者high都可以，因为上面的while循环结束后，low和hign是相等的
    //返回的只是一个小标，也就是第一次快排完成后得到的基准元素下标位置
    return low;


}

void quickSort(int arr[],int low,int high)
{
    //pos 用于记录排序序列的第一个元素的位置
    int pos ;

    //只有当下限小于上限的时候才进行排序,
    //用于记录排序序列的开始元素和结束元素
    if(low<high)
    {
        //找打第一次劈两半之后，第一个元素的下标
        //FindPos(a,low,high)这个函数的主要作用在于找打
        //第一次排序后第一次基准元素的下标
        pos=FindPos(arr,low,high);

        //对最左边的一半元素采用同样的方法进行排序
        quickSort(arr,low,pos-1);
        //对最右边的一半元素采用劈两半的方式进行排序
        quickSort(arr,pos+1,high);
    }



}



int main()
{

    int a[6]= {2,1,0,5,4,3};


    for(int  i=0; i<6; i++)
        cout<<a[i]<<"   ";
    cout<<endl;


    quickSort(a, 0,5);
    cout<<"After sort the result is\n";
    for(int  i=0; i<6; i++)
        cout<<a[i]<<"   ";



    return 0;
}
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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93