数据结构与算法-排序

2020-10-18 HGNULB 约 22 分钟

文章信息 3 个分类 2 个标签

分类

数据结构与算法美团滴滴

一、排序基础

二、基础排序

冒泡排序

每轮通过交换相邻的逆序元素，把未排序区间的最大值移到末尾。

从数组头部开始，依次比较相邻元素。

前者较大时交换，一轮后最大值到达末尾。

缩小未排序区间；若本轮没有交换，提前结束。

复杂度：最好 $O(n)$，平均和最坏 $O(n^2)$，空间 $O(1)$，稳定。

public class BubbleSort {
    public int[] sortArray(int[] nums) {
        if (nums == null || nums.length < 2) {
            return nums;
        }

        int n = nums.length;

        for (int i = 0; i < n - 1; i++) {
            boolean swapped = false;

            for (int j = 0; j < n - 1 - i; j++) {
                if (nums[j] > nums[j + 1]) {
                    swap(nums, j, j + 1);
                    swapped = true;
                }
            }

            // 一轮没有任何交换，说明已经有序，提前退出
            if (!swapped) {
                break;
            }
        }

        return nums;
    }

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

        nums[i] = nums[j];
        nums[j] = temp;
    }
}

func bubbleSort(nums []int) {
    n := len(nums)
    for i := 0; i < n-1; i++ {
        swapped := false
        for j := 0; j < n-1-i; j++ {
            if nums[j] > nums[j+1] {
                nums[j], nums[j+1] = nums[j+1], nums[j]
                swapped = true
            }
        }
        // 一轮没有任何交换，说明已经有序，提前退出
        if !swapped {
            break
        }
    }
}

选择排序

每轮从未排序区间选出最小值，放到已排序区间的末尾。

记录未排序区间第一个元素的下标。

向后扫描，找到更小的元素就更新下标。

扫描结束后交换最小值，再缩小未排序区间。

复杂度：时间 $O(n^2)$，空间 $O(1)$；跨位置交换会打乱相等元素的顺序，因此不稳定。

public class SelectionSort {
    public int[] sortArray(int[] nums) {
        if (nums == null || nums.length < 2) {
            return nums;
        }

        int n = nums.length;

        for (int i = 0; i < n - 1; i++) {
            int minIndex = i;

            for (int j = i + 1; j < n; j++) {
                if (nums[j] < nums[minIndex]) {
                    minIndex = j;
                }
            }

            // 每轮只做一次交换
            if (minIndex != i) {
                swap(nums, i, minIndex);
            }
        }

        return nums;
    }

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

        nums[i] = nums[j];
        nums[j] = temp;
    }
}

func selectionSort(nums []int) {
    n := len(nums)
    for i := 0; i < n-1; i++ {
        minIndex := i
        for j := i + 1; j < n; j++ {
            if nums[j] < nums[minIndex] {
                minIndex = j
            }
        }
        // 每轮只做一次交换
        if minIndex != i {
            nums[i], nums[minIndex] = nums[minIndex], nums[i]
        }
    }
}

插入排序

把数组前半部分看作有序区间，像整理手牌一样，逐个把后面的元素插入正确位置。

从第二个元素开始，暂存当前值。

从后向前检查有序区间，将更大的元素依次后移。

把当前值放入空出的位置，继续处理下一个元素。

复杂度：最好 $O(n)$，平均和最坏 $O(n^2)$，空间 $O(1)$，稳定；适合小规模或近乎有序的数组。

public class InsertionSort {
    public int[] sortArray(int[] nums) {
        if (nums == null || nums.length < 2) {
            return nums;
        }

        for (int i = 1; i < nums.length; i++) {
            int cur = nums[i];
            int j = i;

            // 比 cur 大的元素整体后移一位，腾出插入位置
            while (j > 0 && nums[j - 1] > cur) {
                nums[j] = nums[j - 1];
                j--;
            }

            nums[j] = cur;
        }

        return nums;
    }
}

func insertionSort(nums []int) {
    for i := 1; i < len(nums); i++ {
        cur := nums[i]
        j := i
        // 比 cur 大的元素整体后移一位，腾出插入位置
        for j > 0 && nums[j-1] > cur {
            nums[j] = nums[j-1]
            j--
        }
        nums[j] = cur
    }
}

三、分治排序

归并排序

先把大问题拆成小问题，分别排好序后，再把两个有序部分合并。

从中点把数组分成左右两半。

递归拆分，直到每组只剩一个元素。

