[路飞]_leetcode-912-排序数组

「这是我参与11月更文挑战的第9天，活动详情查看：2021最后一次更文挑战」

[题目地址][B站地址]

给你一个整数数组 nums，请你将该数组升序排列。

示例 1：

输入： nums = [5,2,3,1]
输出： [1,2,3,5]
复制代码

示例 2：

输入： nums = [5,1,1,2,0,0]
输出： [0,0,1,1,2,5]
复制代码

提示：

1. 1 <= nums.length <= 50000
2. -50000 <= nums[i] <= 50000

本题很简单，就是要我们对数组 nums 做一个升序排序

关于常见的排序方法，我之前有一篇文章进行了总结，感兴趣的小伙伴可以去看下 《常用数组排序算法》，所以这里不再对各种排序的过程及实现做重复表述

对于本题，我分别采用了以下几种排序方式进行了提交，每一种排序算法的用时记录如下：

冒泡排序    8480ms
选择排序    2576ms
插入排序    6080ms
希尔排序     136ms
归并排序    4056ms
快速排序    2944ms
计数排序     132ms
Array.sort  136ms
复制代码

需要注意的是本题的快排要使用交换元素进行排序的快排算法，而通过基准值拆分左右数组的快排算法因为空间复杂度太高，会导致爆栈，无法通过提交

这里要说明的是以上用户记录只是当次提交的用时记录，leetcode每次提交的用时会受网络等原因影响有一些波动，例如 shellSort 以及 Array.sort 的提交的都是达到过 110ms 左右的

但是以上数据还是能充分说明哪些排序算法的用时会更优一些

用时最短的是 希尔排序、计数排序以及Array.sort

希尔排序通过对插入排序进行步长拆分的优化，使得插入排序的过程移动距离减小，从而达到高效的排序

计数排序通过下标数组记录原数组中元素的值以及该值出现的次数，然后通过遍历计数数组得到排序后的数组，因为该过程不涉及到比较大小，所以快于任何比较排序算法，时间复杂度为 复杂度为Ο(n+k)

Array.sort 查看 V8 源码可以看到当排序区间小于等于10的时候，会使用插入排序，反之会使用快速排序，而且它的快速排序肯定要比我文章中的快排进行了更多的优化，所以达到了如此高效的排序效率

v8 array.js InnerArraySort 710行

至此，我们就完成了 leetcode 912.排序数组

如有任何问题或建议，欢迎留言讨论！