长大后想做什么？做回小孩！

0%

LeetCode——排序数组

发表于 分类于 Valine：
本文字数： 2.4k

NO.912 排序数组 中等

趁这个机会整理一下常见的11种排序算法，都是些经典的基础的排序方法。

百度上一搜一大把通俗易懂的讲解加上精美的动图，不知道比我高出多少个台阶了。

GKlnGn.png

冒泡排序

每一轮从无序部分找到一个最大的元素放到数组无序部分的尾部。

1
2
3
4
5
6
7
8
9
10
public static void insertionSort(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        int curr = arr[i + 1], preIdx = i;
        while (preIdx >= 0 && arr[preIdx] > curr) {
            arr[preIdx + 1] = arr[preIdx];
            preIdx--;
        }
        arr[preIdx + 1] = curr;
    }
}

平均/最坏/最好时间复杂度：O(n^2) 无论如何都要嵌套循环跑一遍。

优化思路：可以加一个标志，如果已经有序就停止循环，可以将最好时间优化到O(n)

空间复杂度：O(1)

稳定

选择排序

每轮从无序部分选择出一个最小的元素放到数组有序部分的尾部。

1
2
3
4
5
6
7
8
9
10
11
12
public int[] sortArray(int[] nums) {
    for (int i = 0; i < nums.length; i++) {
        int minIdx=i;
        for (int j = i+1; j < nums.length; j++) {
            if (nums[minIdx]>nums[j])minIdx=j;
        }
        int temp=nums[i];
        nums[i]=nums[minIdx];
        nums[minIdx]=temp;
    }
    return nums;
}

平均/最坏/最好时间复杂度：O(n^2)
空间复杂度：O(1)
不稳定

插入排序

每个元素和自己前面的所有元素进行比较，比当前元素大的元素向后移动一个位置，最后找到一个”空位”将当前元素插入到这个”空位”里。

1
2
3
4
5
6
7
8
9
10
11
public int[] sortArray(int[] nums) {
    for (int i = 0; i < nums.length - 1; i++) {
        int curr=nums[i+1],preIdx=i;
        while (preIdx >= 0 && nums[preIdx] > curr) {
            nums[preIdx+1]=nums[preIdx];
            preIdx--;
        }
        nums[preIdx+1]=curr;
    }
    return nums;
}

平均/最坏时间复杂度：O(n^2)
最好时间复杂度：O(n) 初始有序的数组检查一遍，不需要进行插入换位置。
空间复杂度：O(1)
稳定

希尔排序

其实是插入排序的优化版本。一个里程碑意义的排序算法，因为它是冲破O(n^2)时间的第一批算法之一 。

和插入排序的区别在于希尔排序会将数据线按照增量进行分组，对每组使用插入排序；每轮增量分组排序之后增量逐渐减少，每组包含的元素也越来越少，当增量减至1的时候排序完成。而且希尔排序会优先比较每个增量分组里距离较远的元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int[] sortArray(int[] nums) {
    int gap=nums.length/2;
    while (gap > 0) {
        for (int i = 0; i < nums.length; i++) {
            int curr=nums[i],preIdx=i-gap;
            while (preIdx >= 0 && nums[preIdx] > curr) {
                nums[preIdx+gap]=nums[preIdx];
                preIdx-=gap;
            }
            nums[preIdx+gap]=curr;
        }
        gap/=2;
    }
    return nums;
}

平均/最坏/最好时间复杂度：O(nlogn) 亚二次时间运行
空间复杂度：O(1)
不稳定

归并排序

分治算法的思想，先将数据逐步进行折半分组，将每个最小分组有序化之后，再将每个分组逐步两两合并为新的有序分组，最终合并为完整的有序数据。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public int[] sortArray(int[] nums) {
    if (nums.length < 2) return nums;
    int mid = nums.length / 2;
    int[] left = Arrays.copyOfRange(nums, 0, mid);
    int[] right = Arrays.copyOfRange(nums, mid, nums.length);
    return merge(sortArray(left), sortArray(right));
}

private int[] merge(int[] left, int[] right) {
    int[] result = new int[left.length + right.length];
    for (int idx = 0, i = 0, j = 0; idx < result.length; idx++) {
        if (i >= left.length) {
            result[idx] = right[j++];
        } else if (j >= right.length) {
            result[idx] = left[i++];
        } else if (left[i] < right[j]) {
            result[idx] = left[i++];
        } else {
            result[idx] = right[j++];
        }
    }
    return result;
}

平均/最好/最坏时间复杂度：O(nlogn)
空间复杂度：O(n)
稳定

快速排序

每次选出一个哨兵(基准数)，将小于哨兵的元素都放到哨兵左边，大于哨兵的元素都放到哨兵右边，然后再将哨兵的左右部分分别递归进行这样的排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public int[] sortArray(int[] nums) {
    quickSort(nums, 0, nums.length - 1);
    return nums;
}

