快速排序顾名思义，就是很快喽。
算法思想：
1、先找一个基准
2、把小于它的数放左边，打大于它的放右边
3、然后再把它左边和右边的数也用1、2步骤实现
4、递归调用该方法直到有序。
可能没有说清楚，代码如下。
|
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
|
include <stdio.h>
#include <stdlib.h>
int
sortArr[10] = {0};
int
quickSort(
int
left,
int
right)
{
int
i = left;
int
j = right;
int
temp = sortArr[i];
//用来存放基数
if
( left > right )
{
return
-1;
}
while
( i != j )
{
//应该从右边先开始，因为这样才能保持i（left）用于小于等于j（right）。
//如果先从左边开始，就会导致不能正常排序，你可以调试看看。
while
( sortArr[j] <= temp && i < j )
//找大于基准数的数
{
j--;
}
while
( sortArr[i] >= temp && i < j )
//找小于基准数的数
{
i++;
}
if
( i < j )
//判断下标并交换两个数
{
int
tem = sortArr[i];
sortArr[i] = sortArr[j];
sortArr[j] = tem;
}
}
//当两个下标相等时，交换基数和i下标的数。目的是将小于基准数的数
//全部放到基准数的左边，大于基准数的数放到基准数的右边
sortArr[left] = sortArr[i];
sortArr[i] = temp;
//递归调用quickSort函数。
quickSort(left,i-1);
//递归处理基数左边的数
quickSort(i+1,right);
//递归处理基数右边的数
return
0;
}
int
main()
{
int
index = 0;
printf
(
"请输入要排序的10个数："
);
for
( ;index < 10; index++ )
{
scanf
(
"%d"
,&sortArr[index]);
}
quickSort(0,9);
for
( index = 0;index < 10;index++ )
{
printf
(
"%d "
,sortArr[index]);
}
printf
(
"\n"
);
system
(
"pause"
);
return
0;
}
|
时间复杂度是多少了？
O（N*logN）。
本文转自 8yi少女的夢 51CTO博客，原文链接：http://blog.51cto.com/zhaoxiaohu/1758501，如需转载请自行联系原作者
