1. Basic introduction

Quicksort is an improvement on bubbling sort.

2. Basic ideas

By sorting the sorted data into two independent parts, one part of all the data is smaller than the other part of all the data, and then according to this method to the two parts of the data respectively for quick sorting, the whole sorting process can be carried out recursively, in order to achieve the entire data into an ordered sequence

3. Application examples

  1. Sort [-9,78,0,23,-567,70] from smallest to largest using quicksort.
  2. [Test 8W and 800W]
   public static void quickSort(int[] arr,int left, int right) {
        int l = left; / / left subscript
        int r = right; / / right subscripts
        / / the pivot axis value
        int pivot = arr[(left + right) / 2];
        int temp = 0; // Temporary variable, used as an exchange
        // The purpose of the while loop is to place less than the pivot value to the left
        // Greater than the pivot value to the right
        while( l < r) {
            // Keep looking to the left of pivot until the value is greater than or equal to the pivot value
            while( arr[l] < pivot) {
                l += 1;
            }
            // Keep looking to the right of the pivot until the value is less than or equal to the pivot value
            while(arr[r] > pivot) {
                r -= 1;
            }
            // If l >= r, then the left and right values of pivot are both
            // Less than or equal to the pivot value, the right-hand side is all greater than or equal to the pivot value
            if( l >= r) {
                break;
            }

            / / exchange
            temp = arr[l];
            arr[l] = arr[r];
            arr[r] = temp;

            // If arr[l] == pivot is equal r--, move forward
            if(arr[l] == pivot) {
                r -= 1;
            }
            // if arr[r] == pivot = l++, then pivot = l++
            if(arr[r] == pivot) {
                l += 1; }}// if l == r, l++, r--, otherwise stack overflow occurs
        if (l == r) {
            l += 1;
            r -= 1;
        }
        // Recurse to the left
        if(left < r) {
            quickSort(arr, left, r);
        }
        // Recursive to the right
        if(right > l) { quickSort(arr, l, right); }}Copy the code

Testing:

	public static void main(String[] args) {
        //int[] arr = {-9,78,0,23,-567,70, -1,900, 4561};

        // Test the execution speed of quicksort
        // Create a random array for 80000
        int[] arr = new int[8000000];
        for (int i = 0; i < 8000000; i++) {
            arr[i] = (int) (Math.random() * 8000000); // Generate a [0, 8000000) number
        }

        System.out.println("Pre-sort");
        Date data1 = new Date();
        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
        String date1Str = simpleDateFormat.format(data1);
        System.out.println("The time before sorting is equal to" + date1Str);

        quickSort(arr, 0, arr.length-1);

        Date data2 = new Date();
        String date2Str = simpleDateFormat.format(data2);
        System.out.println("The time before sorting is equal to" + date2Str);
        //System.out.println("arr=" + Arrays.toString(arr));
    }
Copy the code