private void quickSort(int[] nums, int low, int high) {
    //递归结束条件low==right
    if (low < high) {
        int l = low, h = high, pivot = nums[low];
        while (l < h) {
            //逆序找到第一个小于temp的，放到l坑位
            while (l < h && nums[h] >= pivot) h--;
            if (l < h) {
                nums[l] = nums[h];
                l++;
            }
            //顺序找到第一个大于temp，放到r坑位
            while (l < h && nums[l] <= pivot) l++;
            if (l < h) {
                nums[h] = nums[l];
                h--;
            }
        }
        //基准数放到最终l==r的坑位
        nums[l] = pivot;
        //递归基准数左右部分
        quickSort(nums, low, l - 1);
        quickSort(nums, l + 1, high);
    }
}

平均/最好时间复杂度：O(nlogn) 每次分割对基准数排序O(n)，递归深度logn
最坏退化到：O(n^2) 数据初始就有序且完全逆序。
空间复杂度：O(logn)
不稳定

堆排序

堆是一个完全二叉树，并且每个结点的值都大于或等于其左右孩子结点的值（这里的讨论以大根堆为例），所以，堆是结点之间满足一定次序关系的完全二叉树。

利用大顶堆结构的性质，完成排序。

先将初始数据作为无序区将无序区构建成一个大顶堆，然后每次从堆顶抽取元素(最大值)放到尾部(有序区的首部)，再调整剩余堆(无序区)，再抽取堆顶放到有序区的首部，再调整堆。。。循此往复所有数据在有序区时(无序区为空)排序完成。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
//无序区的长度
int len;
public int[] sortArray(int[] nums) {
    this.len=nums.length;
    if (len<2)return nums;
    //构建大顶堆
    buidHeap(nums);
    //无序区还有元素
    while (len > 0) {
        //取堆顶元素放入有序区的首位
        swap(nums,0,len-1);
        //无序区减少一个元素
        len--;
        //重新调整为最大堆
        adjustHeap(nums,0);
    }
    return  nums;
}

private void buidHeap(int[] nums) {
    //从最后一个非叶子节点逐步向上构建大顶堆
    for (int i=len/2-1;i>=0;i--){
        adjustHeap(nums,i);
    }
}

private void adjustHeap(int[] nums, int i) {
    int maxIdx=i;
    //找到左右孩子中大于父节点的最大的元素的下标
    if (2*i+1<len&&nums[2*i+1]>nums[maxIdx]){
        maxIdx=2*i+1;
    }
    if (2*i+2<len&&nums[2*i+2]>nums[maxIdx]){
        maxIdx=2*i+2;
    }
    //如果父节点不是最大值，交换父节点和左右子树最大值的位置，并继续递归调整移动之后的父节点
    if (maxIdx != i) {
        swap(nums,i,maxIdx);
        adjustHeap(nums,maxIdx);
    }
}

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

平均/最坏/最好时间复杂度：O(nlogn)

空间复杂度：O(1)

不稳定

二叉搜索树排序

在二叉搜索树中，每个结点的值均大于其左子树上所有结点的值，小于其右子树上所有结点的值，对二叉排序树进行中序遍历得到一个有序序列。所以，二叉排序树是结点之间满足一定次序关系的二叉树。

二叉树搜索排序用数组内的所有元素构建一个搜索二叉树，然后用中序遍历重新将所有的元素填充回原来的数组中。因为搜索二叉树不能用数组来表示，所以必须使用额外的数据结构来构建二叉树。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
public int[] sortArray(int[] nums) {
    //构建根节点
    TreeNode root=new TreeNode(nums[0]);
    //构建二叉搜索树
    for (int i = 1; i < nums.length; i++) {
        buildBST(root,nums[i]);
    }
    //中序遍历,保存到nums中
    //这里必须是传一个引用，不能是普通类型的int。
    //不然在触底返回的时候因为的作用域的问题，普通类型int的变量值不能继续正确递增。
    inorderTraversal(root,nums,new int[1]);
    return nums;
}

private void inorderTraversal(TreeNode root, int[] nums, int[] idx) {
    if (root==null)return;
    inorderTraversal(root.left,nums,idx);
    nums[idx[0]++]=root.val;
    inorderTraversal(root.right,nums,idx);
}

private void buildBST(TreeNode root, int num) {
    if (root==null)return;
    if (num >= root.val) {//大于父节点插入右子树
        if (root.right == null) {
            root.right=new TreeNode(num);
        }else {
            buildBST(root.right,num);
        }
    }else {//小于父节点插入左子树
        if (root.left == null) {
            root.left=new TreeNode(num);
        }else {
            buildBST(root.left,num);
        }
    }
}

平均/最好时间复杂度：O(nlogn)

最坏时间复杂度：O(n^2)

空间复杂度：O(n)

稳定

计数排序

前面都是基于比较的排序，从这里开始就是非比较型排序。

tips：计数排序适合数据有明确的范围，且范围不是特别巨大的情况。而且计数排序适合数据在键值上排列比较稠密的情况，如果比较稀疏的话更适合使用基数排序。

