Article From:https://www.cnblogs.com/wesleyshare/p/9217089.html

 

Basic ideas:

 

  By dividing the records into two separate parts, one part of the record is smaller than the other part, and can be sorted to the two part of the record to achieve the purpose of the overall order.

The popular point is:

  Find a record in a row of records, and then try to put it in a position where the value on the left is smaller than he is, and the right value is larger than him (positive or reverse), and the record is called pivot.

Then repeat the steps on the left and right side of the pivot until the whole order is reached.

  Look at the fast – row Baidu introduction first

Quick row introduction:

Optimized fast row (only better, no best, this is the same).

package algorithm;

import java.util.Arrays;

/**
 * @author wzy
 * @since 18-6-20
 */
public class QuickSort {

    public static void quickSort(int a[], int low, int high) {
        if (low > high)
            return;
        int pivot;
       //Recursive optimization is used here to reduce the depth of virtual machine stack by iterative method, thereby improving the overall performance.//Please search for things stored in the virtual machine stack
        while (low < high) {
            pivot = partition(a, low, high);
            quickSort(a,low,pivot-1);
            low = pivot + 1;
        }
    }
    
 /**
     * @param a Array of pending*@param low Array initiating subscript*@param high Cut array cut-off subscript*@return pivotsubscripting of*/
    private static int partition(int[] a, int low, int high) {
        int pivot = getPivot(a);
        while (low < high) {
            while (low < high && a[high]>=index)
                high--;
            if (low < high)
                a[low++] = a[high];
            while (low < high && a[low] < index)
                low++;
            if (low < high)
                a[high--] = a[low];
        }
        a[low] = index;
        return low;
    }
    
    /**
     * The choice of pivot directly affects the performance of sorting (the number of recursive calls).* so the closer the pivot we choose, the better the result will be.* use the method of "three numbers in the middle" to get pivot.**@param a Array of pending*@return pivot
     */
    private static int getPivot(int[] a) {
        //Omission parameter check
        int h, m;
        m = (h = a.length - 1) >> 1;
        return a[0] >= a[m] && a[0] <= a[h] ? a[0] :
                (a[m] >= a[0] && a[m] <= a[h] ? a[m] : a[h]);
    }

    public static void main(String[] args) {

        int a[] = {49, 38, 65, 97, 76, 13, 27, 49, 1, 4, 2, 5, 7, 99, 88, 77, 66};
        quickSort(a, 0, a.length - 1);
        System.out.println(Arrays.toString(a));
    }
}

QuickSort

 

  Quick sorting, or other sorting, I have not yet learned that there are perfect sorting algorithms. Different sorting algorithms have their own advantages and disadvantages, so we have to choose suitable algorithms for different situations.

Complexity and stability of fast sorting:

  Average: O (nlogn)

  Best situation: O (nlogn)

  Worst case: O (n2)

  Auxiliary space: O (logn) to O (n)

  Stability: instability

 

Link of this Article: Fast sort (Quick Sort)

Leave a Reply

Your email address will not be published. Required fields are marked *