写了2个形式的，原理差不多，都是找基数，递归到一个结束。但是细节和交换上有所不同。
相关code
package day20180728;
public class QuickSort{
public static void quickSort(int[] arr,int lt,int rt)
{
//只有一个元素的时候，递归出口
if(lt>=rt)
return;
int temp=arr[lt];
int st=lt,end=rt;
while(st<end)
{
while(st<end&&temp<=arr[end])
{
end--;
}
while(st<end&&temp>=arr[st])
{
st++;
}
if(st<end)
{
int tag=0;
tag=arr[end];
arr[end]=arr[st];
arr[st]=tag;
}
System.out.println("每一次左右轮换的结果为");
display(arr);
System.out.println();
System.out.println("#########");
}
arr[lt]=arr[st];
arr[st]=temp;
System.out.println("基数为："+st);
System.out.println("基数定位的结果为:");
System.out.println("------****-------");
display(arr);
System.out.println("++++++++++");
//递归基数的左边部分。
quickSort(arr,lt,st-1);
quickSort(arr,st+1,rt);
}
public static void display(int[] arr)
{
for(int elem:arr)
System.out.print(elem+" ");
}
public static void main(String[] args)
{
int[] arr= {11,6,8,22,33,78,65,0};
quickSort(arr,0,arr.length-1);
display(arr);
}
}
结果
每一次左右轮换的结果为
11 6 8 0 33 78 65 22
#########
每一次左右轮换的结果为
11 6 8 0 33 78 65 22
#########
基数为：3
基数定位的结果为:
------****-------
0 6 8 11 33 78 65 22 ++++++++++
每一次左右轮换的结果为
0 6 8 11 33 78 65 22
#########
基数为：0
基数定位的结果为:
------****-------
0 6 8 11 33 78 65 22 ++++++++++
每一次左右轮换的结果为
0 6 8 11 33 78 65 22
#########
基数为：1
基数定位的结果为:
------****-------
0 6 8 11 33 78 65 22 ++++++++++
每一次左右轮换的结果为
0 6 8 11 33 22 65 78
#########
每一次左右轮换的结果为
0 6 8 11 33 22 65 78
#########
基数为：5
基数定位的结果为:
------****-------
0 6 8 11 22 33 65 78 ++++++++++
每一次左右轮换的结果为
0 6 8 11 22 33 65 78
#########
基数为：6
基数定位的结果为:
------****-------
0 6 8 11 22 33 65 78 ++++++++++
0 6 8 11 22 33 65 78
另外一个版本
code如下
package day20180728;
public class qSort {
public static void ksort(int[] arr,int left,int right)
{
if(left>=right)
return ;
int tag=arr[left];
int i=left,j=right;
while(i<j)
{
while(i<j&&arr[i]<=arr[j])
{
j--;
}
if(i<j)
{
int temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
i++;
}
while(i<j&&arr[j]>=arr[i])
{
i++;
}
if(i<j)
{
int temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
j--;
}
}
System.out.println("基数i为："+i);
System.out.println("基数定位的结果为:");
System.out.println("------////-------");
display(arr);
System.out.println("/////////////");
//递归基数的左边部分。
ksort(arr,left,i-1);
ksort(arr,i+1,right);
}
public static void display(int[] arr)
{
for(int elem:arr)
System.out.print(elem+" ");
}
public static void main(String[] args) {
int[] arr= {11,66,8,22,33,78,65,0};
ksort(arr,0,arr.length-1);
display(arr);
}
}
结果
基数i为：2
基数定位的结果为:
------////-------
0 8 11 22 33 78 65 66 /////////////
基数i为：0
基数定位的结果为:
------////-------
0 8 11 22 33 78 65 66 /////////////
基数i为：3
基数定位的结果为:
------////-------
0 8 11 22 33 78 65 66 /////////////
基数i为：4
基数定位的结果为:
------////-------
0 8 11 22 33 78 65 66 /////////////
基数i为：7
基数定位的结果为:
------////-------
0 8 11 22 33 66 65 78 /////////////
基数i为：6
基数定位的结果为:
------////-------
0 8 11 22 33 65 66 78 /////////////
0 8 11 22 33 65 66 78
快速排序设计到了递归，有点不好理解，相关东西可以网上多查看一下
