刻意学习“快速排序”算法

引言

在刷leetcode的时候,遇到了一个数组的题“[数组拆分](https://leetcode-cn.com/problems/array-partition-i/ "数组拆分")”;详细的请见链接。

简单来说,这个题目要求的是给定长度为 2n 的数组, 你的任务是将这些数分成 n 对, 例如 (a1, b1), (a2, b2), …, (an, bn) ,使得从1 到 n 的 min(ai, bi) 总和最大。

这道题据我所知,比较好的解法思路就是先排序,然后把偶数下标的元素值加起来,它们的和就是题目要求的值。

可如何选择排序算法呢,在leetcode的描述中也限定了元素值的范围,和元素个数n的最大值。在这个条件下使用 计数排序 当然也是可以的,并且时间复杂度也是比较低的。
但是刷leetcode的目的不就是让自己掌握更多的算法么。所以决定使用 快速排序 来做。

快速排序

快排么,很早就知道了,是基于比较排序中最快的排序方法了。当初也学过,但是没得其要领,通过这次代码实践,才算真正的领悟。

快速排序的思想:

  • 如果要排序数组中下标从 start 到 end 之间的一组数据,我们选择 start 到 end 之间的任意一个数据作为 pivot(分区点)。
  • 我们遍历 start 到 end 之间的数据,将小于pivot的放到左边,将大于pivot的放到右边,将pivot放到中间。经过这一步骤之后,数组p到r之间的数据就被分成了三个部分,前面 start 到 q-1 之间都是小于pivot的,中间是 pivot ,后面的q+1到 end 之间是大于pivot的。
  • 根据分治、递归的处理思想,我们可以用递归排序下标从 start 到q-1之间的数据和下标从q+1到 end 之间的数据,直到区间缩小为1,就说明所有的数据都有序了。

其实上面这个思想还是很好理解啦,主要难点是代码实现的时候,如何基于交换元素来实现把小于pivot的数据移动到pivot的左边,把大于pivot的元素移动到pivot的右边

Show Me The Code

    private int arrayPairSum(int[] nums) {
        // 对nums进行快速排序
        quick_sort(nums, 0, nums.length - 1);

        // 对题目进行求解
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            if (i % 2 == 0) {
                sum += nums[i];
            }
        }
        return sum;
    }

    private void quick_sort(int[] arr, int start, int end) {
        if (start >= end) return;

        // 通过partition函数获取pivot
        int pivot = partition(arr, start, end);

        quick_sort(arr, start, pivot - 1);
        quick_sort(arr, pivot + 1, end);

    }

    private int partition(int[] arr, int start, int end) {
        // 难点在这里,简单说就是利用 i 和 j 指针来判定要交换位置的元素。
        int pivot = arr[end];
        int i = start;
        for (int j = start; j < end; j++) {
            // i 会指向大于pivot的元素
            // j 和 i 是同起点;当 j 位置上的元素小于pivot时,就与 i 指向的元素交换位置。
            if (arr[j] < pivot) {
                swap(arr, i, j);
                i = i + 1;
            }
        }
        // 在最后,将 pivot 插入中间的位置。
        swap(arr, i, end);

        return i;
    }

    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

结尾

这道题有人笑称就是考察每种排序算法复杂度的。我当时用的第一种解法是使用 Arrays.sort()方法对数组进行排序,提交后发现耗时36ms,然后我又手动实现了快速排序,再提交后耗时是32ms,结果是并没有什么太大的提升,后面我又阅读了Arrays的源码发现它使用的也是快速排序。
顺便看看快速排序的时间空间复杂度吧,计算复杂度的过程比较麻烦,懒得整了。

时间复杂度 O(nlogn)
空间复杂度 O(1)

Related Posts

发表评论

电子邮件地址不会被公开。 必填项已用*标注

© All Right Reserved