当前位置：网站首页>Quick sort

Quick sort

2022-06-10 23:57:00 【Li_ XiaoJin】

About quick sort

The idea of quick sorting ：

Select a number from the array as the reference value , Usually choose the first number , Or the last number .
Use double pointer ( Head and tail ) Traverse , Find the first number larger than the reference value from left to right , Find the first number smaller than the reference value from right to left , Swap two positions , Until the head and tail pointers are equal or the head pointer is greater than the tail pointer , Exchange the reference value with the number of the header pointer . After such a round , The number on the left is smaller than the reference value , The number on the right is larger than the reference value .
For the left series , Repeat the above 1,2 step . Repeat for right 1,2 step .
After the recursion of the left and right sequences , Sort complete .

https://lixj.fun/upload/2021/07/%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F-eadb58e4707d48d6a047cecc1b637849.gif

Algorithm complexity ：O(nlogn)

Algorithm space complexity ：O(1)

Algorithm stability ： unstable

public class QuickSort {

    public static void quickSort(int[] arr, int low, int high) {
        int i,j,temp;
        if (i > j) {
            return;
        }

        i = low;
        j = high;

        temp = arr[low];

        while (i < j) {
            while (arr[j] >= temp && i < j) {
                j--;
            }

            while (arr[i] <= temp && i < j) {
                i++;
            }

            if (i < j) {
                //  In exchange for i and j Value 
                swap(arr, i, j);
            }
        }
        //  In exchange for low  and  i  Value 
        swap(arr, low, i);

        quickSort(arr, low, i-1);
        quickSort(arr, i+1, high);

    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }


    public static void main(String[] args){
        int[] arr = {10,7,2,4,7,62,3,4,2,1,8,9,19};
//        int[] arr = {6 ,1 ,2, 7 ,9 ,3 ,4 ,5 ,10 ,8};
        quickSort(arr, 0, arr.length-1);
        System.out.println(Arrays.toString(arr));
    }
}