排序----快速排序 - 黑马程序员技术交流社区

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

}