快速回忆十大排序

Java中Arrays.sort()

通过查看Arrays.sort() 的源码， 可以发现 Arrays.sort() 并不是简单的使用快排，而是根据要排序的长度选择不同的排序。 简单总结：

区间长度	所使用的排序算法
小于47	插入排序
大于47小于286	快排排序
大于286，数据基本有序	归并排序
大于286，数据基本无序	快速排序

进行快排时会计算5个元素如果有相同元素就进行传统快速排序，如果没有相同的就进行双轴快速排序。

插入排序、归并排序、快速排序连源码都在用可见其重要性。

经典十大排序

排序算法	平均时间复杂度	最好情况	最坏情况	空间复杂度	稳定性
冒泡排序	O(n2)	O(n)	O(n2)	O(1)	稳定
选择排序	O(n2)	O(n2)	O(n2)	O(1)	不稳定
插入排序	O(n2)	O(n)	O(n2)	O(1)	稳定
希尔排序	O(n log n)	O(n log2 n)	O(n log2 n)	O(1)	不稳定
归并排序	O(n log n)	O(n log n)	O(n log n)	O(n)	稳定
快速排序	O(n log n)	O(n log n)	O(n2)	O(log n)	不稳定
堆排序	O(n log n)	O(n log n)	O(n log n)	O(1)	不稳定
计数排序	O(n+k)	O(n+k)	O(n+k)	O(n+k)	稳定
桶数排序	O(n+k)	O(n2)	O(n)	O(n+k)	稳定
基数排序	O(n*k)	O(n*k)	O(n*k)	O(n+k)	稳定

不稳定是指排序过程中会把原本有序区间破化成无序的

排序测试力扣题目

力扣 912.排序数组，地址： https://leetcode.cn/problems/sort-an-array/ 除了冒泡、插入会超时以外，其他排序方式都可以通过。

1. 冒泡排序

这应该是大家接触最早的排序。数就像水里的泡泡一样，泡泡从大到小一个个冒出来。 数组形式： [无序区间] [有序区间] ，在无序区间一直比较并交换把最大的冒到有序区间前。 两层for循环，一层循环将一个最大的数放到最后。 动图演示： Java代码

        for(int i = 0; i < nums.length; i++) {
            for(int j = 0; j  < nums.length - 1 - i; j++) {
                if(nums[j] > nums[j + 1]) {
                    //交换
                    int tem = nums[j];
                    nums[j] = nums[j + 1];
                    nums[j  + 1] = tem;
                }
            }
        }

2. 选择排序

插入排序总结一句话就是挑最小的放前面，比较的次数多但是交换的次数少 数组形式： [有序区间] [无序区间] ，在无序区间挑一个最小的数跟在有序区间后面。 两层for循环，一层循环用来找到最小的数。 动图演示： Java代码：

        int minIndex = 0;
        for(int i = 0; i < nums.length - 1; i++) {
            minIndex = i;
            for(int j = i + 1; j < nums.length; j++) {
               if(nums[j] < nums[minIndex]) {
                   minIndex = j;
               }
           }
           //找到最小数的索引，交换
           int tem = nums[i];
           nums[i] = nums[minIndex];
           nums[minIndex] = tem;
        }

3. 插入排序

插入排序总结：拿到一个元素就去找他该在的位置插入进去 数组形式： [有序区间] [无序区间] ，在无序区间拿第一个元素插入到有序区其应该在的位置 从右往左，放第一个比他小的后面，且从右往左遍历过程中把数组右移。

动图演示： Java代码：

        for(int i = 1; i < nums.length; i++) {
            int index = i - 1;
            int tem = nums[i];
            while(index >= 0 && nums[index] > tem) {
                nums[index + 1] = nums[index]; //右移
                index--;
            }
            nums[index + 1] = tem; //把无序部分第一个数插入到有序部分的这里
        }

4. 希尔排序

