[eight sorting ③] quick sorting (dynamic graph deduction Hoare method, digging method, front and back pointer method)

Catalog

One 、 Bubble sort （Bubble Sort）

Two 、 Quick sort （Quick Sort）

introduction

Fast sorting algorithm

Algorithm description

A common way to divide an interval into left and right halves according to the reference value ：

1、Hoare edition

2、 Excavation method

3、 Front and back pointer method  

Optimization of quicksort

Smaller scale optimization  

Take the middle of three  

Non recursive implementation of quick sorting

Quick sort summary

---

One 、 Bubble sort （Bubble Sort）

The principle of bubble sorting

From left to right , Compare adjacent elements . Compare one round at a time , You will find the largest or smallest in the sequence . This number will appear from the far right of the sequence .

• Take sorting from small to large as an example ,
• Compare adjacent elements . If the first one is bigger than the second one , Just swap them .
• Do the same for each pair of adjacent elements , From the beginning of the first couple to the end of the last couple . After this step , The last element will be the maximum number .
• Repeat the above steps for all elements , Except for the last one .
• Keep repeating the above steps for fewer and fewer elements each time , Until there's no pair of numbers to compare .
• After the first round of comparison , The largest of all numbers will float to the far right ; After the second round of comparison , The second largest of all numbers will float to the penultimate position …… Just compare it round by round , Finally, sort from small to large . 

When is the fastest

When the input data is already in positive order （ It's all in order , Do I need you to bubble sort ？）

When is the slowest

When the input data is in reverse order （ Write a for loop trans Just output the data , Why do you want to bubble sort it ？）

Algorithm stability  

Bubble sort is to move small elements forward or to move large elements back . Comparison is the comparison of two adjacent elements , The exchange also happens between these two elements . therefore , If two elements are equal , I don't think you'll be bored to exchange them ; If two equal elements are not adjacent , So even if we exchange the two in front of each other to make the two adjacent , It won't be exchanged at this time , So the order of the same elements hasn't changed , So bubble sort is a stable sort algorithm .

Time complexity ：O(n^2)

Spatial complexity ：O(1)

Code

    public static void bubbleSort(int[] array){
        for(int i=0; i< array.length-1 ;i++){
            for(int j = 0; j < array.length-1-i;j++){
                if(array[j] > array[j+1]){
                    swap(array,j,j+1);
                }
            }
        }
    }

Optimize ： Avoid meaningless circular judgment in an orderly situation

public static void bubbleSort2(int[] array){
        for(int i=0; i< array.length-1 ;i++){
            boolean flg = false ;
            for(int j = 0; j < array.length-1-i;j++){
                if(array[j] > array[j+1]){
                    swap(array,j,j+1);
                    flg = true;
                }
            }
            if(!flg){
                break;
            }
        }
    }

Two 、 Quick sort （Quick Sort）

introduction

  Finally, our master is coming , This is listed as 20 Quick sorting, one of the top ten algorithms in the 20th century , We introduced it earlier Shell Sort amount to Directly insert the upgrade of sorting , They all belong to Insert sort class , Heap sort amount to Simply choose the upgrade of sorting , They all belong to Select sort class . and Quick sort In fact, it is the slowest one we thought before Bubble sort upgrade , They all belong to Exchange sort class . That is, it also realizes sorting through continuous comparison and mobile exchange , Just its realization , It increases the time of record comparison and movement , Move records with larger keywords directly from the front to the back , Records with smaller keywords move directly from the back to the front , Thus, the total number of comparisons and mobile exchanges are reduced

Fast sorting algorithm

  The basic idea of quick sorting is ： Any... In the element sequence to be sorted A particular element As At baseline , According to the sorting code, the set to be sorted Split into two subsequences , All elements in the left subsequence are less than the base value , All elements in the right subsequence are greater than the base value , Then the leftmost and rightmost subsequences repeat the process , Until all the elements are aligned in their respective positions .

  Algorithm description

Fast sorting uses divide and conquer to put a string （list） It's divided into two strings （sub-lists）. The specific algorithm is described as follows ：

• Pick a member of the sequence , be called “ The benchmark ”（pivot）;
• Reorder the sequence , All elements smaller than the base value are placed in front of the base value , All elements that are larger than the base value are placed after the base value （ The same number can go to either side ）. After the partition exits , The benchmark is in the middle of the sequence . This is called a partition （partition） operation ;
• recursively （recursive） Sort the substrings of elements that are less than the base value and elements that are greater than the base value .

//  Let's say that... Is sorted in ascending order array Array [left, right) Sort the elements in the interval 
void QuickSort(int[] array, int left, int right)
{
if(right - left <= 1)
return;
//  Align... According to the reference value array Array of  [left, right) The elements in the interval are divided 
int div = partion(array, left, right);
//  After the division is successful, use div The left and right parts are formed for the boundary  [left, div)  and  [div+1, right)
//  Recursive row [left, div)
QuickSort(array, left, div);
//  Recursive row [div+1, right)
QuickSort(array, div+1, right);
}

  The above is a recursive implementation of quick sorting Main frame , Discovery and Binary tree preorder traversal The rules are very much like , When writing a recursive framework, you can think about the pre order traversal rules of binary tree, which can be written quickly , In the following sequence, you only need to analyze how to divide the data in the interval according to the benchmark value .