用双指针合并两个有序部分；相等时先取左边，保持稳定。

复杂度：时间 $O(n \log n)$，空间 $O(n)$，稳定。

public class MergeSort {
    public int[] sortArray(int[] nums) {
        if (nums == null || nums.length < 2) {
            return nums;
        }

        mergeSort(nums, 0, nums.length - 1);

        return nums;
    }

    private void mergeSort(int[] nums, int left, int right) {
        if (left >= right) {
            return;
        }

        int mid = left + (right - left) / 2;

        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);
        merge(nums, left, mid, right);
    }

    private void merge(int[] nums, int left, int mid, int right) {
        int[] temp = new int[right - left + 1];
        int p = 0;
        int p1 = left;
        int p2 = mid + 1;

        while (p1 <= mid && p2 <= right) {
            // 相等时取左边，保证稳定性
            if (nums[p1] <= nums[p2]) {
                temp[p++] = nums[p1++];
            } else {
                temp[p++] = nums[p2++];
            }
        }

        while (p1 <= mid) {
            temp[p++] = nums[p1++];
        }

        while (p2 <= right) {
            temp[p++] = nums[p2++];
        }

        System.arraycopy(temp, 0, nums, left, temp.length);
    }
}

func sortArray(nums []int) []int {
    if len(nums) <= 1 {
        return nums
    }
    mid := len(nums) / 2
    left := sortArray(append([]int(nil), nums[:mid]...))
    right := sortArray(append([]int(nil), nums[mid:]...))
    return merge(left, right)
}

func merge(left, right []int) []int {
    res := make([]int, 0, len(left)+len(right))
    p1, p2 := 0, 0
    for p1 < len(left) && p2 < len(right) {
        // 相等时取左边，保证稳定性
        if left[p1] <= right[p2] {
            res = append(res, left[p1])
            p1++
        } else {
            res = append(res, right[p2])
            p2++
        }
    }
    res = append(res, left[p1:]...)
    res = append(res, right[p2:]...)
    return res
}

快速排序

选一个基准，把数组分成较小和较大的两部分，再用同样的方法排序两边。

随机选一个元素作为基准，交换到区间最左边。

右指针找比基准小的值，左指针找比基准大的值，交替填入空出的位置。

两个指针相遇时放回基准，再递归排序左右区间。

随机基准可减小有序数组的退化风险；代码使用严格比较，避免大量相等元素集中到一侧。

复杂度：平均 $O(n \log n)$，最坏 $O(n^2)$，递归栈平均 $O(\log n)$，不稳定。

public class QuickSort {
    public int[] sortArray(int[] nums) {
        if (nums == null || nums.length < 2) {
            return nums;
        }

        quickSort(nums, 0, nums.length - 1);

        return nums;
    }

    private void quickSort(int[] nums, int left, int right) {
        if (left >= right) {
            return;
        }

        // 随机选基准并换到最左侧，避免有序输入退化为 O(n^2)
        int index = left + (int) (Math.random() * (right - left + 1));

        swap(nums, left, index);
        int pivot = nums[left];
        int i = left;
        int j = right;

        while (i < j) {
            while (i < j && nums[j] > pivot) {
                j--;
            }

            if (i < j) {
                nums[i++] = nums[j];
            }

            while (i < j && nums[i] < pivot) {
                i++;
            }

            if (i < j) {
                nums[j--] = nums[i];
            }
        }

        nums[i] = pivot;
        quickSort(nums, left, i - 1);
        quickSort(nums, i + 1, right);
    }

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

        nums[i] = nums[j];
        nums[j] = temp;
    }
}

func sortArray(nums []int) []int {
    if len(nums) <= 1 {
        return nums
    }
    quickSort(nums, 0, len(nums)-1)
    return nums
}

func quickSort(nums []int, left, right int) {
    if left >= right {
        return
    }
    // 随机选基准并换到最左侧，避免有序输入退化为 O(n^2)
    index := rand.Intn(right-left+1) + left
    nums[left], nums[index] = nums[index], nums[left]
    pivot := nums[left]
    i, j := left, right
    for i < j {
        for i < j && nums[j] > pivot {
            j--
        }
        if i < j {
            nums[i] = nums[j]
            i++
        }
        for i < j && nums[i] < pivot {
            i++
        }
        if i < j {
            nums[j] = nums[i]
            j--
        }
    }
    nums[i] = pivot
    quickSort(nums, left, i-1)
    quickSort(nums, i+1, right)
}

