算法排序----快速排序法

短命女 2022-05-23 10:05 217阅读 0赞

首先我来说一说快速排序算法的核心思想。

这是我在百科上找到的官方定义：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

我来具体解释一下，实际上我们排序的目的就是为了让左侧的值比右侧的值小，那么我们就可以取一个基准值。这个基准值我们可以把它当做是一个序列的左侧，将这个基准值从右往左进行查找，这个时候右侧的起始值实际上是原数组的右侧值，我们设这个下标为right，找到一个比基准值大的值和基准值进行交换。每对比一次我们让right自增一。同时将right 的值代替基准值所在的下标。同理我们这个时候在从左侧向右侧开始查找，设这个下标为left，找到一个比基准值小的值和基准值进行交换，每对比一次我们让left自减一，同时将left的值代替基准值所在的下标(这个地方我们注意一下，这个时候的基准值已经发生了改变实际上刚才的那个right值。)

快速排序的平均时间复杂度也是：O(nlogn)。

下面是一个图例

![70][]

下面我将用我的代码来解释一下具体的算法。

/**
     * 快速排序法
     * @param array
     * @return
     */
    public int[] quickSort(int[] array){
    	if(array.length>0){
    		doQuickSort(array,0,array.length-1);
    	}
    	return array;
    }
    private void doQuickSort(int[] array, int left, int right) {
    	if(left<right){
    		int middle = getMiddle(array,left,right);//实际的排序流程
    		//运用分治法的思想对数组进行递归。
    		doQuickSort(array, left, middle-1);
    		doQuickSort(array, middle+1, right);
    	}
    }

首先我们看到了快速排序我用到了递归的算法，将一个长序列分为短的序列然后将每个短的序列进行递归排序，将每个短的序列排序完成后再合成长的序列对长的序列进行排序。那么我们来看看这个getMiddle 方法。实际上这个方法的返回值是基准值最后应该插入的位置。这个方法如下

/**
     * 获取中间下标
     * @param array
     * @param left
     * @param right
     * @return
     */
    private int getMiddle(int[] array, int left, int right) {
    	int base = array[left];//以左侧为基数
    	int index = left;//记录基数的下标
    	while(left<right){
    		while(left<right&&array[right]>=base){
    			right--;
    		}
    		array[index] = array[right];//将基数所在下标对应的值改为找到的比基数小的值
    		index = right;//修改基数所在的下标位置
    		array[right] = base;//将找到的比基数小的位置的值改为基数的值
    		while(left<right&&array[left]<=base){
    			left++;
    		}
    		array[index] = array[left];
    		index = left;
    		array[left] = base;
    	}
    	return index;
    }

基本思路就和我上述的一样，当left和right的值相等时，我们就结束了整个方法，并将最终的index值返回。我们应该注意每次引用这个方法，整个数组就会完成一次调整，调整的结果就是将传入的序列的左侧值放到它应该在这个序列中的位置。一直递归到最底层完成全部的排序就得到了我们想要的结果。

[70]: /images/20220523/cf1b56988f5d4042b322d1ab39854aa4.png