数据结构与算法 排序

排序算法总结

Posted by 小拳头 on Saturday, December 12, 2020

总结几大排序算法. 主要对比时间复杂度和空间复杂度. 下图是排序算法属性的总结. (表格中希尔排序的部分存疑)

算法 平均时间复杂度 最坏情况 空间复杂度 排序方式 稳定性
冒泡排序 $O(n^{2})$ $O(n^{2})$ $O(1)$ 内部 稳定
选择排序 $O(n^{2})$ $O(n^{2})$ $O(1)$ 内部 不稳定
插入排序 $O(n^{2})$ $O(n^{2})$ $O(1)$ 内部 稳定
希尔排序 $O(nlogn)$ $O(nlog^{2}n)$ $O(1)$ 内部 不稳定
快速排序 $O(nlogn)$ $O(n^{2})$ $O(nlogn)$ 内部 不稳定
归并排序 $O(nlogn)$ $O(nlogn)$ $O(1)$ 外部 稳定
堆排序 $O(nlogn)$ $O(nlogn)$ $O(1)$ 内部 不稳定
计数排序 $O(n+k)$ $O(n+k)$ $O(k)$ 外部 稳定
桶排序 $O(n)$ $O(n^{2})$ $O(n+k)$ 外部 稳定
基数排序 $O(d(n+k))$ $O(d(n+k))$ $O(n+k)$ 外部 稳定

接下来都以把一个array或者list从小到大排列为基准进行介绍.

冒泡排序

从前到后比较, 发现逆序则交换, 每次循环都把最大的值放到最后面. 考虑最坏的情况, 比如表示逆序的情况, 需要排序$1+2+…+(n-1) = \frac{n(n-1)}{2}$次, 所以时间复杂度是$O(n^{2})$. 最好情况就是已经有序, 遍历一次即可. 注意这里的flag可以稍微优化冒泡排序, 因为当子循环没有发生任何交换, 就代表剩下的数据已经成功排列了.

public void bubbleSort(int[] nums) {
    for (int i = 0; i < nums.length; i++) {
        //boolean flag = true; //如果次轮没有交换, 说明已排序成功
        for (int j = 0; j < nums.length - i - 1; j++) {
            if (nums[j] > nums[j + 1]) {
                swap(nums, j, j + 1);
                //flag = false;
            }
        }
        //if (flag) return;
    }
    //System.out.println(Arrays.toString(nums));
}

选择排序

每一轮选最小值, 放在未排序的的首位. 不管数组顺序怎样, 比较的次数不变, 也就是$n(n-1)/2$, 所以时间复杂度是$O(n^2)$, 但交换移动的次数少, 所以可以说简单选择排序的性能略优于冒泡排序.

public void selectSort(int[] nums) {
    for (int i = 0; i < nums.length; i++) {
        int min = nums[i];
        int minIndex = i;
        for (int j = i; j < nums.length; j++) {
            if (nums[minIndex] > nums[j]) {
                min = nums[j];
                minIndex = j;
            }
            swap(nums, i, minIndex);
        }
    }
    //System.out.println(Arrays.toString(nums));
}

插入排序

把数组的值往前插, 前面插入的数组是有序的. 已经有序的话只用遍历一次, 也就是$O(n)$, 否则还是需要$O(n^{2})$的时间. 如果排序是随机的, 可以计算到平均比较和移动次数是$n^{2}/4$. 和冒泡和选择相比, 插入排序性能会好一点.

public void insertSort(int[] nums) {
    for (int i = 1; i < nums.length; i++) {
        int j = i - 1;
        int key = nums[i];
        while (j >= 0 && key < nums[j]) {
            nums[j + 1] = nums[j];
            j--;
        }
        nums[j + 1] = key;
    }
    //System.out.println(Arrays.toString(nums));
}

希尔排序(Shell Sort)

