八大排序----快速排序_以数组[5,2,9,4,7,8,6,3,0,1]为例讲解下快速排序每一步是如何进行排序的以及如何

快速排序是一种不怎么稳定的排序，最快时间复杂度为O（nlogn），最慢则需要O（n*n）,作者不太喜欢这个排序，因为这个排序有库函数，谁愿意自己写呢（手动狗头）。

大体思想：

快排采用的是分治的思想，每次将一个数放到属于自己的位置，然后再去对左右排序，依次类推

举例：

数组：5,2,6,9,1,3,4,8,7
如图，以4为基准，一个指针放在i=0，一个放在j=len-1，从右往左找一个比基准小的数（即应该出现在基准左面但却出现在右面了），然后和左指针所处互换，在从左向右找一个比基准大的数，再i，j互换，直到两个指针相遇，基准左面全都是小于基准，右面都大于基准

public static void swap(int[] nums,int i,int j){
        int temp=nums[i];
        nums[i]=nums[j];
        nums[j]=temp;
    }
    public static void quicksort(int[] nums,int start,int end,int k){
        if(start>=end)return;
        int l=start,r=end,mark=nums[start];
        while (l != r) {
            while(nums[r]>=mark&&l<r)r--;
            swap(nums,l,r);
            while(nums[l]<=mark&&l<r)l++;
            swap(nums,l,r);
        }
        quicksort(nums, l+1, end, k);
        quicksort(nums,start,l-1,k);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17