排序算法

桶排序，冒泡排序，快速排序原理

桶排序（计数排序）

新建一个数组（最大值+1位） [0，最大值]，初始都为0
是几就，第几个数加1：array[t]++
最后遍历数组，有几个就输出几遍

时间复杂度为 O(M+N)
空间浪费，但如果数字量大到和所有整数个数差不多时（42亿以上个），就不会浪费了

• int 2^32个 = 42亿多点。
  42亿 * 4字节(Byte) ~ 170Byte ~ 16G
• • 若只判断有没有，0/1， 每个分一个位 （1Byte=8Bit=2^3Bit）
    2^32 Bit = 2^29 Byte = 521M
    （BitMap思想）

冒泡排序

1. 两两比较，直到把最后一个归位
2. 然后再两两比较，直到把倒数第二个归位
3. 直到最后一次，前两个比较，分别归位

时间复杂度为 O(N2)

public class Math {
    public static void main(String[] args) {
        int[] nums = new int[]{5, 8, 6, 4, 1};
        bubbleSort(nums);
    }
    public static void bubbleSort(int[] nums) {
        int size = nums.length;
        for (int i = 0; i < size - 1; i++) {  //一个个冒泡
            for (int j = 0; j < size - 1 - i; j++) {  //冒好i个 少i个
                if (nums[j] > nums[j + 1]) {
                    int n = nums[j];
                    nums[j] = nums[j + 1];
                    nums[j + 1] = n;
                }
            }
        }
    }
}

5 8 6 4 1 
5 6 8 4 1 
5 6 4 8 1 
5 6 4 1 8  //最大8归位
--         //排 5 6 4 1
5 6 4 1 8 
5 4 6 1 8 
5 4 1 6 8  //6归位
--         //排 5 4 1
4 5 1 6 8 
4 1 5 6 8  //5归位
--         //排 4 1 
1 4 5 6 8 

快速排序

1. 以第一个数为参考，两边向中间巡查，小的放左边，大的放右边，参考值放两个相遇的中间（参考值归位）
2. 以参考值为中心，分为两组，分别递归进行第1步，直到最后一个归位

平均时间复杂度为 O(NlogN)
最坏仍是相邻交换，则复杂度与冒泡相同为O(N2)

public class Math {
    public static void main(String[] args) {
        int[] nums = new int[]{5, 9, 3, 2, 8, 6, 4, 1};
        quickSort(nums, 0, nums.length-1);
    }

    static void quickSort(int[] nums, int start, int end) {
        if (start < end) {
            int middle = getMiddle(nums, start, end); //将numbers数组进行一分为二
            quickSort(nums, start, middle - 1);    //分别对两部分递归排序
            quickSort(nums, middle + 1, end); 
        }
    }

    public static int getMiddle(int[] nums, int start, int end) {
        int ref = nums[start]; //数组的第一个作为中轴
        while (start < end) {
            while (start < end && nums[end] >= ref) {
                end--;
            }
            nums[start] = nums[end];//比中轴小的记录移到低端
            while (start < end && nums[start] < ref) {
                start++;
            }
            nums[end] = nums[start]; //比中轴大的记录移到高端
        }
        nums[start] = ref; //中轴记录到尾
        return start; // 返回中轴的位置
    }
}

5 9 3 2 8 6 4 1 //1->5
--
1 9 3 2 8 6 4 1 //9->1
1 9 3 2 8 6 4 9 //4->9
1 4 3 2 8 6 8 9 //8->4
1 4 3 2 5 6 8 9 //5->8
---
1 2 3 2 5 6 8 9 //2->4
1 2 3 4 5 6 8 9 //4->2

归并排序

1. 先拆分成两半，一直分到一个或两个
2. 然后合并，合并时，小的在前大的在后，合并后替换原来的
3. 一直合并完成

时间复杂度O(NlogN)

public class Math {
    public static void main(String[] args) {
        int[] nums = {50, 10, 90, 30, 70, 40, 80, 60, 20};
        mergeSort(nums, 0, nums.length - 1);
    }

    public static void mergeSort(int[] nums, int start, int end) {
        int mid = (start + end) / 2;
        if (start < end) {
            mergeSort(nums, start, mid); //左边递归拆分
            mergeSort(nums, mid + 1, end); //右边递归拆分
            merge(nums, start, mid, end); //层层合并
        }
    }
    public static void merge(int[] nums, int start, int mid, int end) {
        int[] sorted = new int[end - start + 1];
        int k = 0;
        int i = start;
        int j = mid + 1;
        while (i <= mid && j <= end) {
            if (nums[i] <= nums[j]) {
                sorted[k++] = nums[i++];
            } else {
                sorted[k++] = nums[j++];
            }
        }
        while (i <= mid) {
            sorted[k++] = nums[i++];
        }
        while (j <= end) {
            sorted[k++] = nums[j++];
        }
        for (int k2 = 0; k2 < sorted.length; k2++) {
            nums[start + k2] = sorted[k2];
        }
    }
}

50 10 90 30 70 40 80 60 20 
----
10 50  90  30 70   40  80  60  20  
10 50  90  30 70   40  80  60  20 
10 50 90   30 70   40  80  60  20 
10 30 50 70 90    40  80  60  20 
10 30 50 70 90   40 80   60 20 
10 30 50 70 90   40 80   20 60 
10 30 50 70 90   20 40 60 80 
10 20 30 40 50 60 70 80 90

各种排序算法复杂度及稳定性：

• 稳定性
  原数组：2 1 3 5 3
  稳定的前一个3一定在前，后一个3一定在后
  不稳定的不一定谁前谁后
• 稳定排序应用场景：有两个排序关键字的时候，稳定排序可以让第一个关键字排序的结果服务于第二个关键字排序中数值相等的那些数。

ps: 看图，请到 https://blog.csdn.net/XSF50717/article/details/47318123