java之快速排序代码

java之快速排序代码

快速排序

快速排序代码

	将最后一位作为准参数，分为两块，大于准参数的放在右边，小于准参数的放在左边，再从每一块中将最后一个作为准参数，以此类推进行。直接看代码

public class QuickSort {

    public static void main(String[] args) {
    }

    @Test
    public void test (){
    	// 当最后一位数是最小值或者最大值时，需要做一些特殊处理
        int[] arr = {4,8,2,1,6,7,5,9,10};
		// 随机选取准参数
 		int a =  (int)(Math.random()*(arr.length));
        System.out.println("a:" +a);;
        QuickSort(arr,0,a);
        // int a = 5;
        // QuickSort(arr,0,arr.length-1);
        print(arr);
    }

    public int Partition(int[] arr,int low,int high){
        // 获取基准数
        int piv = arr[high];
        int left = low;
        int right = high - 1;
        while (left < right){
            while (left <= right && arr[left] <= piv ){
                left++;
            }
            while (left <= right && arr[right] >=piv){
                right--;
            }
            if (left < right){
                swap(arr,left,right);
            }
        }
        if (arr[high] > arr[left]){
            return left;
        }
        swap(arr,left,high);
        return left;
    }

    public void QuickSort (int[] arr ,int low,int high) {
        if (low < high){
            int p = Partition(arr,low,high);
            QuickSort(arr,low,p-1);
            QuickSort(arr,p+1,high);
        }
        // 随机获取准参数时，后面一段的处理 或者以第一值为准参数时 
        else if (low == high && low <= arr.length){
            int p = Partition(arr,low,arr.length-1);
            QuickSort(arr,low,p-1);
            QuickSort(arr,p+1,arr.length-1);
        }
    }

    public static void swap(int[] arr, int i, int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void print(int[] arr){
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }
}

结果如下： 每次选择的准参数不同，产生的结果相同

发现了一个bug

改良后的代码

    public void QuickSort (int[] arr ,int low,int high) {
        if (low < high){
            int p = Partition(arr,low,high);
            if (p ==0){
                QuickSort(arr,0,0);
            } else {
                QuickSort(arr,low,p-1);
                QuickSort(arr,p+1,high);
            }
        } else if (low == high && low <= arr.length){
            lToR(arr,low,arr.length - 1);
        }
    }

    public void lToR (int[] arr ,int low,int high){
        if (low < high) {
            int p = Partition(arr, low, high);
            lToR(arr, low, p - 1);
            if (p != arr.length) {
                lToR(arr, p + 1, high);
            }
        }
    }