快速排序

算法思想

每次排序先选出一个主元，然后将比主元小的数放到左边，比主元大的放右边然后再分别进入左边右边快排。

需要注意的是

  1. 主元的选取方法，一般是选择头中尾三个数中的中位数，而非固定的某个位置的数字
  2. 当数据规模剩下的比较小的时候采用其它的排序来完成剩下的排序，防止数据规模不大时候仍然各种递归导致处理得很慢
  3. 遇到相等的元素也要进行交换，防止得到的两个子集大小相差较大

算法实现

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
#include<stdlib.h>
#include<stdio.h>

void Quick_sort(int *Data,int N);
void swap(int *A,int *B);
void Qsort(int *Data, int Left, int Right);
void Insertion_sort(int *Data,int N);
int Median3(int *Data, int Left, int Right );

const int Cutoff = 100;

int main()
{
    int i,N,*Data;
    scanf("%d\n",&N);
    Data = (int*)malloc(N*sizeof(int));
    for(i = 0;i < N;i++)
        scanf("%d ",&Data[i]);
    Quick_sort(Data,N);
    for(i = 0;i < N-1; i++)
        printf("%d ",Data[i]);
    printf("%d\n",Data[N-1]);
}

void Quick_sort(int *Data,int N)
{
    Qsort( Data, 0, N-1 );
}
void swap(int *A,int *B)
{
    int tmp;
    tmp = *A;
    *A = *B;
    *B = tmp;
}
void Qsort(int *Data, int Left, int Right)
{
    int Pivot, i, j;
    if( Cutoff <= Right-Left ){
        Pivot = Median3( Data, Left, Right );
        i = Left; j = Right - 1;
        while(1)
        {
            while( Data[++i] < Pivot );
            while( Data[--j] > Pivot );
            if( i < j )
                swap( &Data[i], &Data[j] );
            else
                break;
        }
        swap( &Data[i], &Data[Right-1]);
        Qsort( Data, Left, i-1 );
        Qsort( Data, i+1, Right);
    }
    else
        Insertion_sort(Data+Left,Right-Left+1);
}
void Insertion_sort(int *Data,int N)
{
    int i,j,tmp;
    for(i = 1; i < N;i++)
    {
        tmp = Data[i];
        for(j = i;j > 0 && tmp < Data[j-1];j--)
            Data[j] = Data[j-1];
        Data[j] = tmp;
    }
}
int Median3( int *Data, int Left, int Right )
{
    int center = ( Left + Right ) / 2;
    if( Data[Left] > Data[center] )
        swap( &Data[Left], &Data[center] );
    if( Data[Left] > Data[Right] )
        swap( &Data[Left], &Data[Right] );
    if( Data[center] > Data[Right] )
        swap( &Data[center], &Data[Right] );
    swap( &Data[center], &Data[Right-1]);
    return Data[Right-1];
}

测试结果

快速排序不愧是实际使用中最快的排序算法，总体而言已经很快了

image-20210818173934940