1. 首页
  2. 文章中心
  3. 算法

那些高效的排序算法归并排序快速排序

137 阅读 0 评论
我是靠谱客的博主 执着星月，这篇文章主要介绍那些高效的排序算法归并排序快速排序，现在分享给大家，希望可以做个参考。

排序算法是数据结构与算法的必学内容，校招面试的常考点（咳咳，面向秋招学习），要想熟练的掌握它们，不光要了解过程，更重要的是体会其思想。

为了对比各个排序算法的效率，可以写一个随机数生成器：

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import java.util.Random;

public class MakeArray {

    public static final int ARRAY_LENGTH  = 10000000; // 数组长度为一千万

    public static int[] makeArray() {
        Random r = new Random();
        int[] result = new int[ARRAY_LENGTH];
        for (int i = 0; i < ARRAY_LENGTH; i++) {
            result[i] =  r.nextInt(ARRAY_LENGTH);	// 用随机数填充数组
        }
        return result;
    }
    
}

归并排序

  1. 命名的艺术
  • 首先，要给这命名点赞，概括性很棒：递归-合并（当然，这样说有一些牵强，毕竟递归只是实现“分”的一种方法，不过是记忆其步骤的好方法）
  1. 那么什么是“分”，递归是怎么实现“分”的？
  • “对一个元素很多的数组排序太麻烦了，如果这个数组只有一个元素就好了”，这便是“分”要达到的效果。我们只需要每次让子数组（你可以把原数组想象成二叉树的根）长度减半（方案相同，所以可以递归），便可以实现“分”。
  1. 如何合并？
  • 前面说到，我们希望数组只有一个元素，通过“分”，我们得到了许多只有一个元素的数组（只有一个元素，必然有序），把它们合并是一件非常容易的事，合并之后就得到了有序子数组，所以，我们需要一个函数来合并两个有序数组。

代码如下：

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
import java.util.Arrays;

/**
 * @author bobo
 * @time 2020/08/27
 * @description 归并排序
 */
public class MergeSort {

    public static void sort(int[] nums) {
        sort(nums, 0, nums.length - 1);
    }

     public static void sort(int[] nums, int left, int right) {
        if (left >= right) return;	 // 1个元素，不用排序
        int mid = (left + right) >>> 1;	 // 无符号右移，避免溢出
        sort(nums, left, mid);	
        sort(nums, mid + 1, right);
        if (nums[mid] <= nums[mid + 1]) return;	// 有序，提前返回
        mergeTwoArr(nums, left, mid, right);
    }

    public static void mergeTwoArr(int[] nums, int left, int mid, int right) {
        int[] tmp = new int[right - left + 1];
        int i = left, j = mid + 1, k = 0;
        // 这里可能可读性有些差，但是理解了算法的过程的话也不失为一种优雅的写法
        while (i <= mid && j <= right) {
            tmp[k++] = nums[i] < nums[j] ? nums[i++] : nums[j++];
        }
        while (i <= mid) {
            tmp[k++] = nums[i++];
        }
        while (j <= right) {
            tmp[k++] = nums[j++];
        }

        System.arraycopy(tmp, 0, nums, left, right - left + 1);
    }
   

    public static void main(String[] args) {
        int[] nums = MakeArray.makeArray();  // 随机数生成器
        long start = System.currentTimeMillis();
        sort(nums);
//        System.out.println(Arrays.toString(nums));	// 数组比较大时打印比较耗时
        System.out.println("MergeSort cost time: " + (System.currentTimeMillis() - start) + "ms.");
    }

}

我们注意到，每一次合并都需要有一次复制操作，对于元素比较多的数据来说，这是一个比较耗时的操作，为了消除这种“手动复制”，我们可以以传参的方式得到同样的效果，主体代码如下：

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
	public static void sort(int[] nums) {
        int[] tmp = nums.clone();
        sort(nums, tmp, 0, nums.length - 1);
    }

    public static void sort(int[] nums, int[] tmp, int left, int right) {
        if (left >= right) return;
        int mid = (left + right) >>> 1;
        sort(tmp, nums, left, mid);	 // 注意这里的参数，是颠倒的
        sort(tmp, nums, mid + 1, right);
        mergeTwoArr(nums, tmp, left, mid, right);
    }

    public static void mergeTwoArr(int[] nums, int[] tmp, int left, int mid, int right) {
        int i = left, j = mid + 1, k = left;
        while (i <= mid && j <= right) {
            nums[k++] = tmp[i] < tmp[j] ? tmp[i++] : tmp[j++];
        }
        while (i <= mid) {
            nums[k++] = tmp[i++];
        }
        while (j <= right) {
            nums[k++] = tmp[j++];
        }
    }

优化前：
在这里插入图片描述
优化后：
在这里插入图片描述
可以看到，通过传参的方式完成复制带来的优化还是比较可观的。

  1. 一个例题
    力扣23题 合并K个升序链表（咳咳，面试被问到了哦~）