希尔排序是当时最早突破 O(n2)的排序，是插入排序的改进版本。 插入排序主要在于右移是O(n) 希尔排序的思想是引入一个增量，先两两插入排序，再四四插入排序，最终整体插入排序，这样前面处理完，后面插入移动次数会变少。 每一轮按照事先决定的间隔进行插入排序，间隔依次缩小最后为1。 动图演示： 如果看不懂这个动图，可以先看看这个教程，再回头看这个动图。https://www.runoob.com/data-structures/shell-sort.html Java代码：

        for(int gap = nums.length / 2; gap > 0; gap /= 2) {
            //对每组进行插入排序。 这里和动图不太一样，并不是一组一组进行的，而是各组交叉进行的
            for(int i = gap; i < nums.length; i++) {
                int tem = nums[i];
                int index = i;
                while(index >= gap && nums[index - gap] > tem) {
                    //按分组的位置右移
                    nums[index] = nums[index - gap];
                    index -= gap;
                }
                nums[index] = tem;
            }
        }
        return nums;

5. 归并排序

希尔排序是分治法的一个典型应用，将已有序的子序列合并，得到完全有序的序列；

动图演示： 更直观的图片演示：

Java代码：

    int[] tem;
    public int[] sortArray(int[] nums) {
        tem = new int[nums.length];
        mergeSort(nums, 0, nums.length - 1);
        return nums;
    }

    void mergeSort(int[] nums, int l, int r) {
        if(l >= r) return;
        int mid = (l + r) / 2;
        //分
        mergeSort(nums, l, mid);
        mergeSort(nums, mid + 1, r);
        
        //治(归并)
        int i = l, j = mid + 1;
        int index = 0;
        while(i <= mid && j <= r) {
            if(nums[i] <= nums[j]) {
                tem[index++] = nums[i++];
            }else {
                tem[index++] = nums[j++];
            }
        }
        while(i <= mid) tem[index++] = nums[i++];
        while(j <= r) tem[index++] = nums[j++];

        //把归并完成的这部分赋值回给原始数组
        for(int k = 0; k < r - l + 1; k++) {
            nums[k + l] = tem[k];
        }
    }

6. 快速排序

通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小， 然后再分别对这两部分记录继续进行排序，以达到整个序列有序。 数组形式： [小数] [基准元素] [大数]，在区间中随机挑选一个元素作为基准，小于基准元素的放基准之前，大于基准的放基准之后。 然后再对小数和大数区间做快排

整个流程就是找到基准点应该放置的位置。

动图演示：

Java代码：

    public int[] sortArray(int[] nums) {
        quickSort(nums, 0, nums.length - 1);
        return nums;

    }

    public void quickSort(int[] nums, int left, int right) {
        //顺序选取基准值
        if(left >= right) return;
        int first = left, key = nums[first], end = right;
        while (first < end) {
            //先看右边的， 比基准大就不管
            while (first < end && nums[end] >= key) {
                end--;
            }
            //右边end指向的这个值小于分界值， 交换.
            nums[first] = nums[end];

            //然后走左边
            while (first < end && nums[first] <= key) {
                ++first;
            }
            //如果first指针指向的值大于分界值key, 交换
            nums[end] = nums[first];
        }
        // 左右指针相同， 基准值该在这个位置，使得基准值左右两边是比他小和比他大的数
        nums[first] = key;
        //递归， 对左右两边再进行上面操作
        quickSort(nums, left, first - 1);
        quickSort(nums,first + 1, right);
    }

