欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

排序算法-快速排序

程序员文章站 2022-07-08 23:03:14
...

一.快速排序的基本原理

快速排序分为以下几步:

第一步:在数组中任意选取一个数作为基准数(pivot)

第二步:通过处理,将数组中大于基准数的数都放在基准数的右边,小于基准数的数都放在基准数的左边。

第三步:通过第二步,对基准数的左右两边再重复第一步和第二步的操作,不断重复,直到区间里只剩下一个或者没有元素为止。

二.快速排序图解

排序算法-快速排序

三.快速排序代码(Java) 

import javax.swing.plaf.basic.BasicArrowButton;
import java.util.ArrayList;
import java.util.Arrays;


public class QuickSort {
    public static void main(String[] args) {
        int[] array = {9,13,12,3,0,3,21};
        qucikSort(array);
        System.out.println(Arrays.toString(array));
    }

    private static void qucikSort(int[] array) {
        quickSortDiGui(array,0,array.length-1);
    }

    private static void quickSortDiGui(int[] array,int left, int right) {
        //当left大于right即证明左边或者右边没有元素
        //当left等于right即证明只有一个元素不用再比较
        if(left >= right){
            return;
        }
        /*
            快速排序:
                1.选取一个基准点(此处选最左边的元素)
                2.将比基准点小的元素放在基准点的左边,将比基准点大的元素放在基准点的右边。最后将基准点与中间的值交换,并且返回基准点的位置
                3.一轮结束后,基准点的左边和右边分别一个小的数组重复第二步操作,直到基准点左边或者着右边的元素为1个或者0个(即采用分治方法)
         */
        //1.传进来一个数组之后,先进行一次第二步的操作(partition)返回值为mid
        int mid =  partition(array,left,right);
        quickSortDiGui(array,left,mid-1);
        quickSortDiGui(array,mid+1,right);
    }

    private static int partition(int[] array, int left, int right) {
        int begin = left;
        int end = right;
        int pivot = array[left];
        while(begin<end){
            while(begin < end && array[end] >= pivot){
                end--;
            }
            while(begin < end && array[begin]<= pivot){
                begin++;
            }
            swap(array,begin,end);
        }
        swap(array,begin,left);
        return begin;
    }

    private static void swap(int[] array, int begin, int end) {
        int t = array[begin];
        array[begin] = array[end];
        array[end] = t;
    }

}

四.复杂度分析

排序算法-快速排序

五.注意事项(循环必须先执行end--)

排序算法-快速排序 

如上图,6在左,9在右  我们将6作为基数。

假设从左边开始(与正确程序正好相反)

while (nums[i] <= index && i < j) { 
    i++; 
}
while (nums[j] >= index && j > i) {
    j--;
}
按照这个代码逻辑,走一遍,i 就会移动到现在的 数字 7 那个位置停下来,而  j 原来在 数字 9 那个位置

于是,j 也会停留在数字7 那个位置,然后 i == j了,这时候交换基准数和nums[i]

交换后的数组为:7 1 2 6 9 

这时候,你会发现问题来了,这结果不对呀!!!

问题在于当我们先从在边开始时,那么 i 所停留的那个位置肯定是大于基数6的

而在上述例子中,为了满足 i<j 于是 j也停留在7的位置,但最后交换回去的时候,7就到了左边

不行,因为我们原本 交换后数字6在边应该是全部小于6,右边全部大于6,但现在不行了。

所以,我们必须从右边开始,也就是从基准数的对面开始。