黑马程序员技术交流社区

标题: 排序----快速排序 [打印本页]

作者: 疯狂的神龟    时间: 2018-10-9 12:00
标题: 排序----快速排序
         快速排序是由东尼·霍尔锁发明的一种排序算法。这种方法快速排序通常明显比其他的算法更快,因为它的内部循环可以在大部分的架构上很有效率低被实现出来,看下图排序的思想:

1、从数组中取出一个数作为基数

2、分区:将比这个数大或者等于的数放到它的右边,小于它的数放到左边。

3、再对左右区间 重复第二步,直到各区间只有一个数。

下面我们举例说明下利用java语言如何实现快速排序的:
          题目:创建一个随机的列表集合,共取30个数,取值范围在100-2100之间,利用快速排序的方法排序并打印。


[AppleScript] 纯文本查看 复制代码

import java.util.ArrayList;

import java.util.Random;

/**
* @Description: 创建一个随机的列表集合,共取30个数,取值范围在100-2100之间,利用快速排序的方法排序并打印。
* @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);
        }
    }
}
      







欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2