如果遇到数组是 9 8 7 6 5 4 3 2 1， 再从左往右顺序选取基准值的话，每次都得移动 n 个， 算法时间复杂度退回到O(n2)。 所以最好是随机选取基准，或者提前打乱数组，数组越乱，快排越快 随机选取基准值，快排代码：

    public int[] sortArray(int[] nums) {
        quickSort(nums, 0, nums.length - 1);
        return nums;

    }
    public void quickSort(int[] nums, int left, int right) {
        if(left >= right) return;
        //随机选取基准值
        int index = left + (int)(Math.random() * (right - left + 1));
        int key = nums[index];
        int first = left, end = right;
        nums[index] = nums[first];
        nums[first] = key;
        
        while (first < end) {
            //先看右边的， 比基准大就不管
            while (first < end && nums[end] >= key) {
                end--;
            }
            //右边end指向的这个值小于分界值， 交换.
            nums[first] = nums[end];

            //然后走左边
            while (first < end && nums[first] <= key) {
                ++first;
            }
            //如果first指针指向的值大于分界值key, 交换
            nums[end] = nums[first];
        }
        // 左右指针相同， 基准值该在这个位置，使得基准值左右两边是比他小和比他大的数
        nums[first] = key;

        //递归， 对左右两边再进行上面操作
        quickSort(nums, left, first - 1);
        quickSort(nums,first + 1, right);
    }

7. 堆排序

利用小顶堆。

待补充

8. 计数排序

记录索引位置数的个数，利用索引本身就有序进行排序。 有一个缺点就是得事先知道数据得范围，范围多大就得开多大数组。 动图演示： Java代码：

    public int[] sortArray(int[] nums) {
        int[] dic = new int[100001];
        for(int i = 0; i < nums.length; i++) {
            dic[nums[i] + 50000]++;
        }
        int index = 0;
        for(int i = 0; i < dic.length; i++) {
            for(int j = 0; j < dic[i]; j++) {
                nums[index++] = i - 50000;
            }
        }
        return nums;
    }

9. 桶排序

桶排序是计数排序的升级版， 计数排序是一对一的映射，而桶排序是一对多的映射，把数据分到不同的桶里的元素用其他排序方式排序。 动图演示：

Java代码：

    public int[] sortArray(int[] nums) {
        int n = nums.length;
        int max = nums[0], min = nums[0];
        for(int i = 0; i < n; i++) {
            if(nums[i] > max) max = nums[i];
            if(nums[i] < min) min = nums[i];
        }
        int diff = max - min;
        //设n个桶
        List<Integer>[] buket = new List[n];
        for(int i = 0; i < n; i++) {
            buket[i] = new ArrayList<>();
        }
        //每个桶的范围，防止为0
        int section = diff / n + 1; 
        for(int i = 0; i < n; i++) {
            int id = (nums[i] - min) / section - 1; // -1防止等于 n
            if(id < 0) id = 0;
            buket[id].add(nums[i]);
        }
        //桶内排序
        for(int i = 0; i < n; i++) {
            Collections.sort(buket[i]);
        }
        //返回排序数组
        int index = 0;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < buket[i].size(); j++) {
                nums[index++] = buket[i].get(j);
            }
        }
        return nums;
    }

10. 基数排序

基数排序是桶排序的扩展， 思想是把整数按每位不同放入不同的桶里，按每位进行比较。 比如 32，34，16， 5 排序， 先按个位数排序 32，34，5，16， 再按十位排序5，16，32，34就完事了 【因为之前按个位排序时把 32放在了34前面，所以再进行十位排序时，按顺序来32自然在34前面】 动图演示： Java代码：

    public int[] sortArray(int[] nums) {
        List<Integer>[] buket = new List[10];
        for(int i = 0; i < 10; i++) buket[i] = new ArrayList<>();
        // 把负数全部转化成正数处理
        int max = nums[0] + 50000;
        //得到最大的数
        for(int t : nums) if(t + 50000 > max) max = t + 50000;
        
        //从个位到最高位
        int len = String.valueOf(max).length(); //最高位位数
        for(int i = 0; i < len; i++) {
            //入桶
            for(int t : nums) {
                buket[((t + 50000) / (int)Math.pow(10, i)) % 10].add(t + 50000);
            }
            //出桶
            int index = 0;
            for(int j = 0; j < 10; j++) {
                for(int k = 0; k < buket[j].size(); k++) {
                    nums[index++] = buket[j].get(k) - 50000;
                }
                buket[j].clear(); //清空桶
            }
        }
        return nums;
    }

对链表进行排序

