使用分割思想实现快速排序算法

            public
            class
             QuickSort{
    
    
            //
            分割数组,将数组分成两部分. 一部分比pivot(枢轴元素)大,另一部分比pivot小
            private
            static
            int parition(int[] arr, int left, int right){
        
        int pivot = media3(arr, left, right);
        int i = left;
        int j = right - 1;//注意 ,在 media3()中 arr[right-1]就是 pivot
        
        //应对特殊情况下的数组,比如数组长度 小于3if(i >= j)
            return i;
        
        for(;;)
        {
            while(arr[++i] < pivot){}
            while(arr[--j] > pivot){}
            if(i < j)
                swap(arr, i, j);
            elsebreak;
        }
        
        swap(arr, i, right-1);//restore pivot 将枢轴元素放置到合适位置:arr左边元素都比pivot小,右边都比pivot大return i;// 返回 pivot的 索引    }
    
    
    //三数取中,用在快排中随机选择枢轴元素时privatestaticint media3(int[] arr, int left, int right){
        if(arr.length == 1)
            return arr[0];
        
        if(left == right)
            return arr[left];
        
        int center = (left + right) / 2;
        
        //找出三个数中的最小值放到 arr[left]if(arr[center] < arr[left])
            swap(arr, left, center);
        if(arr[right] < arr[left])
            swap(arr, left, right);
        
        //将 中间那个数放到 arr[media]if(arr[center] > arr[right])
            swap(arr, center, right);
        
        swap(arr, center, right-1);//尽量将大的元素放到右边--将privot放到右边, 可简化 分割操作(partition).return arr[right-1];//返回中间大小的那个数    }
        
    privatestaticvoid swap(int[] arr, int left, int right){
        int tmp = arr[left];
        arr[left] = arr[right];
        arr[right] = tmp;
    }
    
    
    publicstaticvoid quickSort(int[] arr){
        quickSort(arr, 0, arr.length - 1);
    }
    privatestaticvoid quickSort(int[] arr, int left, int right){
        if(left < right){
            int pivot_index = parition(arr, left, right);
            quickSort(arr, left, pivot_index - 1);
            quickSort(arr, pivot_index + 1, right);
        }
    }
    
    
    publicstaticvoid main(String[] args) {    
        int[] arr2 = {1,0,-1};
        quickSort(arr2);
        for (int i : arr2) {
            System.out.print(i + " ");
        }
    }
}