.有梦想的咸鱼丶

.有梦想的咸鱼丶

错误快排代码(先移动首部指针)

代码及运行结果

public class FastSort {

    public static void quikSort(int[] nums, int left, int right){
        if (left >= right){
            return;
        }
        int num = nums[left];
        int start = left;
        int end = right;
        while (start < end){
            // 先移动首部指针
            while (start < end && nums[start] <= num){
                start++;
            }
            while (start < end && nums[end] >= num){
                end--;
            }

            if (start < end){
                int tmp = nums[start];
                nums[start] = nums[end];
                nums[end] = tmp;
            }
        }
        nums[left] = nums[start];
        nums[start] = num;
        quikSort(nums, left, start - 1);
        quikSort(nums, start + 1, right);
    }



    public static void main(String[] args) {
        int[] nums = {34, 1, 5, -2, 0, 35, 36, 38};
        quikSort(nums, 0, nums.length - 1);
        for (int num : nums){
            System.out.print(num + ",");
        }
    }
}

运行结果:-2,5,0,1,35,34,38,36,

错误原因分析

首先要明确快排的步骤:

  1. 以第一个元素为基准点。
  2. 将小于基准点的元素都移到基准点的左边,将大于基准点的元素都移到基准点的右边。
  3. 分别对基准点左右的元素进行快速排序。

步骤2的详细过程是:

  1. 定义两个指针,一个指针从数组首部出发,一个指针从数组尾部出发。
  2. 首部指针遇到比基准元素大的元素就停止,尾部指针遇到比基准元素小的元素就停止。
  3. 交换首部指针和尾部指针指向的元素。
  4. 首尾指针相遇,将基准元素与指针相遇点的元素交换。

问题就出在上述步骤4,考虑如下情况:

指针相遇时:

快速排序指针移动先后顺序问题分析-LMLPHP

 步骤4执行完毕:

快速排序指针移动先后顺序问题分析-LMLPHP

 显而易见,比基准元素34大的元素35被放到了左边。

为什么会出现这种情况呢?

因为先移动的指针一定会等待后移动的指针,那么指针相交的位置一定是先移动的指针(首指针)先停止的位置,这里先移动的指针是首指针,它的停止条件是指针指向的元素>基准元素,那么最终停止的位置(指针相交位置)的元素也是大于基准元素的(特殊情况另论:一个指针始终没动,另一个指针直接移动到头,此时指针终止并不是元素大小导致的),而我们选取的基准元素是数组的第一个元素,也就是在数组的左边,这样最后比基准元素大的元素就被交换到了数组的左边。

所以,当选取最左边的元素为基准元素时,先移动的指针一定要是右边的指针。

同理,当选取最右边的元素为基准元素时,先移动的指针一定要是左边的指针。

正确代码

public class FastSort {

    public static void quikSort(int[] nums, int left, int right){
        // 只有一个元素或者无元素,不进行快排
        if (left >= right){
            return;
        }
        // 选取数组左边的元素为基准元素
        int num = nums[left];
        // 定义首尾指针
        int start = left;
        int end = right;
        // 指针未相交
        while (start < end){
            // 先移动右边的指针
            while (start < end && nums[end] >= num){
                end--;
            }
            // 再移动左边的指针
            while (start < end && nums[start] <= num){
                start++;
            }

            // 两指针终止但没相交,交换元素
            if (start < end){
                int tmp = nums[start];
                nums[start] = nums[end];
                nums[end] = tmp;
            }
        }
        // 两指针相交,将基准元素放入指针相交位置
        nums[left] = nums[start];
        nums[start] = num;
        // 分别对基准元素左右的元素进行快排
        quikSort(nums, left, start - 1);
        quikSort(nums, start + 1, right);
    }



    public static void main(String[] args) {
        int[] nums = {34, 1, 5, -2, 0, 35, 36, 38};
        quikSort(nums, 0, nums.length - 1);
        for (int num : nums){
            System.out.print(num + ",");
        }
    }
}

总结

快排注意点:

  1. 明确快排终止条件:left >= right,即只有一个元素或者没有元素。
  2. 明确指针移动条件,start < end,即首指针在尾指针右边时才能移动。
  3. 明确指针定义:定义指针时,两个指针一定要把基准元素包含进去。(因为指针相交时交换元素并没有判断与基准元素的大小,特殊情况下:一个指针没动,另一个指针直接移动到头,此时指针的终止条件也可能是因为指针相交了,元素与基准元素的大小比较未知,这时候与基准元素交换可能是一次错误的交换,但是如果把基准元素包含进来,就会与基准元素自身交换,不会产生影响)
  4. 明确指针移动顺序:当选取最左边的元素为基准元素时,先移动的指针一定要是右边的指针;当选取最右边的元素为基准元素时,先移动的指针一定要是左边的指针。
05-13 12:02