数据结构与算法刷题笔记10——排序算法(快排)

快速排序

算法思想

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

需要注意的是

  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