快速排序
转载http://158067568.iteye.com/blog/914049
快排是分治法的一个应用,快排主要是通过一个设定枢轴,然后以这个枢轴为标杆,将待排序列按大小分成比枢轴大的,和比枢轴小的两部分。然后在对划分完的子序列进行快排,知道子序列中元素的个数为 1 位置。
快速排序实现
快排是程序员必须掌握的,举一个例子来解释,如下图:
<!--[endif]-->
首先选定枢轴,一般设置 low 所对应的元素位置为枢轴,如图选定的枢轴为 26 。
在高位指针始终不小于低位指针的前提下:
高位指针开始判断其是否比枢轴值大,如果符合,高位指针减 1 ,继续寻找,直到找到不符合的情况,然后把该值赋给此时低位所在位置。
低位指针开始判断其是否比枢轴值小,如果符合,低位指针加 1 ,继续寻找,直到找到不符合情况,然后将该值赋给此时高位指针所指位置。
如此反复,知道低位与高位指针重合,此时,在讲当前的枢轴值赋给低位指针所指的值。这样就完成了一次排序。
此时枢轴值就到了其最终位置上,然后继续对以枢轴为轴的两部分进行排序。
JAVA 实现快速排序
package
cn.edu.heut.zcl;
public
class
QuickSort {
/**
* 快速排序,对整数型数组o进行
* @param o
* @param low
* @param hight
*/
public
static
void
quiteSort(
int
[] o ,
int
low ,
int
hight ){
if
(low < hight){
int
povitePosition = adjust(o,low,hight);
quiteSort( o , low , povitePosition - 1
);
quiteSort( o , povitePosition + 1
, hight );
}
}
/**
* 进行调整
* @param o
* @param low
* @param hight
* @return
*/
private
static
int
adjust(
int
[] o ,
int
low ,
int
hight ){
//选定枢轴为low所对应的值
int
pivote = o[low];
while
(low < hight){
while
(hight > low && compare( pivote , o[hight] ) <=
0
){
// 高位找到比povite大,则符合要求,继续寻找
hight -- ;
}
o[low] = o[hight] ;
while
(low < hight && compare( pivote , o[low] ) >=
0
){
//低位开始找到比povite小,符合要求,继续寻找
low ++ ;
}
o[hight] = o[low];
}
o[low] = pivote ;
return
low;
}
/**
*
* @param num1 减数
* @param num2 被减数
* @return
*/
private
static
int
compare(
int
num1,
int
num2) {
return
num1 - num2 ;
}
/**
* @param args
*/
public
static
void
main(String[] args) {
int
[] i = {
26
,
53
,
48
,
15
,
13
,
46
,
32
,
15
};
quiteSort(i, 0
, i.length-
1
);
for
(
int
ii:i){
System.out.print(ii+" "
);
}
}
}