快速排序

package com.jzyt.threadpool;

/**
 * @CLASS 快速排序填坑法
 *  递归
 */
public class QuickSortTest {

    public static void quickSort(int[] arr,int left,int right){
     if(left < right){
         int index = getIndex(arr,left,right);
         quickSort(arr,0,index-1);
         quickSort(arr,index+1,right);
     }
    }

    /**
     * 获取基准数
     * @param arr 数组
     * @param left 以基准数分割后数组的起始索引
     * @param right 以基准数分割胡的数组的最后一个索引
     * @return 基准数
     */
    private static int getIndex(int[] arr, int left, int right) {
        int i = left;
        int j = right;

        //定义一个基准数
       int base = arr[left];
       while (i<j){

           //当队尾元素大于等于基准数时，队尾元素指针向前移
           while (i<j && arr[j]>=base){
               j--;
           }
           //如果队尾元素比基准数小，就把队尾元素赋值给队首元素，同时队首元素指针继续向后移动
           if(i<j){
               arr[i] = arr[j];
               i++;
           }
           //当对首元素小于基准数时，对首元素指针向后移
           while (i<j && arr[i]<base){
               i++;
           }
           //如果队首元素大于或者基准数，就把队首元素赋值给队尾元素，同时队尾元素指针继续向前移动
           if(i<j){
               arr[j] = arr[i];
               j--;
           }
       }
       //把第一个坑给补齐
       arr[i] = base;
       //返回基准数的位置索引
        return i;
    }

    /**
     * main方法
     * @param args
     */
    public static void main(String[] args) {
        int[] arr = {3,5,4,2,1,8,7,9,6,0};
        quickSort(arr,0,arr.length-1);
        for (int i = 0; i < arr.length; i++) {
            if(i < arr.length-1){
                System.out.print(arr[i]+",");
                continue;
            }
            System.out.print(arr[i]);
        }
    }

}

快速排序

原文：https://www.cnblogs.com/lukeweijava/p/12074969.html