快速排序（基准是中位数）_快速排序以中间数作为基准值

简介：

　　快排相比冒泡等相对较快，是因为其是跳跃式交换（快，要根据数据量等）

下面算法介绍：

　　①根据数据量，若大于cutoff，则用快排，反之用插入排序

　　②先找基准（这里采用中位数），并将基准放在Right-1的位置（Right放比较三个数最大那个）

　　③从左边向右开始找，若找到比基数大的（则左边指针停下）；然后从右边开始向左找，若找到比基数小的（则右边指针停下）；

　　④交换左右指针所指的数

　　⑤循环，③~⑤，直至基本有序，跳出

　　⑥将Right-1的数（即基数） 与 中间交换

　　⑦分左右两边子递归，重复①~⑥

##include<cstdio>
##include<algorithm>
using namespace std;
##define MAXN 110

void Swap(int *a, int *b){
    int temp;
    temp = *b;
    *b = *a;
    *a = temp;
}
//插入排序
void insertion_sort(int *a, int n) {
    int i, j;
    int temp;
    for (i = 1;i < n;i++) {
        temp = a[i];
        for (j = i; j > 0 && a[j - 1] > temp; j--)
                a[j] = a[j - 1];
        a[j] = temp;
    }
}


//取三个位的中位数
int Median3(int *A, int left, int right){
    int center = (left + right) / 2;
    if(A[left] > A[center])
        Swap(&A[left], &A[center]);
    if(A[left] > A[right])
        Swap(&A[left], &A[right]);
    if(A[center] > A[right])
        Swap(&A[center],&A[right]);

    Swap(&A[center], &A[right - 1]);     //将基准Pivot藏到右边

    return A[right - 1];                
}

void Qsort(int *A, int left, int right){
    int pivot, cutoff, low, high;
    cutoff = 3;                      //定义cutoff, 当数据量小于cutoff时候，用插入排序

    if(cutoff <= right - left){     //如果序列元素充分多，进入快排
        pivot = Median3(A, left, right);
        low = left;
        high = right - 1;
        while(1){
            while(A[++low] < pivot);
            while(A[--high] > pivot);
            if(low < high)
                Swap(&A[low], &A[high]);
            else break;
        }
        Swap(&A[low], &A[right - 1]);
        Qsort(A, left, low - 1);
        Qsort(A, low + 1, right );
    }
    else
        insertion_sort(A + left, right - left + 1);
}

int main(void){
//    int A[MAXN];
//    scanf("%d", &N);
//    for(int i = 0; i < N; ++i)
//        scanf("%d", &A[i]);
    int A[] = {8, 5, 2, 3, 6, 9, 7, 4, 1, 0, 23};
    int N = 11;
    for(int i = 0 ; i < N; ++i)
        printf("%d ", A[i]);
    printf("\n");
    Qsort(A, 0, N - 1);
    for(int i = 0 ; i < N; ++i)
        printf("%d ", 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