快速排序:
基本思想:
1、先从数列中取出一个数作为基数。
2、分区,将比此基数大的数放到它右边,小的数放到它左边。
3、再对左右两块区间进行第二步,直到各中间只有一个数。(分治策略)
public void quick_sort1(int s[],int l,int r){
if (l < r)
{
int i = AdjustArray(s, l, r);//对基数排序,返回排序后的基数位置
quick_sort1(s, l, i - 1); //划分基数两边区域继续排序,分治
quick_sort1(s, i + 1, r);
}
}
public int AdjustArray(int a[],int i,int j){//取a[i]做为基数排序,返回排好序之后基数的位置
int k=a[i];
while(i<j){
while(i<j){//右向左寻找比基数小的数,进行交换
if(k<a[j]){
j--;
}else{
a[i++]=a[j];
a[j]=k;
break;
}
}
while(i<j){ //左向右寻找比基数大的数,进行交换
if(k>a[i]){
i++;
}else{
a[j--]=a[i];
a[i]=k;
break;
}
}
}
return i;
}
上述代码将基数排序和分治 分为两个函数,较为繁琐,简化后如下:
public void quick_sort(int a[],int l,int r){
if (l < r) {
int i=l,j=r,k=a[i];
while(i<j){ //对区域内基数进行排序,选区域内第一个数为基数
while(i<j){
if(k<a[j]){
j--;
}else{
a[i++]=a[j];
a[j]=k;
break;
}
}
while(i<j){
if(k>a[i]){
i++;
}else{
a[j--]=a[i];
a[i]=k;
break;
}
}
}
quick_sort(a, l, i - 1); //分治,对基数两边区域继续排序
quick_sort(a, i + 1, r);
}
}
//上述代码对基数排序的部分,即指定区域内比基数小的放在左边,比基数大的放在右边,此部分较为繁琐,简化如下:
int i = l, j = r, x = s[l];
while (i < j) {
while(i < j && s[j] >= x) // 从右向左找第一个小于x的数
j--;
if(i < j)
s[i++] = s[j];
while(i < j && s[i] < x) // 从左向右找第一个大于等于x的数
i++;
if(i < j)
s[j--] = s[i];
}
s[i] = x;