Boom LeetCode入门（二）O(NlogN)时复的排序算法

发表于 2022-05-05 更新于 2022-05-08 分类于 Boom LeetCode 阅读次数：

前言

Boom LeetCode(一)中介绍了常用排序算法选择排序、冒泡排序和插入排序，这些排序算法的时间复杂度均为，排序效率较低，而对于排序，结合二分法和归并思想能够有效提升算法查询效率，本部分中介绍时间复杂度的排序算法。

归并排序

算法思路

归并排序通过递归地划分左右数组，对左右数组完成排序后，再合并两个数组，完成最终数组的排序，算法思路如下：

代码实现

代码实现：

package p2.sort_nlogn;

import java.util.Scanner;

//归并排序
public class MergeSort {

    //处理输入输出
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("请输入排序数字个数==========>");
        int n = sc.nextInt();
        int[] nums = new int[n];
        System.out.println("请输入数据============>");
        for (int i = 0; i < n; i++) {
            nums[i]= sc.nextInt();
        }
        mergeSort(nums);
        for (int num : nums) {
            System.out.print(num + " ");
        }
    }

    //调用函数
    private static void mergeSort(int[] nums) {
        if(nums == null || nums.length < 2){
            return;
        }
        sort(nums, 0, nums.length - 1);
    }

    //归并排序核心代码
    private static void sort(int[] nums, int l, int r) {
        if(l == r){
            return;
        }
        int m = l + (r - l) / 2; //int m = l + ((r - l) >> 1);
        sort(nums, l , m);
        sort(nums, m+1, r);
        merge(nums, l, m, r);
    }

//    借助辅助数组完成左右数组合并
    private static void merge(int[] nums, int l, int m, int r) {
        int[] arr = new int[r - l + 1];
        int index = 0;
        int i = l;
        int j = m + 1;
        while(i <= m && j <= r){
            arr[index++] = nums[i] <= nums[j] ? nums[i++]:nums[j++];
        }
        while(i <= m){
            arr[index++] = nums[i++];
        }
        while(j <= r){
            arr[index++] = nums[j++];
        }
        for (int k = 0; k < arr.length; k++) {
            nums[l + k] = arr[k];
        }
    }


}

以master公式计算其时间复杂度为

其中a=2, b=2, d=1即

所以其时间复杂度为

归并排序时间复杂度低的原因是，相比于part1中提到的时间复杂度为的排序算法，这些算法每一次排序过程都要经过一个长时间的元素比较，浪费了大量的比较次数。而归并排序中，每一次合并的两个数组都是有序的，这大大降低了比对次数，从而降低了算法的时间复杂度

由于归并排序中借用了其它数组完成数组的合并，因而该排序为外排序算法

额外空间复杂度为

思考：

快速排序

算法思路

快速排序经历了多个版本的迭代优化，不同版本基本思路如下：

代码实现

代码实现：

package p2.sort_nlogn;

import com.sun.org.apache.bcel.internal.generic.SWAP;
import jdk.internal.org.objectweb.asm.commons.StaticInitMerger;

import java.util.Scanner;

//快速排序3.0
public class Code02_QuickSort {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("请输入排序数字个数==========>");
        int n = sc.nextInt();
        int[] nums = new int[n];
        System.out.println("请输入数据============>");
        for (int i = 0; i < n; i++) {
            nums[i] = sc.nextInt();
        }
        quickSort(nums);
        for (int num : nums) {
            System.out.print(num + " ");
        }
    }

    private static void quickSort(int[] nums) {
        if(nums == null || nums.length < 2){
            return;
        }
        sort(nums, 0, nums.length-1);
    }

    private static void sort(int[] nums, int l, int r) {
        if(l < r){
            //快排3.0不同于其它两个版本就在于这里
            //不再是仅取数组尾元素作为flag
            //而是随机选择一个数，并与数组尾元素交换作为flag
            //这降低了数据整体有序时，O(n^2)复杂度的时间复杂度
            swap(nums, r, l + (int)Math.random() * (r - l + 1));
            
            //数组p用来记录一次排序完成后，当前排序数字的左右边界
            // (例如以5为flag时，排序完成后[1, 3, 2, 4, 5, 5, 9, 7])
            //这时返回p[0]为4，p[1]为5
            //partition函数功能即为找到左右边界的具体实现
            int[] p = partition(nums, l, r);

            //以左右边界划分数组，递归调用函数排序
            sort(nums, l, p[0] - 1);
            sort(nums, p[1] + 1, r);
        }
    }

    private static int[] partition(int[] nums, int l, int r) {
        //less始终记录左边界的下一位
        //more始终记录右边界
        int less = l - 1;
        int more = r;
        while(l < more){
            if(nums[l] < nums[r]){
                swap(nums, ++less, l++);
            }else if(nums[l] > nums[r]){
                swap(nums, --more, l);
            }else{
                l++;
            }
        }
        swap(nums, more, r);
        return new int[]{less + 1, more};
    }

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