Quick Sort

妖狐艹你老母 2022-01-16 12:39 198阅读 0赞

public static <T> void quickSort(T[] items)
    {
        quickSort(items, null);
    }
    	
    public static <T> void quickSort(T[] items, Comparator<T> comparator)
    {
        if (items == null || items.length == 0)
            return;
    		
        quickSort(items, comparator, 0, items.length - 1);
    }
    	
    private static <T> void quickSort(T[] items, Comparator<T> comparator, int low, int high)
    {
        // Select a pivot
        T pivot = items[calcPivot(low, high)];
    	
        // Move all items smaller than pivot to its left.
        // Move all items greater than pivot to its right.
        int i = low;
        int j = high;
        while (i <= j)
        {
            while (compare(comparator, items[i], pivot) < 0)
    	    i ++;
    	    
            while (compare(comparator, items[j], pivot) > 0)
    	    j --;
    	    
            if (i <= j)
            {
                swap(items, i, j);
                i ++;
                j --;
            }
        }
        
        if (low < j)
            quickSort(items, comparator, low, j);
    		
        if (i < high)
            quickSort(items, comparator, i, high);
    }	
    
    private static <T> int compare(Comparator<T> comparator, T a, T b)
    {
        if (comparator != null)
            return comparator.compare(a, b);
        else
            return ((Comparable)a).compareTo((Comparable)b);
    }
    	
    private static int calcPivot(int low, int high)
    {
        return low + (high - low) / 2;
    }
    	
    private static void swap(T[] items, int i, int j)
    {
        T temp = items[i];
        items[i] = items[j];
        items[j] = temp;
    }

转载于:https://blog.51cto.com/7371901/1604124