计数排序的过程是创建一个长度为数组中最小和最大元素之差的数组，分别对应数组中的每个元素，然后用这个新的数组来统计每个元素出现的频率，然后遍历新的数组，根据每个元素出现的频率把元素放回到老的数组中，得到已经排好序的数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public int[] sortArray(int[] nums) {
    //找到最大值最小值
    int min=Integer.MAX_VALUE,max=Integer.MIN_VALUE;
    for (int e : nums) {
        min=Math.min(e,min);
        max=Math.max(e,max);
    }
    //计算出最小值关于原点的偏移量，min为负偏移量记为正数，min为正偏移量记为负数
    int bias=0-min;
    //计数器
    int[] counter=new int[max-min+1];
    //计数
    for (int e : nums) {
        counter[e+bias]++;
    }
    //取出计数器中的数字，按序重新放回
    int nums_idx=0,counter_idx=0;
    while (nums_idx < nums.length) {
        if (counter[counter_idx] != 0) {
            counter[counter_idx]--;
            nums[nums_idx++]=counter_idx-bias;
        }else {
            counter_idx++;
        }
    }
    return nums;
}

平均/最好/最坏时间复杂度：O(n+k) n是arr长度，k是范围
空间复杂度：O(k)
稳定

桶排序

“桶”很形象的命名，所谓”桶”就是提前制定好的一个规则，将符合规则的数据元素放入对应的”桶”中。其实这里很像计数排序，计数排序中每个桶是一个key，把符合key的元素计入其中。

首先新建一个桶的数组，每个桶的规则需要提前制定好，比如元素在0~9为一个桶、10~19为一个桶。然后遍历整个待排序的数组，把元素分配到对应的桶里面。接下来单独对每个桶里面的元素进行排序，桶内的排序算法可以选择比较排序或者非比较排序，得到排序后的数组。最后把所有的桶内的元素还原到原数组里面得到最后的排序数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public int[] sortArray(int[] nums) {
    //定义一个桶的大小
    int SIZE = 100;
    //找到最大最小值,即元素范围
    int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
    for (int e : nums) {
        min = Math.min(min, e);
        max = Math.max(max, e);
    }
    int bias = 0-min;
    int span = max - min + 1;
    //计算桶的数量
    int bucketNum = (span % SIZE == 0) ? (span / SIZE) : (span / SIZE + 1);
    //遍历将元素放入对应的桶中
    List<Integer>[] buckets=new List[bucketNum];
    for (int e : nums) {
        int idx=(e+bias)/SIZE;
        if (buckets[idx]==null)buckets[idx]=new ArrayList<>();
        buckets[idx].add(e);
    }
    //将每个桶中的元素进行排序后放入nums
    int idx=0;
    for (List<Integer> bucket : buckets) {
        if (bucket != null) {
            bucket.sort(null);//默认升序,内部是TimSort
            //排序后放回nums
            for (Integer e : bucket) {
                nums[idx++]=e;
            }
        }
    }
    return nums;
}

桶排序可以看做是一种特殊的计数排序，只是桶的规则不同，所以不单单是记录数量了。

平均/最好时间复杂度:O(n+k) 同样受到数据范围的影响。

最坏时间复杂度：取决于桶内的排序算法，例如采用了快排，那么最坏就是O(n^2)。

空间复杂度：O(n+k)

稳定(取决于桶内的排序规则)

基数排序

基数排序是规则不同的桶排序，基数排序也是把元素送入对应的桶中，不过规则是根据所有数字的某一位上面的数字来分类。

基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
public int[] sortArray(int[] nums) {
    // 计算最大最小数
    int max = -1,min = 1;
    for (int num : nums) {
        max = Math.max(max, num);
        min = Math.min(min, num);
    }
    // 求得绝对值最大的数
    max = Math.max(max, -min);
    // 计算绝对值最大的数的位数
    int digits = 0;
    while (max > 0) {
        max /= 10;
        digits++;
    }
    // 建一个包含所有位数的数组
    List<Integer>[] buckets = new List[19];
    for (int i = 0; i < buckets.length; i++) {
        buckets[i] = new ArrayList<>();
    }
    // 对十进制每一位进行基数排序
    int pos,cur;
    for (int i = 0, mod = 1; i < digits; i++, mod*=10) {
        // 扫描数组将值放入对应的桶
        for (int num : nums) {
            pos = (num / mod) % 10;
            buckets[pos+9].add(num);
        }
        // 将桶内元素放回到数组里面
        cur = 0;
        for (List<Integer> bucket : buckets) {
            if (bucket!=null) {
                for (Integer integer : bucket) {
                    nums[cur++] = integer;
                }
                // 将桶清空
                bucket.clear();
            }
        }
    }
    return nums;
}

平均/最坏/最好时间复杂度：O(n*k/d) k是key的总数量，d是最大十进制数的位数
空间复杂度：O(n+2^d)
稳定

除了上述的十一种排序之外，还有很多牛逼的排序，例如TimSort应用于Python默认排序API、Java中的Collections.sort()。

还有一些比较搞怪有趣的排序，例如 睡眠排序：对于nums，创建n个线程，每个线程sleep(nums[i])秒，然后线程醒过来的时候报数。这样就可以排序了、猴子排序(BogoSort)：随机打乱nums中的元素，直至数组有序，名副其实的欧皇排序法。

等等。。。

本人菜鸟，有错误请告知，感激不尽！

更多题解和源码:github