快速排序是由东尼·霍尔锁发明的一种排序算法。这种方法快速排序通常明显比其他的算法更快,因为它的内部循环可以在大部分的架构上很有效率低被实现出来,看下图排序的思想:
1、从数组中取出一个数作为基数 2、分区:将比这个数大或者等于的数放到它的右边,小于它的数放到左边。 3、再对左右区间 重复第二步,直到各区间只有一个数。 下面我们举例说明下利用java语言如何实现快速排序的:
题目:创建一个随机的列表集合,共取30个数,取值范围在1-99之间,利用快速排序的方法排序并打印。 [AppleScript] 纯文本查看 复制代码 [/align][align=left]import java.util.ArrayList;[/align]import java.util.Random;
/**
* @Description: 创建一个随机的列表集合,共取30个数,取值范围在1-100之间,利用快速排序的方法排序并打印。
* @Author: lihui
* @CreateDate: 2018/10/9 10:14
* @Version: 1.0
*/
public class QuickSortDemo {
public static void main(String[] args) {
ArrayList<Integer> list = new ArrayList<>();
creationArray(list);
showArray("创建数组:",list);
quickArray(list,0,list.size()-1);
showArray("快排后",list);
}
//创建一个集合,随机获取30个100-2100之间的数
public static void creationArray(ArrayList<Integer> list){
Random random = new Random();
for (int i = 0; i < 30; i++) {
list.add(random.nextInt(100)+1);
}
}
//显示遍历集合并打印出来
public static void showArray(String str,ArrayList<Integer> list){
System.out.print(str+"arr=[");
for (int i = 0; i < list.size(); i++) {
System.out.print(list.get(i)+" ");
}
System.out.println("]");
}
//快速排序的方法
public static void quickArray(ArrayList<Integer> list,int low,int high){
int l = low;
int h =high;
int key = list.get(low);//以最左的为基准值
//遍历下标l不能大于下标h,否则跳出循环
while(l<h){
//若是l一直小于h,并且下标h对应集合的值一直大于h或等于取的基准值key,这保持在基准值key的右边,否则换到左边
while(l<h && list.get(h)>=key) h--;
//调到这里若是l还是小于h,说明有一个h对应的值小于基准值key,所以换位置换位置
if(l < h){
int temp = list.get(l);
list.set(l,list.get(h));
list.set(h,temp);
l++;
}
//若是l一直小于h,并且下标h对应集合的值一直小于或等于h取的基准值key,这保持在基准值key的左边,否则换到右边
while(l<h && list.get(l)<key) l++;
//调到这里若是l还是小于h,说明有一个l对应的值大于基准值key,所以换位置换位置
if(l < h){
int temp = list.get(l);
list.set(l,list.get(h));
list.set(h,temp);
h--;
}
//若是l>low,要继续执行上面的步骤,需要改变现有的范围
if(l>low) quickArray(list,low,l-1);
//若是h<high,要继续执行上面的步骤,需要改变现有的范围
if(h<high) quickArray(list,l+1,high);
}
}
}
|