Posted by & filed under Uncategorized.

About caoyaming

Yaming Cao has written 16 post in this blog.

基本思想:

设要排序的数组是A[0]……A[N-1],首先任意选取一个数据(通常选用第一个元素)作为基准点,然后将所有比它小的数都放到它前面,所有比它大的数都放到它后面,这个过程称为一趟快速排序,然后采用分治策略,分别以同样的方式排序前面和后面的数据。值得注意的是,快速排序不是一种稳定的排序算法,也就是说,多个相同的值的相对位置也许会在算法结束时产生变动。
一趟快速排序的算法是:
1)设置两个变量i、j,排序开始的时候:i=0,j=N-1;
2)以第一个数组元素作为基准点。
3)从j开始向前搜索,即由后开始向前搜索(j–),找到第一个小于A[i](此时基准点)的值A[j],将值与A[j]交换;
4)从i开始向后搜索,即由前开始向后搜索(i++),找到第一个大于A[j](此时基准点)的A[i],将A[j]与A[i]交换;
5)重复第3步
6)重复第3、4、5步,直到i=j; (3,4步中,没找到符合条件的值,即3中A[j]不小于key,4中A[j]不大于key的时候改变j、i的值,使得j=j-1,i=i+1,直至找到为止。找到符合条件的值,进行交换的时候i, j指针位置不变。另外,i==j这一过程一定正好是i+或j-完成的时候,此时令循环结束),到此找到基准点的下标,作为分治下标。
7重复1-6步骤递归排序前半部分
8 重复1-6步骤递归排序后半部分

 

(java实现代码)

public static void quickSort(int a[], int start, int end) {
int i, j;
i = start;
j = end;
if ((a == null) || (a.length == 0))
return;

while (i < j) {//查找基准点下标
while (i < j && a[i] <= a[j])
// 以数组start下标的数据为key,右侧扫描
j–;
if (i < j) { // 右侧扫描,找出第一个比key小的,交换位置
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
while (i < j && a[i] < a[j])
// 左侧扫描(此时a[j]中存储着key值)
i++;
if (i < j) { // 找出第一个比key大的,交换位置
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
if (i – start > 1) { // 递归调用,把key前面的完成排序
quickSort(a, 0, i – 1);
}
if (end – j > 1) {
quickSort(a, j + 1, end); // 递归调用,把key后面的完成排序
}
}

Leave a Reply

  • (will not be published)