A common way to divide an interval into left and right halves according to the reference value ：

1、Hoare edition

Hoare Law is the founder of fast platoon Hoare Named , It is also the initial implementation version of fast platoon . Its basic idea is to use Two pointers Respectively point to the... Of the array to be sorted start and ending . 

 

• If we take the header value as our key value , Then we must let the right pointer move first
• If we take the tail value as our key value , Then we must let the left pointer move first

Pictured , We take the header value as key value

How to move and How to find benchmark

• right Pointer until less than key The value of just stopped
• left Pointer until greater than key The value of just stopped
• take left and right Exchange the corresponding values . Repeat the above process until the two meet
• After encounter , take key The value of the subscript is exchanged with the value where it meets
• At this point, the meeting place is the benchmark

Let's use the dynamic diagram to deduce  

Code ：

 //Hoare Law 
    public static int partitionHoare(int[] array,int low,int high){
        int key = low;
        while(low < high){
            while (low < high && array[high] >= array[key]){
                high--;
            }
            // here high Subscript is the number you are looking for 
            while (low < high && array[low] <= array[key]){
                low++;
            }
            // here low Subscript is the number you are looking for 
            swap(array,low,high); //low and high Subscript element exchange 
        }
        // here low and high Met 
        swap(array,low,key);
        return low;
    }
    public static void quickSort(int[] array,int left,int right){
        if(left >= right) return;
        int pivot = partition(array,left,right);
        quickSort(array,left,pivot-1);
        quickSort(array,pivot+1,right);
    }

It should be noted that

2. Excavation method

 

  We need to be in key Dig a hole （ hold 6 Take it out and put it in one tmp variable ）, Form a pit , then R Look to the left 6 Put the small one into the pit , A new pit is formed , then L Look right , Find the ratio 6 Big , Put it into a new pit

We still use dynamic graph to deduce

  The advantage of digging is that it is easier for us to understand , According to this idea, we write a fast platoon by digging a pit  

// Excavation method 
    public static int partitionHole(int[] array,int low,int high){
        int tmp = array[low];
        while(low < high) {
            while (low < high && array[high] >= tmp){
                high--;
            }
            array[low] = array[high];
            while (low < high && array[low] <= tmp){
                low++;
            }
            array[high] = array[low];
        }
        array[low] = tmp;
        return low;

    }

    public static void quickSort(int[] array,int left,int right){
        if(left >= right) return;
        int pivot = partitionHole(array,left,right);
        quickSort(array,left,pivot-1);
        quickSort(array,pivot+1,right);
    }

3、 Front and back pointer method  

edition 1 

seeing the name of a thing one thinks of its function , need Two pointers , One in front, one in back , Use them separately cur Indicates the front pointer ,prev Represents the back pointer , At the beginning , Our rules cur stay prev The next position of , Here we still choose the first number as the benchmark

• prev Each time, it needs to point to the last number less than the benchmark value from the left to itself
• If cur The value of is greater than the reference value , At this time, only cur++
• If cur The pointing position is smaller than the reference value
• Then we let prev++
• Judge prev++ Whether it is related to cur Equal position
• If not equal , The exchange cur and prev Value
• until cur > R after , We'll exchange prev and key, In this way, the position of the reference value is determined

Now we are still Dynamic graph deduction

Code

// Front and back pointer method 1
private static int partition(int[] array,int low,int high){
        int prev = low;
        int cur = low+1;
        while (cur <= high){
            if(array[cur] < array[low] && array[++prev]!=array[cur]){
                swap(array,cur,prev);
            }
            cur++;
        }
        swap(array,prev,low);
        return low;
    }

    public static void quickSort(int[] array,int left,int right){
        if(left >= right) return;
        int pivot = partition(array,left,right);
        quickSort(array,left,pivot-1);
        quickSort(array,pivot+1,right);
    }

edition 2

This way of writing may be better understood , But the essence is the same

// Front and back pointer method 2
    private static int partition2(int[] array,int low,int high){
        int d = low+1;
        int tmp = array[low];
        for(int i = low+1;i <= high; i++){
            if(array[i] < tmp){
                swap(array,i,d);
                d++;
            }
        }
        swap(array,d-1,low);
        return d-1;
    }


    public static void quickSort(int[] array,int left,int right){
        if(left >= right) return;
        int pivot = partition2(array,left,right);
        quickSort(array,left,pivot-1);
        quickSort(array,pivot+1,right);
    }

Optimization of quicksort

Smaller scale optimization  

Every time you recurse , The data is slowly becoming orderly

