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

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

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. 命名的艺术

• 首先，要给这命名点赞，概括性很棒：递归-合并（当然，这样说有一些牵强，毕竟递归只是实现“分”的一种方法，不过是记忆其步骤的好方法）

2. 那么什么是“分”，递归是怎么实现“分”的？

• “对一个元素很多的数组排序太麻烦了，如果这个数组只有一个元素就好了”，这便是“分”要达到的效果。我们只需要每次让子数组（你可以把原数组想象成二叉树的根）长度减半（方案相同，所以可以递归），便可以实现“分”。

3. 如何合并？

• 前面说到，我们希望数组只有一个元素，通过“分”，我们得到了许多只有一个元素的数组（只有一个元素，必然有序），把它们合并是一件非常容易的事，合并之后就得到了有序子数组，所以，我们需要一个函数来合并两个有序数组。

代码如下：

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.");
    }

}

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

	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++];
        }
    }

优化前：

优化后：

可以看到，通过传参的方式完成复制带来的优化还是比较可观的。

4. 一个例题
   力扣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

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

/**
 * 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的位置）。

2. 如何避免极端情况？

• 如果数组是倒序的，且每次都选取第一元素为pivot，则快排的时间复杂度会升至O(N²)
• 故为了避免出现这种极端情况，应优化pivot的选取方案：三位（第一个，中间，最后）取中；随机选取

/**
 * @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;
    }
}

3. 一个例题
   剑指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个数，而不是排序

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);
    }
}

懒人附体，未完待续…

最后

以上就是执着星月为你收集整理的那些高效的排序算法归并排序快速排序的全部内容，希望文章能够帮你解决那些高效的排序算法归并排序快速排序所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。