快速排序 - 简书

快速排序

分两步操作：
第一步，分区
将最右边的值作为基准位，把小于基准位的数放左边，大于基准位的数放右边
最后将左指针停留位置的值与基准位交换，并返回左指针的索引（作为递归的基准位索引）

 /** 分区 */
 private int partition(int left_pointer,int right_pointer){
     // 1 最右边的值作为基准位
     int aim_index = right_pointer;
     int aim_value = array[aim_index];
     // 2 从基准位的左边元素开始
     right_pointer --;
     // 3 循环
     while (left_pointer < right_pointer){
         // 先看左边，依次往右递增，大于基准位则停下
         while (array[left_pointer] <= aim_value && left_pointer < right_pointer){
             left_pointer ++;
         }
         // 再看右边，依次往左递减，小于基准位则停下
         while (array[right_pointer] >= aim_value && left_pointer < right_pointer){
             right_pointer --;
         }
         // 4 如果满足条件，停下的左边值和右边值互换
        if (left_pointer < right_pointer){
            swap(left_pointer,right_pointer);
        }else {
            // 否则跳出循环
            break;
        }
     }
     // 5 循环结束，如果满足条件，将基准位和两个指针同位的值比较互换
    if (array[left_pointer] > aim_value){
        swap(left_pointer,aim_index);
    }
    // 6 最后返回左指针
     return left_pointer;
}

第二步，递归
先检查索引，当左指针 >= 右指针则不执行该方法
调用第一步分区方法将数组分为两部分，并将返回的左指针索引作为轴索引

public void sortQuick(int left_index,int right_index){
    // 1 前置条件
    if (left_index >= right_index){
        return;
    }
    // 2 分区，返回轴索引
    int point_index = partition(left_index,right_index);
    // 对基准位左侧部分递归调用
    sortQuick(left_index,point_index);
    // 对基准位右侧部分递归调用
    sortQuick(point_index+1,right_index);
}

完整代码：

package com.sort;

/**
 * @author: jk
 * @since: 2020-03-22 01:02
 * <p>
 * 快速排序
 * </p>
 **/
public class QuickSort {

    private int[] array;

    public QuickSort(int[] array) {
        this.array = array;
    }

    public void sortQuick(int left_index,int right_index){

        // 1 前置条件
        if (left_index >= right_index){
            return;
        }

        // 2 分区，返回轴索引
        int point_index = partition(left_index,right_index);

        // 对基准位左侧部分递归调用
        sortQuick(left_index,point_index);
        // 对基准位右侧部分递归调用
        sortQuick(point_index+1,right_index);
    }


    /** 分区 */
    private int partition(int left_pointer,int right_pointer){

        // 1 最右边的值作为基准位
        int aim_index = right_pointer;
        int aim_value = array[aim_index];

        // 2 从基准位的左边元素开始
        right_pointer --;

        // 3 循环
        while (left_pointer < right_pointer){

            // 先看左边，依次往右递增，大于基准位则停下
            while (array[left_pointer] <= aim_value && left_pointer < right_pointer){
                left_pointer ++;
            }

            // 再看右边，依次往左递减，小于基准位则停下
            while (array[right_pointer] >= aim_value && left_pointer < right_pointer){
                right_pointer --;
            }


            // 4 如果满足条件，停下的左边值和右边值互换
           if (left_pointer < right_pointer){
               swap(left_pointer,right_pointer);
           }else {
               // 否则跳出循环
               break;
           }

        }

        // 5 循环结束，如果满足条件，将基准位和两个指针同位的值比较互换
       if (array[left_pointer] > aim_value){
           swap(left_pointer,aim_index);
       }

       // 6 最后返回左指针
        return left_pointer;
    }


    // 互换方法
    private void swap(int index_1,int index_2){
        int temp = array[index_1];
        array[index_1] = array[index_2];
        array[index_2] = temp;
    }

}

测试方法：

public static void main(String[] args) {
     // int[] arr = {10,7,4,7,62,3,4};
     // int[] arr = {0,2,2,1,2,4,3};
    int[] arr = {3,4,2,1,2,2,0};
    QuickSort quickSort = new QuickSort(arr);
    quickSort.sortQuick(0,arr.length - 1);
    for (int i = 0; i < arr.length; i++) {
        System.out.print(arr[i] + " ");
    }

最后编辑于：2020.03.23 01:14:59