QuickSort

喜欢ヅ旅行 2022-06-02 05:11 56阅读 0赞

快速排序：基于分治的思想，是冒泡排序的改进型。首先在数组中选择一个基准点（该基准点的选取可能影响快速排序的效率，后面讲解选取的方法），然后分别从数组的两端扫描数组，设两个指示标志（l指向起始位置，h指向末尾)，首先从后半部分开始，如果发现有元素比该基准点的值小，就交换l和h位置的值，然后从前半部分开始扫秒，发现有元素大于基准点的值，就交换l和h位置的值，如此往复循环，直到l>=h,然后把基准点的值放到hi这个位置。一次排序就完成了。以后采用递归的方式分别对前半部分和后半部分排序，当前半部分和后半部分均有序时该数组就自然有序了

package sort;
    
    /**
     * Created by long.chen  on 2018/1/4.
     */
    public class QuickSort<T extends Comparable<T>> {
        /**
         *
         * @param array
         * @param l
         * @param h
         */
        public void quickSort(T[] array, int l, int h) {
            int low = l;
            int height =h;
            if (low >= height)
                return;
            //选择卫兵
            T temp = array[low];
            while (low < height) {
                while (low < height && temp.compareTo(array[height]) <= 0) {
                    height--;
                }
                while (low < height && temp.compareTo(array[low]) >= 0) {
                    low++;
                }
                if (low < height) {
                    T tempSec = array[height];
                    array[height] = array[low];
                    array[low] = tempSec;
                }
            }
                 array[l]=array[low];
                 array[low]=temp;
    
                 quickSort(array,l,height-1);
                 quickSort(array,height+1,h);
        }
        public static void main(String[] args){
            QuickSort<Integer> quickSort= new QuickSort<>();
            Integer[] arr = {10,9,8,88,4,29,0,4,8};
            quickSort.quickSort(arr, 0, arr.length-1);
            for (int i = 0; i < arr.length; i++) {
                System.out.println(arr[i]);
            }
        }
    }