给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
示例 1：
输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
1->4->5,
1->3->4,
2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

这里就不写解题思路了，直接代码伺候（好吧，就是懒）~

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {

    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) {
            return null;
        }
        return merge(lists, 0, lists.length - 1);
    }

    private ListNode merge(ListNode[] lists, int start, int end) {
        if (start >= end) {
            return lists[start];
        }

        int mid = (start + end) >>> 1;
        ListNode left = merge(lists, start, mid);
        ListNode right = merge(lists, mid + 1, end);
        return mergeTwoLists(left, right);
    }

    private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummyHead = new ListNode(-1);
        ListNode cur = dummyHead;
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                cur.next = new ListNode(l1.val);
                l1 = l1.next;
            } else {
                cur.next = new ListNode(l2.val);
                l2 = l2.next;
            }
            cur = cur.next;
        }
        cur.next = l1 == null ? l2 : l1;
        return dummyHead.next;
    }

}

快速排序

归并排序的时间复杂度是O(NlogN)，且是稳定的排序算法，美中不足的是它的空间复杂度是O(N)，接下来要登场的快速排序，则时间与空间两手抓。

  1. 分而治之
  • 与归并一样，快排的核心思想也是分治
  • 不同的是，归并是“自下而上”（先分成小数组，再合并成大数组），快排则是“自顶向下”（先找到当前pivot的位置）。
  1. 如何避免极端情况？
  • 如果数组是倒序的，且每次都选取第一元素为pivot，则快排的时间复杂度会升至O(N2)
  • 故为了避免出现这种极端情况，应优化pivot的选取方案：三位（第一个，中间，最后）取中；随机选取
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
/**
 * @author bobo
 * @time 2020/08/29
 * @description java code to realize quick sort
 */
public class QuickSort {
    private static final Random r = new Random();

    public static void main(String[] args) {
        int[] arr = MakeArray.makeArray();
//        int[] arr = new int[] {-1, 0, -2, 3, 4, 6, 1, 2, -1, 3, 8, 4, 2, 6};
        long start = System.currentTimeMillis();
        sort(arr);
//        System.out.println(Arrays.toString(arr));
        System.out.println("Quick sort cost time : " + (System.currentTimeMillis() - start) + " ms.");
    }

    public static void sort(int[] nums) {
        quickSort(nums, 0, nums.length - 1);
    }

    public static void quickSort(int[] arr, int start, int end) {
        // 长度大于1
        if (start < end) {
            swap(arr, start, start + r.nextInt(end - start + 1));
            int x = arr[start], i = start, j = end;
            while (i < j) {
                // 找小于基准元素的数
                while (i < j && arr[j] >= x) j--;
                // 填坑
                if (i < j) arr[i++] = arr[j];
                // 找大于等于基准元素的数
                while (i < j && arr[i] < x) i++;
                // 填坑
                if (i < j) arr[j--] = arr[i];
            }
            // 此时 i == j
            arr[i] = x;
            quickSort(arr, start, i - 1);
            quickSort(arr, i + 1, end);
        }
    }

    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}
  1. 一个例题
    剑指Offer40 最小的k个数

输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。
示例 1：
输入：arr = [3,2,1], k = 2
输出：[1,2] 或者 [2,1]
示例 2：
输入：arr = [0,1,2,1], k = 1
输出：[0]

这里直接选取第一个元素为pivot，毕竟我们的目的是找到最小的k个数，而不是排序

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        if (k >= arr.length) {
            return arr;
        }
        return quickSort(arr, k, 0, arr.length - 1);
    }

    private int[] quickSort(int[] arr, int k, int l, int r) {
        int pivot = arr[l];
        int i = l;
        int j = r;
        while (i < j) {
            while (i < j && arr[j] >= pivot) j--;
            if (i < j) arr[i++] = arr[j];
            while (i < j && arr[i] < pivot) i++;
            if (i < j) arr[j--] = arr[i];
        }
        arr[i] = pivot;
        if (i == k) {
            return Arrays.copyOf(arr, k);
        }
        return i < k ? quickSort(arr, k, i + 1, r) : quickSort(arr, k, l, i - 1);
    }
}

懒人附体，未完待续…

最后

以上就是执着星月最近收集整理的关于那些高效的排序算法归并排序快速排序的全部内容，更多相关那些高效内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
点赞(91)

相关文章

各种排序算法的实现与比较各种排序算法的实现和比较
各种排序算法的实现与比较各种排序算法的实现和比较
java排序算法之快速排序
java排序算法之快速排序
最高效的排序方法
最高效的排序方法
排序算法之快速排序（五）
排序算法之快速排序（五）
那些高效的排序算法归并排序快速排序
那些高效的排序算法归并排序快速排序
五种排序方法总结
五种排序方法总结
排序算法和设计模式
排序算法和设计模式
5种排序方式
5种排序方式

评论列表共有 0 条评论

立即
投稿
返回
顶部