四、堆结构

堆排序

升序排序使用大顶堆：堆顶始终是当前最大值，把它依次放到数组末尾。

从最后一个非叶子节点开始下沉，自下而上建成大顶堆。

把堆顶与未排序区间的末尾元素交换，最大值完成归位。

缩小堆的范围，将新堆顶与较大的子节点交换，直到恢复大顶堆。

复杂度：建堆 $O(n)$，整体 $O(n \log n)$，空间 $O(1)$，不稳定。

public class HeapSort {
    public int[] sortArray(int[] nums) {
        if (nums == null || nums.length < 2) {
            return nums;
        }

        int n = nums.length;

        // 建堆：从最后一个非叶子节点开始依次下沉
        for (int i = n / 2 - 1; i >= 0; i--) {
            siftDown(nums, i, n);
        }

        for (int j = n - 1; j > 0; j--) {
            swap(nums, 0, j);
            siftDown(nums, 0, j);
        }

        return nums;
    }

    private void siftDown(int[] nums, int k, int size) {
        while (2 * k + 1 < size) {
            int j = 2 * k + 1;

            if (j + 1 < size && nums[j + 1] > nums[j]) {
                j++;
            }

            if (nums[k] >= nums[j]) {
                break;
            }

            swap(nums, k, j);
            k = j;
        }
    }

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

        nums[i] = nums[j];
        nums[j] = temp;
    }
}

func heapSort(nums []int) {
    n := len(nums)
    // 建堆：从最后一个非叶子节点开始依次下沉
    for i := n/2 - 1; i >= 0; i-- {
        siftDown(nums, i, n)
    }
    for j := n - 1; j > 0; j-- {
        nums[0], nums[j] = nums[j], nums[0]
        siftDown(nums, 0, j)
    }
}

func siftDown(nums []int, k, size int) {
    for 2*k+1 < size {
        j := 2*k + 1
        if j+1 < size && nums[j+1] > nums[j] {
            j++
        }
        if nums[k] >= nums[j] {
            break
        }
        nums[k], nums[j] = nums[j], nums[k]
        k = j
    }
}

构造初始堆

堆排序过程图解

五、手写排序

912. 排序数组

面试手写排序的标准题，使用随机化快排。随机选基准避免有序数组持续极端分区；partition 使用严格比较 > 和 <，让相等元素分散到两侧，避免全相等数组退化。期望时间复杂度为 $O(n \log n)$，递归栈的期望空间复杂度为 $O(\log n)$。

class Solution {
    public int[] sortArray(int[] nums) {
        if (nums == null || nums.length < 2) {
            return nums;
        }

        quickSort(nums, 0, nums.length - 1);

        return nums;
    }

    private void quickSort(int[] nums, int left, int right) {
        if (left >= right) {
            return;
        }

        // 随机选基准，避免有序用例退化为 O(n^2)
        int index = left + (int) (Math.random() * (right - left + 1));

        swap(nums, left, index);
        int pivot = nums[left];
        int i = left;
        int j = right;

        while (i < j) {
            // 严格比较 > 和 <，让相等元素均分到两侧，避免全相等用例退化
            while (i < j && nums[j] > pivot) {
                j--;
            }

            if (i < j) {
                nums[i++] = nums[j];
            }

            while (i < j && nums[i] < pivot) {
                i++;
            }

            if (i < j) {
                nums[j--] = nums[i];
            }
        }

        nums[i] = pivot;
        quickSort(nums, left, i - 1);
        quickSort(nums, i + 1, right);
    }

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

        nums[i] = nums[j];
        nums[j] = temp;
    }
}

func sortArray(nums []int) []int {
    if len(nums) <= 1 {
        return nums
    }
    quickSort(nums, 0, len(nums)-1)
    return nums
}

func quickSort(nums []int, left, right int) {
    if left >= right {
        return
    }
    // 随机选基准，避免有序用例退化为 O(n^2)
    index := rand.Intn(right-left+1) + left
    nums[left], nums[index] = nums[index], nums[left]
    pivot := nums[left]
    i, j := left, right
    for i < j {
        // 严格比较 > 和 <，让相等元素均分到两侧，避免全相等用例退化
        for i < j && nums[j] > pivot {
            j--
        }
        if i < j {
            nums[i] = nums[j]
            i++
        }
        for i < j && nums[i] < pivot {
            i++
        }
        if i < j {
            nums[j] = nums[i]
            j--
        }
    }
    nums[i] = pivot
    quickSort(nums, left, i-1)
    quickSort(nums, i+1, right)
}

