【算法必会】快速排序

By | 5月 28, 2021

简单理解,取基准值M,将小于M的值都挪到左边,大于M的值都挪到右边,然后对左右两个区间分别重复进行选基准和排序,
直到左右都排列完,得到的数组是排好序的,时间复杂度(NlogN)
注意:在基本有序的情况下不适合用快排,快排适合数据打乱的情况下

源码如下:

public  static void quickSortMethod(int[] arr,int left,int right){
        if(left>right) return;
        int tmp=arr[left];
        int i=left;
        int j=right;
        while (i<j){
            while(arr[j]>=tmp&&j>i){
                j--;
            }
            if(tmp>arr[j]){
                arr[i]=arr[j];
            }
            while(arr[i]<=tmp&&i<j){
                i++;
            }
            if(tmp<arr[i]) {
                arr[j] = arr[i];
            }

        }
        arr[i]=tmp;
        quickSortMethod(arr,0,i-1);
        quickSortMethod(arr,i+1,right);
    }

    public static void main(String[] args){
        int[] arr={1,3,2,24,1,2,4,3,3,55,6,77,41};
        quickSortMethod(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));
    }

 

发表评论

邮箱地址不会被公开。