When the amount of data is small and tends to be orderly , We can directly use insert sorting to optimize

  public static int partitionHole(int[] array,int low,int high){
        int tmp = array[low];
        while(low < high) {
            while (low < high && array[high] >= tmp){
                high--;
            }
            array[low] = array[high];
            while (low < high && array[low] <= tmp){
                low++;
            }
            array[high] = array[low];
        }
        array[low] = tmp;
        return low;

    }
  public static void quickSort(int[] array,int left,int right){
        if(left >= right) return;
        if(right-left+1 <= 10000){  // The small-scale sorting in a certain interval is directly inserted into the sorting 
            // Insert sort 
            insertSortRange(array,left,right);
            return;
        }
        int pivot = partitionHole(array,left,right);
        quickSort(array,left,pivot-1);
        quickSort(array,pivot+1,right);
    }
  public static void insertSortRange(int[] array,int low, int end){
        for(int i = low+1 ; i<=end ;i++){
            int tmp = array[i];
            int j = i-1;
            for(; j >= low ; j--){
                if(array[j] > tmp){
                    array[j+1] = array[j];
                }else{
                    break;
                }
            }
            array[j+1] = tmp;
        }
    }

  But this optimization has not been fundamentally solved In order Optimization with too deep recursion

If you want to fundamentally solve the problem , Try to make each division more uniform

Take the middle of three  

  We use it Take the middle of three choose key

• Take the three Numbers ： head , tail , In the middle element Size centered The one of

Then exchange this element with the team head element , As key

  Let's take a look at the code

 public static int partitionHole(int[] array,int low,int high){
        int tmp = array[low];
        while(low < high) {
            while (low < high && array[high] >= tmp){
                high--;
            }
            array[low] = array[high];
            while (low < high && array[low] <= tmp){
                low++;
            }
            array[high] = array[low];
        }
        array[low] = tmp;
        return low;

    }    
// Take the three Numbers , Find the first , in , Of the last three numbers   Subscript of a medium-sized number 
    private static int medianOfThreeIndex(int[] array, int left, int right){
        int mid = left + ((right-left)>>>1);
        //int mid = (right+left)/2 ;
        if(array[left] < array[right]){
            if(array[mid] < array[left]){
                return left;
            }else if(array[mid] > array[right]){
                return right;
            }else{
                return mid;
            }
        }else{
            if(array[mid] < array[right]){
                return right;
            }else if(array[mid] > array[left]){
                return left;
            }else{
                return mid;
            }
        }
    }
    public static void quickSort(int[] array,int left,int right){
        if(left >= right) return;
        //1. The small-scale sorting in a certain interval is directly inserted into the sorting 【 The optimization is the comparison within the interval 】
        if(right-left+1 <= 10000){
            // Insert sort 
            insertSortRange(array,left,right);
            return;
        }
        //2. Take the middle of three 【 What is optimized is the segmentation of itself 】
        int index = medianOfThreeIndex(array,left,right);
        swap(array,left,index);

        int pivot = partitionHole(array,left,right);
        quickSort(array,left,pivot-1);
        quickSort(array,pivot+1,right);
    }

Non recursive implementation of quick sorting

We need to use Stack

We used to be after we had determined the benchmark , Do the same operation recursively for the remaining intervals

Now let's create a stack , Put the left of the remaining interval 、 The subscripts at the right position are put into the stack respectively , As shown in the figure, a benchmark has been found 6 The situation of

   then Pop up an element at the top of the stack 9 to H, Pop up another stack top element 6 to L, According to the new L and H Find a new benchmark , Repeat the above operation

  Code

// Excavation method 
    public static int partitionHole(int[] array,int low,int high){
        int tmp = array[low];
        while(low < high) {
            while (low < high && array[high] >= tmp){
                high--;
            }
            array[low] = array[high];
            while (low < high && array[low] <= tmp){
                low++;
            }
            array[high] = array[low];
        }
        array[low] = tmp;
        return low;
    } 
// Quick sort （ Non recursive ）
    public static void quickSortNor(int[] array,int left,int right){
      Stack<Integer> stack = new Stack<>();
        int pivot = partitionHole(array,left,right);
        if(pivot > left+1){
            // Explain that there are two or more data on the left 
            stack.push(left);
            stack.push(pivot-1);
        }
        if(pivot < right-1){
            stack.push(pivot+1);
            stack.push(right);
        }
        while (!stack.isEmpty()){
            right = stack.pop();
            left = stack.pop();

            pivot = partitionHole(array,left,right);
            if(pivot > left+1){
                // Explain that there are two or more data on the left 
                stack.push(left);
                stack.push(pivot-1);
            }
            if(pivot < right-1){
                stack.push(pivot+1);
                stack.push(right);
            }
        }
    }

Quick sort summary

1. The overall performance and usage scenarios of quick sort are quite good , That's why we call it quick sort
2. Time complexity ：O(N*logN)
3. Spatial complexity ：O(logN)
4. stability ： unstable