如果你掌握了 插入排序、快速排序、归并排序的精髓，那么试试这三种方法对链表进行排序吧 狂刷三道力扣中等题： 力扣 147. 对链表进行插入排序力扣 148. 排序链表力扣 剑指 Offer II 077. 链表排序

1. 插入排序O(n2)

插入排序： 【有序】【无序】 无序部分找最小值放有序后头

直接上Java代码：

    public ListNode insertionSortList(ListNode head) {
        //由于链表只能从前往后遍历，所以只能从前往后遍历找插入位置
        //没有元素或者只有一个元素直接返回
        if(head == null || head.next == null) return head;
        ListNode dump = new ListNode();
        dump.next = head;
        ListNode lastNode = head;//有序节点的最后一个节点
        ListNode cur = head.next;
        while(cur != null) {
            if(cur.val >= lastNode.val) {
                //直接往后走
                lastNode = lastNode.next;
            }else {
                ListNode pre = dump;
                while(pre.next.val < cur.val) {
                   pre = pre.next;
                }
                //lastNode 不变，但是lastNode下一个数被插入前面了，
                lastNode.next = cur.next;
                cur.next = pre.next;
                pre.next = cur;
            }
            cur = lastNode.next;
        }
        lastNode.next = null;
        return dump.next;
    }

2.快速排序O(n log n)

快速排序： 【小数】【基准元素】【大数】，所有小数移动到基准元素左边，大数移动到基准元素右边

直接上Java代码： 对于力扣 148. 排序链表，快排超时了。

    public ListNode sortList(ListNode head) {
        if(head == null || head.next == null) return head;
        ListNode dump = new ListNode();
        dump.next = head;
        return quickSort(dump, null);
    }

    ListNode quickSort(ListNode headPre, ListNode end) {
        if(headPre == end || headPre.next == end || headPre.next.next == end) return headPre;
        //将小于基准值的节点存在这个临时链表中
        ListNode temDump = new ListNode();
        ListNode tp = temDump;
        //key 为基准节点，基准节点左边是比他小的，右边是比他大的
        ListNode key = headPre.next, lp = headPre;
        while(lp.next != end) {
            if(lp.next.val < key.val) {
            //节点值小于基准节点，就把这个节点放到左边
                tp.next = lp.next;
                tp = tp.next;
                lp.next = lp.next.next;
            }else {
                lp = lp.next;
            }
        }
        //合并大小两个链表
        tp.next = key;
        //整个链表用headPre连回来
        headPre.next = temDump.next; // 链表插回原链表（如果不做这一步，处理右半部分的时候就断了）
        quickSort(headPre, key);
        quickSort(key, end);

        return headPre.next;
    }

2.归并排序O(n log n)

链表排序最好就是用归并排序， 链表的归并排序不需要额外空间 归并，分治

归并排序需要不断的把链表分为两段，分为两段的方法可以用快慢指针，快指针溢出走两步，慢指针一次走一步，快指针走到头慢指针指向中间节点。

直接上Java代码：

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

    ListNode mergeSort(ListNode head) {
        if(head.next == null) return head;
        // 分
        //找中间节点
        ListNode fast = head, slow = head, pre = null;//pre 是slow节点的前一个节点
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            pre = slow;
            slow = slow.next;
        }
        pre.next = null; //断链， 现在head只有一半链表, slow 是另一半链表
        ListNode left = mergeSort(head); // 继续把head这一半进行分半
        ListNode right = mergeSort(slow); //继续把slow这一半进行分半

        //治
        //left、 right都是从最小（一个节点）回溯到最长（一半）
        //合并left、right
        ListNode dump = new ListNode();
        ListNode cur = dump;
        while(left != null && right != null) {
            if(left.val <= right.val) {
                cur.next = left;
                left = left.next;
                cur = cur.next;
            }else {
                cur.next = right;
                right = right.next;
                cur = cur.next;
            }
        }
        if(left != null) cur.next = left;
        if(right != null) cur.next = right;
        return dump.next;
    }
}