六、有序合并

88. 合并两个有序数组

nums1 尾部预留了空位，使用三个指针从后往前放入较大元素，避免覆盖 nums1 中还没处理的值。收尾只需拷贝 nums2 的剩余元素。时间复杂度为 $O(m + n)$，额外空间为 $O(1)$。

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i = m - 1;
        int j = n - 1;
        int k = m + n - 1;

        while (i >= 0 && j >= 0) {
            // 从后往前填较大者，不会覆盖 nums1 未处理的元素
            if (nums1[i] > nums2[j]) {
                nums1[k--] = nums1[i--];
            } else {
                nums1[k--] = nums2[j--];
            }
        }

        while (j >= 0) {
            nums1[k--] = nums2[j--];
        }
    }
}

func merge(nums1 []int, m int, nums2 []int, n int) {
    i, j, k := m-1, n-1, m+n-1
    for i >= 0 && j >= 0 {
        // 从后往前填较大者，不会覆盖 nums1 未处理的元素
        if nums1[i] > nums2[j] {
            nums1[k] = nums1[i]
            i--
        } else {
            nums1[k] = nums2[j]
            j--
        }
        k--
    }
    for j >= 0 {
        nums1[k] = nums2[j]
        j--
        k--
    }
}

21. 合并两个有序链表

用哑结点统一头结点处理，双指针每次把较小节点接到结果链表尾部，最后直接挂接未走完的链表。相等时优先取 l1，保持合并的稳定性。时间复杂度为 $O(m + n)$，额外空间为 $O(1)$。

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;

        while (l1 != null && l2 != null) {
            // 相等时优先取 l1，保持稳定性
            if (l1.val <= l2.val) {
                cur.next = l1;
                l1 = l1.next;
            } else {
                cur.next = l2;
                l2 = l2.next;
            }

            cur = cur.next;
        }

        cur.next = (l1 != null) ? l1 : l2;

        return dummy.next;
    }
}

func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
    dummy := &ListNode{}
    cur := dummy
    for l1 != nil && l2 != nil {
        // 相等时优先取 l1，保持稳定性
        if l1.Val <= l2.Val {
            cur.Next = l1
            l1 = l1.Next
        } else {
            cur.Next = l2
            l2 = l2.Next
        }
        cur = cur.Next
    }
    if l1 != nil {
        cur.Next = l1
    } else {
        cur.Next = l2
    }
    return dummy.Next
}

七、链表排序

148. 排序链表

链表不适合随机访问，使用归并排序：快慢指针找中点并断链，递归排序两半，再合并两条有序链表。fast 从 head.next 出发，保证偶数长度时两半都不为空。时间复杂度为 $O(n \log n)$，递归栈空间为 $O(\log n)$。

class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        // fast 从 head.next 出发，保证偶数长度时 slow 停在中点偏左
        ListNode slow = head;
        ListNode fast = head.next;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        ListNode mid = slow.next;

        slow.next = null;

        return merge(sortList(head), sortList(mid));
    }

    private ListNode merge(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;

        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                cur.next = l1;
                l1 = l1.next;
            } else {
                cur.next = l2;
                l2 = l2.next;
            }

            cur = cur.next;
        }

        cur.next = (l1 != null) ? l1 : l2;

        return dummy.next;
    }
}

func sortList(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }
    // fast 从 head.Next 出发，保证偶数长度时 slow 停在中点偏左
    slow, fast := head, head.Next
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
    }
    mid := slow.Next
    slow.Next = nil
    return merge(sortList(head), sortList(mid))
}

func merge(l1, l2 *ListNode) *ListNode {
    dummy := &ListNode{}
    cur := dummy
    for l1 != nil && l2 != nil {
        if l1.Val <= l2.Val {
            cur.Next = l1
            l1 = l1.Next
        } else {
            cur.Next = l2
            l2 = l2.Next
        }
        cur = cur.Next
    }
    if l1 != nil {
        cur.Next = l1
    } else {
        cur.Next = l2
    }
    return dummy.Next
}

八、参考资料

https://www.programiz.com/dsa/heap-sort

https://sort.hust.cc

.article-image.is-loading { width: var(--article-image-width, 100%); height: auto; } .article-image.is-loading img { position: static; width: auto !important; height: auto !important; opacity: 1; pointer-events: auto; } .article-image-spinner { display: none; }

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2020/16696008

许可本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！