希尔排序好处就是在宏观的序列上排好了序, 在增量逐渐减小的序列上再排序. 是插入排序升级版, 防止小的数在数组末尾, 就会花很多时间插入. 移位法更加明显的体现了插入排序吗可以看出来形式和插入排序一模一样, 不过把gap从1变成了从大到小的动态gap. 时间复杂度$O(nlogn)$/$O(n^{3/2})$(有待考量, 一般说$O(n^{3/2})$适用于更广泛的增量序列.

public void shellSortSwap(int[] nums) {
    for (int gap = nums.length / 2; gap > 0; gap /= 2) {
        for (int i = gap; i < nums.length; i++) { //遍历每一组
            for (int j = i - gap; j >= 0; j -= gap) {
                if (nums[j] > nums[j + gap]) {
                    swap(nums, j, j + gap);
                }
            }
        }
    }
    //System.out.println(Arrays.toString(nums));
}

public void shellSortInsert(int[] nums) {
    for (int gap = nums.length / 2; gap > 0; gap /= 2) {
        for (int i = gap; i < nums.length; i++) { //遍历每一组
            int j = i;
            int key = nums[j];
            while (j >= 0 && key < nums[j]) {
                nums[j + gap] = nums[j];
                j -= gap;
            }
            nums[j + gap] = key;
        }
    }
    //System.out.println(Arrays.toString(nums));
}

快速排序 -> 有问题

把数组分为两部分, 保证第一部分比第二部分小, 再接着分. 对于基准点的选择, 一般有三数取中/随机数的方法. 代码中我只是简单地取了第一个数. 可以把快排看作是是二叉树的先序遍历.

public void quickSort(int[] nums, int left, int right) {
    if (left < right) {
        int p = partition(nums, left, right);
        partition(nums, left, p - 1);
        partition(nums, p + 1, right);
    }
}

private int partition(int[] nums, int left, int right) {
    /* 随机化
        int index = new Random().nextInt(right - left + 1) + left;
        int temp = arr[left];
        arr[left] = arr[index];
        arr[index] = temp;
        int p = arr[left];
    /*
    int p = nums[left];
    while (left < right) {
        while (left < right && nums[right] >= p) right--;
        nums[left] = nums[right];
        while (left < right && nums[left] <= p) left++;
        nums[right] = nums[left];
    }
    nums[left] = p;
    return left;
}

复杂度分析

最坏情况下, 每次划分都包含0个元素和n - 1个元素. $O(0) = 1$, 因为0个元素时直接返回, 划分数组的时间复杂度是$O(n)$, 那么算法运行时间是$T(n) = T(n - 1) + O(0) + O(n) = T(n - 1) + O(n)$. 递归树的方法解, 一共有n层树, 每层划分的负责度是$O(n)$, 所以最后的时间复杂度是$O(n^2)$.

最好情况下, 每次刚好划分数组$T(n) = 2T(n/2) + O(n)$, 递归树的深度变成了$logn$, 所以时间复杂度是$nlogn$. 一般情况下, 用$T(n) = T(9n/10)+ T(n/10) + O(n)$举例, 实际上树的深度也是对数级别, 时间复杂度依然是$nlogn$. 深度在$log_{10/9}n = O(lgn)$处终止.

归并排序

归并排序用了分治的思想, 需要进行logn次循环, 每一趟都会进行n次扫描, 所以时间复杂度总是保持在$nlogn$. 经典的逆序对问题其实就可以通过归并排序的思想来做. 是二叉树的后序遍历.

public void mergeSort(int[] nums, int left, int right) {
    if (left < right) {
        int mid = (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 i = left, j = mid + 1, index = 0;
    while (i <= mid && j <= right) {
        temp[index++] = nums[i] <= nums[j] ? nums[i++] : nums[j++];
    }
    while (i <= mid) temp[index++] = nums[i++];
    while (j <= right) temp[index++] = nums[j++];
    for (int k = 0; k < temp.length; k++) nums[k + left] = temp[k];
}

堆排序

通过大顶堆来排序序列, 每次把最小的取出来之后再做heapify, 直到取出所有点. 最好最坏平均时间复杂度都是$nlogn$, 因为取堆顶重建时间都是$logn$, 而最终需要取$n - 1$次. 但是初始构建堆的时候需要多次比较, 所以如果序列个数比较少就划不来了. 父节点是(i - 1) / 2, 两个子节点是2i + 1和2i + 2.

public void heapSort(int[] nums, int n) {
    buildheap(nums, n);
    for (int i = n - 1; i >= 0; i--) {
        swap(nums, 0, i); //取最大的一个
        heapify(nums, i, 0);
    }
}

private void buildheap(int[] nums, int n) {
    int parent = (n - 2) / 2; //n-1是最后一个节点
    for (int i = parent; i >= 0; i--) {
        heapify(nums, n, i);
    }
}

private void heapify(int[] nums, int n, int index) {
    if (index >= n) return;
    int c1 = 2 * index + 1;
    int c2 = 2 * index + 2;
    int maxIndex = index;
    if (c1 < n && nums[maxIndex] < nums[c1]) maxIndex = c1;
    if (c2 < n && nums[maxIndex] < nums[c2]) maxIndex = c2;
    if (index != maxIndex) {
        swap(nums, maxIndex, index);
        heapify(nums, n, maxIndex);
    }
}

计数排序

用一个array来记保存对应index的数字, 空间换时间.

public void countSort(int[] nums) {
    int maxValue = -1;
    for (int num: nums) {
        if (num > maxValue) {
            maxValue = num;
        }
    }
    int[] buckets = new int[maxValue + 1];
    for (int num: nums) {
        buckets[num]++;
    }
    int index = 0;
    for (int i = 0; i < buckets.length; i++) {
        while (buckets[i] > 0) {
            nums[index++] = i;
            buckets[i]--;
        }
    }
    //System.out.println(Arrays.toString(nums));
}

桶排序

思路同计数排序, 把不同的数字按一定规则放在桶中, 对桶内的数据排序.

基数排序

根据从个位到十位, 十位到百位进行比较, 把数字放进对应的桶中, 再按顺序填回序列.

public void radixSort(int[] nums) {
    //得到最大长度的数字
    int maxValue = nums[0], maxLength = 0;
    for (int num: nums) {
        if (num > maxValue) maxValue = num;
    }
    while (maxValue > 0) {
        maxValue /= 10;
        maxLength++;
    }
    //放入桶
    int[][] bucket = new int[10][nums.length];
    int[] bucketLength = new int[10];
    for (int i = 0, n = 1; i < maxLength; i++, n *= 10) {
        for (int j = 0; j < nums.length; j++) {
            int dight = nums[j] / n % 10;
            bucket[dight][bucketLength[dight]] = nums[j];
            bucketLength[dight]++; //记录每个bucket已经放了多少数字, 对应下一个该放数字的index
        }
        //放入数组
        int index = 0;
        for (int k = 0; k < 10; k++) {
            for (int l = 0; l < bucketLength[k]; l++) {
                nums[index++] = bucket[k][l];
            }
            bucketLength[k] = 0;
        }
    }
    //System.out.println(Arrays.toString(nums));
}

测试类

public class SortTest {
    long startTime;

    @Test
    public void test() {
        int[] nums = new int[50000];
        for (int i = 0; i < 50000; i++) {
            nums[i] = (int)(Math.random() * 5000000);
        }
        Sorting sorting = new Sorting();

        //冒泡排序
        startTime = System.currentTimeMillis();
        sorting.bubbleSort(Arrays.copyOf(nums, nums.length));
        System.out.println("冒泡排序: " + (System.currentTimeMillis() - startTime));

        //选择排序
        startTime = System.currentTimeMillis();
        sorting.selectSort(Arrays.copyOf(nums, nums.length));
        System.out.println("选择排序: " + (System.currentTimeMillis() - startTime));

        //插入排序
        startTime = System.currentTimeMillis();
        sorting.insertSort(Arrays.copyOf(nums, nums.length));
        System.out.println("插入排序: " + (System.currentTimeMillis() - startTime));

        //希尔排序(交换)
        startTime = System.currentTimeMillis();
        sorting.shellSortSwap(Arrays.copyOf(nums, nums.length));
        System.out.println("希尔排序(交换): " + (System.currentTimeMillis() - startTime));

        //希尔排序(插入)
        startTime = System.currentTimeMillis();
        sorting.shellSortSwap(Arrays.copyOf(nums, nums.length));
        System.out.println("希尔排序(插入): " + (System.currentTimeMillis() - startTime));

        //快速排序
        startTime = System.currentTimeMillis();
        int[] quickArray = Arrays.copyOf(nums, nums.length);
        sorting.quickSort(quickArray, 0, quickArray.length - 1);
        System.out.println("快速排序: " + (System.currentTimeMillis() - startTime));
        //System.out.println(Arrays.toString(quickArray));

        //归并排序
        startTime = System.currentTimeMillis();
        int[] mergeArray = Arrays.copyOf(nums, nums.length);
        sorting.mergeSort(mergeArray, 0, mergeArray.length - 1);
        System.out.println("归并排序: " + (System.currentTimeMillis() - startTime));
        //System.out.println(Arrays.toString(mergeArray));

        //堆排序
        startTime = System.currentTimeMillis();
        int[] heapArray = Arrays.copyOf(nums, nums.length);
        sorting.heapSort(heapArray, heapArray.length);
        System.out.println("堆排序: " + (System.currentTimeMillis() - startTime));
        //System.out.println(Arrays.toString(heapArray));

        startTime = System.currentTimeMillis();
        int[] heapArray2 = Arrays.copyOf(nums, nums.length);
        sorting.heapSort2(heapArray2, heapArray.length);
        System.out.println("堆排序: " + (System.currentTimeMillis() - startTime));
        //System.out.println(Arrays.toString(heapArray2));

        //记数排序
        startTime = System.currentTimeMillis();
        sorting.countSort(Arrays.copyOf(nums, nums.length));
        System.out.println("记数排序: " + (System.currentTimeMillis() - startTime));

        //桶排序
        startTime = System.currentTimeMillis();
        sorting.radixSort(Arrays.copyOf(nums, nums.length));
        System.out.println("桶排序: " + (System.currentTimeMillis() - startTime));
    }
}

排序的算法题

剑指Offer51.数组中的逆序对

归并排序, 逆序放入数组的时候计数.

class Solution {

    int res;
    public int reversePairs(int[] nums) {
        res = 0;
        mergeSort(nums, 0, nums.length - 1);
        return res;
    }

    public void mergeSort(int[] nums, int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2;
            mergeSort(nums, left, mid);
            mergeSort(nums, mid + 1, right);
            merge(nums, left, mid, right);
        }
    }

    public void merge(int[] nums, int left, int mid, int right) {
        int[] temp = new int[right - left + 1];
        int i = left, j = mid + 1, index = 0;
        while (i <= mid && j <= right) {
            if (nums[i] <= nums[j]) {
                temp[index++] = nums[i++];
            } else {
                res += mid - i + 1;
                temp[index++] = nums[j++];
            }
        }
        while (i <= mid) temp[index++] = nums[i++];
        while (j <= right) temp[index++] = nums[j++];
        for (int k = 0; k < temp.length; k++) nums[k + left] = temp[k];
    }
}

剑指Offer40.最小的k个数/面试题17.14.最小K个数

快排, 只要筛选的partition点刚好是k, 那么左边就是最小的k个数.

class Solution {
    public int[] smallestK(int[] arr, int k) {
        quickSort(arr, 0, arr.length - 1, k);
        return Arrays.copyOfRange(arr, 0, k);
    }

    public void quickSort(int[] arr, int left, int right, int k) {
        if (left < right) {
            int p = partition(arr, left, right);
            if (p + 1 == k) return;
            else if (p + 1 < k) quickSort(arr, p + 1, right, k);
            else quickSort(arr, left, p - 1, k);
        }
    }

    public int partition(int[] arr, int left, int right) {
        int p = arr[left];
        while (left < right) {
            while (left < right && arr[right] >= p) right--;
            arr[left] = arr[right];
            while (left < right && arr[left] <= p) left++;
            arr[right] = arr[left];
        }
        arr[left] = p;
        return left;
    }
}

147. 对链表进行插入排序

last指针及以前都是有序的, cur只要小于last, 就需要向前插入.

class Solution {
    public ListNode insertionSortList(ListNode head) {
        if (head == null) return head;
        ListNode dummy = new ListNode();
        dummy.next = head;
        ListNode last = dummy.next, cur = last.next;
        while (cur != null) {
            if (cur.val >= last.val) {
                last = last.next;
            } else { //把现在的cur插入到前面的正确位置
                ListNode pre = dummy;
                while (pre.next.val <= cur.val) {
                    pre = pre.next;
                }
                last.next = cur.next;
                cur.next = pre.next;
                pre.next = cur;
            }
            cur = last.next;
        }
        return dummy.next;
    }
}

148. 排序链表

尝试归并排序.

class Solution {
    public ListNode sortList(ListNode head) {
        return mergeSort(head, null);
    }

    public ListNode mergeSort(ListNode head, ListNode tail) { //左闭右开
        if (head == null) return head; //节点数等于0
        if (head.next == tail) { //节点数等于1
            head.next = null; //分离前后结因为后面的merge要两个list
            return head;
        }
        ListNode slow = head, fast = head;
        while (fast != tail) {
            slow = slow.next;
            fast = fast.next;
            if (fast != tail) fast = fast.next;
        }
        ListNode mid = slow;
        ListNode l1 = mergeSort(head, mid);
        ListNode l2 = mergeSort(mid, tail);
        return merge(l1, l2);
    }

    public ListNode merge(ListNode l1, ListNode l2) { //等同leetcode24
        if (l1 == null) return l2;
        if (l2 == null) return l1;
        ListNode head = null;
        if (l1.val <= l2.val) {
            head = l1;
            l1.next = merge(l1.next, l2);
        } else {
            head = l2;
            l2.next = merge(l1, l2.next);
        }
        return head;
    }
}
comments powered by Disqus
CATALOG
    FEATURED TAGS
    java jvm spring 前端 操作系统 数据库 数据结构与算法 网络编程
    FRIENDS