# 排序算法学习之快速排序算法
##1. 快速排序算法的原理
快速排序算法的原理是选取一个值作为标志，将一个数组分为2部分，左边部分的数全部都比标志值小，右边部分都比标志值大，然后分别对左边数组和又边数组进行递归，直到排序完成。
下面是进行一次数组处理的过程：
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
94
95
96
97
98
99
100
101
102对以下的数组进行排序：
[key]
i j
33 17 54 15 23 21 37 20 32 24
将数组的第一个数设置为标志
[key]
[第一次处理]：比较str[i]与str[j］（ 如果str[i]<str[j],就执行'j--'，然后重复［第一次处理］），发现33>24，即str[i]>str[j]，所以将str[i],str[j]互换位置，i 向前进一位，得到如下的数组
i-->i j
24 17 54 15 23 21 37 20 32 33
i j
24 17 54 15 23 21 37 20 32 33
[key]
[第二次处理]：比较str[i]与str[j]，17>33,即str[i]<str[j],所以执行'i++'操作,i右移一位。
i-->i j
24 17 54 15 23 21 37 20 32 33
i j
24 17 54 15 23 21 37 20 32 33
[key]
[第三次处理]：比较str[i]与str[j]，54>33,即str[i]>str[j],所以将str[i],str[j]互换位置，然后执行'j--'操作
i j
24 17 54 15 23 21 37 20 32 33
i j<--j
24 17 33 15 23 21 37 20 32 54
i j
24 17 33 15 23 21 37 20 32 54
[key]
[第四次处理]：比较str[i]与str[j]，33>32,即str[i]>str[j],所以将str[i],str[j]互换位置，然后执行'i++'操作
i j
24 17 33 15 23 21 37 20 32 54
i-->i j
24 17 32 15 23 21 37 20 33 54
i j
24 17 32 15 23 21 37 20 33 54
[key]
[第五次处理]：比较str[i]与str[j]，15<33,即str[i]<str[j],所以执行'i++'操作,i右移一位。
i j
24 17 33 15 23 21 37 20 32 54
i-->i j
24 17 32 15 23 21 37 20 33 54
i j
24 17 32 15 23 21 37 20 33 54
[第六次处理]
。。。。。。
[key]
[第八次处理]:比较str[i]与str[j]，37>33,即str[i]>str[j],所以将str[i],str[j]互换位置，然后执行'j--'操作
i j
24 17 33 15 23 21 37 20 33 54
i j<--j
24 17 32 15 23 21 33 20 37 54
i j
24 17 32 15 23 21 33 20 37 54
[key]
[第九次处理]:比较str[i]与str[j]，54>33,即str[i]>str[j],所以将str[i],str[j]互换位置，然后执行'i++'操作
i j
24 17 33 15 23 21 33 20 37 54
i--->j
24 17 32 15 23 21 20 33 37 54
ij
24 17 32 15 23 21 20 33 37 54
发现i,j已经相等，此次循环处理结束。
通过上面的过程，成功的将所有比33大的数排在了它的后面，把比33小的数排在了33的前面，得到了第一次处理的结果。
然后再通过对左边 2 边分别进行递归处理，最终得到排序结果。
##2. 下面是完整的 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
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
#include<stdio.h>
//快速排序函数声明 str为数组地址，left，right分别为排序数组的的左边界和右边界
void sqrtNum(long *str,int left,int right);
//传进来的a，b是2个指针，并将指针所指向地址中储存的数据进行交换
void exchange(long* a,long* b){
long temp;
temp=*a;
*a=*b;
*b=temp;
}
//主函数
int main(){
long str[10];
for(int i=0;i<10;i++){
scanf("%ld",&str[i]);
}
sqrtNum(str,0,9);
for(int i=0;i<10;i++){
printf(" %ld",str[i]);
}
printf("\n");
return 0;
}
//排序函数的具体内容
void sqrtNum(long *str,int left,int right){
//long key=str[left];
int kn=left;
int m=left;
int n=right;
while(m<n){
//当从右读的标志n大于从左开始读的标志m时，一直循环，判断右边读的数组中的数是否比标志[key]大，如果大，就一直执行n--直到str[m]的值大于等于str[n]：执行第二个if语句中的内容，然后break；跳出内循环
while(m<n){
if(str[m]<str[n]){
n--;
}
if(str[m]>=str[n]){
exchange(&str[n],&str[m]);
m++;
break;
}
}
//当从右读的标志n大于从左开始读的标志m时，一直循环，判断左边读的数组中的数是否比标志[key]大，如果大，就一直执行m++直到str[m]的值大于等于str[n]：执行第二个if语句中的内容，然后break；跳出内循环
while(m<n){
if(str[m]<str[n]){
m++;
}
if(str[m]>=str[n]){
exchange(&str[n],&str[m]);
n--;
break;
}
}
}
kn=m;
if(left<right){
sqrtNum(str, left,kn-1);
sqrtNum(str, kn+1,right);
}
}
