快速排序是在冒泡排序的基础上进行的改装,它的原理是经过一趟排序将数据分割成两部分,左边的数据小于右边的数据,然后分别对这两部分数据用同样的原理进行排序,整个排序过程是用递归实现的,下面来看一个例子
package com.lamp.sort;
public class QuickSort{
public static void main(String[] args) {
int[] data = {5,3,9,2,6,1};
sort(data,0,data.length);
for (int i = 0; i < data.length; i++) {
System.out.println(data[i]);
}
}
/* 首先我要找到一个位置的数使得其左边的数字比它要小,右边的数字比它要大
开始的时候数组为5,3,9,2,6,1
首先从左端下标为++i开始扫描发现3小于5满足条件继续,发现下一个9大于5而此时i的下标值为2
不满足条件推出左端扫描的while循环,开始从最右端开始扫描,发现最右端第一个数字就小于5,此时
j的值为5,而i此时是小于j的,交换两位置数据,即一轮循环后的数据为
5,3,1,2,6,9
接着从左端开始继续扫描,当扫描到大于5的值的时候,i的值变为4即6所处位置的下标,当从右端
开始扫描时,扫描到小于5的数字时,j的值变为3,而此时i的值大于j的值不满足条件推出最外的
while循环,此时数组的数据为
5,3,1,2,6,9
然后将第一个数和j处下标的数进行互换,数组变为
2,3,1,5,6,9
这样就达到了预期的目标,即下标为3的数据大于其左边的数据且小于其右边的数据
然后以5为分割点对两边的数据用同样的原理进行排序
*/
private static void sort(int[] data, int left, int right) {
int i = left;
int j = right;
int middle = data[left]; //第一次调用时候我选取要排序的数组的第一个数作为关键数据
while(true){
while(++i<right-1 && data[i]<middle);
while(--j>left && data[j]>middle);
if(i >= j){
break;
}
swap(data,i,j);
}
data[left] = data[j];
data[j] = middle;
if(left < j){
sort(data,left,j);
}
if(i < right){
sort(data,i,right);
}
}
private static void swap(int[] data, int i, int j) {
int temp = data[i];
data[i] = data[j];
data[j] = temp;
}
}
分享到:
评论