时间戳

首页 > 技术文章 > 快速排序的两种方法

快速排序的两种方法

linzeliang1222 2020-10-07 12:03 原文

第一种（左右指针法）

  • 我们取中间值作为基准值，又两个索引分别从左端和右端向中间靠拢，比较大小，将小于基准值的归到左边，大于基准值的归到右边，这时l与r可能都指向基准值的位置，但是下一步两个索引自增，l大于r(但是要保证不超出边界即left与right)，这是l作为右半部分的新的递归的left，right就是right；r作为左半部分的新的递归的right，left就是left，直到排序剩下一个就是有序的了

  • 代码实现

    import java.util.Arrays;

/**
 * @Description: 快速排序第一种
 * @Author: LinZeLiang
 * @Date: 2020-10-04
 */
public class QuickSortFirst {

    public static void main(String[] args) {
        int[] a = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};

        quickSort(a, 0, a.length - 1);

        System.out.println(Arrays.toString(a));

    }

    /**
     * @param a 待排序数组
     * @param left 指向第一个元素
     * @param right 指向最后一个元素
     */
    public static void quickSort(int[] a, int left, int right) {
        //记录下基准值（中间值）
        int pivot = a[(left + right) / 2];
        int l = left;
        int r = right;

        while (l <= r) {
            //直到找到比基准值大的
            while (a[l] < pivot) {
                l++;
            }
            //直到找到比基准值小的
            while (a[r] > pivot) {
                r--;
            }
            //交换两边数字，l向右移动一位，r向左移动一位
            if (l <= r) {
                int temp = a[l];
                a[l] = a[r];
                a[r] = temp;
                l++;
                r--;
            }
        }

        //将左半部分递归排序
        if (r > left) {
            quickSort(a, left, r);
        }
        //将右半部分进行递归排序
        if (l < right) {
            quickSort(a, l, right);
        }
    }
}

第二种（挖坑法）

  • 将数组的第一个数作为基准值，思想其实和第一个一样，只是实现的方法不一样而已

  • 代码实现

    import java.util.Arrays;

/**
 * @Description: 快速排序第二种
 * @Author: LinZeLiang
 * @Date: 2020-10-04
 */
public class QuickSortSecond {

    public static void main(String[] args) {
        int[] a = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};

        quickSort(a, 0, a.length - 1);

        System.out.println(Arrays.toString(a));
    }

    /**
     * 快速排序
     * 
     * @param a 待排序数组
     * @param left 指向子数组第一个索引
     * @param right 指向子数组最后一个索引
     */
    public static void quickSort(int[] a, int left, int right) {
        if (left < right) {
            //将链表一分为二得到中间值
            int center = partion(a, left, right);
            //然后分别再对两边递归排序
            quickSort(a, left, center - 1);
            quickSort(a, center + 1, right);
        }
    }

    /**
     * 进行分区
     * 
     * @param a 待分区数组
     * @param left 指向数组第一个索引
     * @param right 指向数组最后一个索引
     */
    public static int partion(int[] a, int left, int right) {
        //将第一个值作为基准值
        int pivot = a[left];
        while (left < right) {
            //当队尾元素大于等于pivot时，往前移动，直到找到小于pivot
            //与基准值pivot比较时必须要添加等号，否则出现一样的数字就会进入无限递归循环
            while (left < right && a[right] >= pivot) {
                right--;
            }
            //队尾元素小于pivot，将其赋值给left
            a[left] = a[right];
            //当队头元素小于等于pivot时，往后移动指针，直到大于基准值
            while (left < right && a[left] <= pivot) {
                left++;
            }
            //队头元素大于pivot，将其赋值给right
            a[right] = a[left];
        }
        //由于基准值pivot还处于未分配状态，
        //跳出循环时left和right相等,此时的left或right就是pivot的正确索引位置
        //由原理部分可以很清楚的知道left位置的值并不是pivot,所以需要将tmp赋值给a[left]
        //第一个循环时将right赋值给left，right处于未分配状态，第二个循环时将left的赋值给right，left处于未分配状态
        a[left] = pivot;
        return left;
    }
}

第三种（和第二种类似）

  • 和第二种类似，只不过将两个函数合并成一个函数了

  • 代码实现

    import java.util.Arrays;

/**
 * @Description: 快速排序第二种
 * @Author: LinZeLiang
 * @Date: 2020-10-04
 */
public class QuickSortSecond {

    public static void main(String[] args) {
        int[] a = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};

        quickSort(a, 0, a.length - 1);

        System.out.println(Arrays.toString(a));
    }

    /**
     * 快速排序
     * 
     * @param arr 待排序数组
     * @param left 指向子数组第一个索引
     * @param right 指向子数组最后一个索引
     */
    public static void quickSort(int[] arr, int left, int right) {
        if (left < right) {
            int l = left;
            int r = right;
            // 把left的值作为基准中保存起来，此时该位置看作一个坑
            int pivot = arr[l];
            // 先进行左右分别挖坑填入
            while (l < r) {
                while (l < r && arr[r] >= pivot) {
                    r--;
                }
                arr[l] = arr[r];
                while (l < r && arr[l] <= pivot) {
                    l++;
                }
                arr[r] = arr[l];
            }
            // 最后把基准值填回去
            arr[l] = pivot;
            
            // 然后分别递归两边
            quickSork(arr, left, l-1);
            quickSork(arr, l+1, right);
        }
    }
}

推荐阅读