A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

© 疯狂的神龟 初级黑马   /  2018-10-9 12:38  /  607 人查看  /  0 人回复  /   0 人收藏 转载请遵从CC协议 禁止商业使用本文

快速排序是由东尼·霍尔锁发明的一种排序算法。这种方法快速排序通常明显比其他的算法更快,因为它的内部循环可以在大部分的架构上很有效率低被实现出来,看下图排序的思想:

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);
        }
    }
}

0 个回复

您需要登录后才可以回帖 登录 | 加入黑马