排序算法之快速排序

叁歲伎倆 2022-12-29 14:25 115阅读 0赞

### \[交换排序-快速排序\] ###

**1.算法思想：**

*  选择一个元素作为**基准**，先从右向左遍历数组寻找比基准小的数a，然后从左向右寻找比基准大的数b，交换a和b的值，当左右会面时，与基准数交换值。目的是让基准数处于数组中间位置
 *  可以将基准理解为**分数线**，选取60作为及格线，通过左右交换的方式确定左边都是不及格的元素，右边则都是及格的元素，然后对不及格和及格部分再进行细分，例如及格可以分为优和良，以90和70作为基准；不及格可以分为中和差，以50和30作为判断基准，将元素置于对应的区间内。

**2.流程解析**

定义数组：`int[] array = {60 , 10 , 20 , 90 , 80 , 30 , 40 , 100 , 50 , 70};`

1.  选取 **60** 作为"基准"；
2.  从右向左，寻找比 **60** 小的数，从左向右，寻找比 **60** 大的数；
    
    **===>** \[ **60** , 10 , 20, 90 , 80 , 30 , 40 , 100 , 50 ,70 \]
3.  交换 50 和 90 ；
    
    \[ **60** , 10 , 20, 50 , 80 , 30 , 40 , 100 , 90 ,70 \]
4.  第二次寻找；
    
    **===>**\[ **60** , 10 , 20, 50 , 80 , 30 , 40 , 100 , 90 ,70 \]
5.  交换 40 和 80 ；
    
    \[ **60** , 10 , 20, 50 , 40 , 30 , 80 , 100 , 90 ,70 \]
6.  第三次寻找，此时左右会在 30 的位置会面；
7.  交换 **60** 和 30 ；
    
    \[ 30 , 10 , 20, 50 , 40 , **60** , 80 , 100 , 90 ,70 \]
8.  第一轮排序结束，基数 **60** 被移到了中间位置；
9.  以此类推，以 **30** 作为基准进行下一轮排序；

**代码实现：**

public static void quickSort(int[] array , int left , int right){ 
             //if用于结束递归
            if(left > right){  return; }
            //pivot存放基准数
            int pivot = array[left];
            int i = left;
            int j = right;
            while(i != j){ 
                //从右边开始寻找
                while(array[j] >= pivot && i < j){  j--; }
                //从左边开始寻找
                while(array[i] <= pivot && i < j){  i++; }
                //交换两个元素值
                if(i < j){ 
                    int temp = array[i];
                    array[i] = array[j];
                    array[j] = temp;
                }
            }
            //将基准数换到相对中间的位置
            array[left] = array[i];
            array[i] = pivot;
            
    		//递归处理左边的
            quickSort(array,left,i-1);
            //递归处理右边的
            quickSort(array,i+1,right);
    	}
    	public static void main(String[] args) { 
            int[] array = { 60 , 10 , 20 , 90 , 80 , 30 , 40 , 100 , 50 , 70};
            System.out.println("排序前Array:" + Arrays.toString(array));
            quickSort(array,0,array.length-1);
            System.out.println("排序后Array:" + Arrays.toString(array));
            /* * 排序前Array:[60, 10, 30, 90, 80, 20, 40, 100, 50, 70] * 排序后Array:[10, 20, 30, 40, 50, 60, 70, 80, 90, 100] */
    	}

**小结**：冒泡排序目的是每次循环整个待排序的序列，将最大值放到数组最右侧；而快速排序目的是选择中间值，折中分区，然后再对左右分区数据进行排序。  
**理解≠学会，一定要打断点，debug逐步调试，手动敲一遍代码！！！**