97.排序数组
题目链接
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sort-an-array
题目描述
给定一个整数数组 nums，将该数组升序排列。
示例 1：
输入：[5,2,3,1]
输出：[1,2,3,5]
示例 2：
输入：[5,1,1,2,0,0]
输出：[0,0,1,1,2,5]
提示：
1 <= A.length <= 10000
-50000 <= A[i] <= 50000
关键技术
| 算法 | 稳定性 | 时间复杂度 | 空间复杂度 | 执行用时 | 内存消耗 |
| 自带sort排序 | × | n·log(n) | log(n) | 136ms | 42M |
| 冒泡排序 | √ | n² | 1 | 4988ms | 40.4M |
| 选择排序 | × | n² | 1 | 2220ms | 40.5M |
| 插入排序 | √ | n² | 1 | 888ms | 40.4M |
| 希尔排序 | × | n·log(n) | 1 | 116ms | 40.2M |
| 快速排序 | × | n·log(n) | log(n) | 200 ms | 54.1M |
题目分析
法一：sort 函数：v8中的sort()在10以内是插入排序，其余是快排。
/**
* @param {number[]} nums
* @return {number[]}
*/
var sortArray = function(nums) {
nums.sort((a,b)=>a-b);
return nums;
};
法二：冒泡排序：比较相邻的元素，从开始第一对比到结尾的最后一对，如果前一个比后一个大，交换位置。
/**
* @param {number[]} nums
* @return {number[]}
*/
//冒泡排序
var sortArray = function(nums) {
let n = nums.length;
if(n < 2){
return nums;
}
for(let i=0;i<n;i++){
for(let j=0;j<n-i-1;j++){
if(nums[j+1] < nums[j])
{
let temp = nums[j+1];
nums[j+1] = nums[j];
nums[j] = temp;
}
}
}
return nums;
};
法三：选择排序：从数组中选择最小的元素，将它与数组中第一个元素交换位置，再从数组剩下的元素中选择出最小的元素，与数组第二个位置交换顺序。
/**
* @param {number[]} nums
* @return {number[]}
*/
//选择排序
var sortArray = function(nums) {
let n = nums.length;
if(n < 2){
return nums;
}
for(let i=0;i<n;i++){
let min = i;
for(let j=i;j<n;j++){
if(nums[j] < nums[min])
{
min = j;
}
}
let temp = nums[min];
nums[min] = nums[i];
nums[i] = temp;
}
return nums;
};
法四：插入排序：每次都将当前元素插入到左侧已经排序的数组中，使得插入之后左侧数组依然有序。
/**
* @param {number[]} nums
* @return {number[]}
*/
//插入排序
var sortArray = function(nums) {
let n = nums.length;
if(n < 2){
return nums;
}
for(let i=1;i<n;i++){
let temp = nums[i];
let j = i-1; //默认已排序的元素
while(j>=0 && nums[j]>temp){ //在已排序好的队列中从后向前扫描
nums[j+1] = nums[j]; //已排序的元素大于新元素，将该元素移动到下一个位置
j--;
}
nums[j+1] = temp;
}
return nums;
};
法五：希尔排序：使用插入排序，对间隔h的序列进行排序。通过不断减小h，最后令h=1，就可以使得整个数组是有序的。
/**
* @param {number[]} nums
* @return {number[]}
*/
//希尔排序
var sortArray = function(nums) {
let n = nums.length;
if(n < 2){
return nums;
}
// 初始步数
let gap = parseInt(n/2);
// 逐渐缩小步数
while(gap){
// 从第gap个元素开始遍历
for(let i=gap;i<n;i++){
// 逐步和其前面其他的组成员进行比较和交换
for(let j=i-gap;j>=0;j-=gap){
if(nums[j] > nums[j+gap]){
[nums[j],nums[j+gap]] = [nums[j+gap],nums[j]];
}
else{
break;
}
}
}
gap = parseInt(gap/2);
}
return nums;
};
法六：快速排序：通过切分元素将数组分成两个子数组，左子数组<=切分元素，右子数组>=切分元素，将两个子数组排序，也就是将整个数组排序。
/**
* @param {number[]} nums
* @return {number[]}
*/
//快速排序
var sortArray = function(nums) {
//如果数组<=1,则直接返回
let n = nums.length;
if(n < 2){
return nums;
}
let centerIndex = parseInt(n/2);
//找基准，并把基准从原数组删除
let centerNum = nums.splice(centerIndex,1)[0];
//定义左右数组
let left = [];
let right = [];
//比基准小的放在left，比基准大的放在right
for(let i=0;i<nums.length;i++){
if(nums[i] <= centerNum){
left.push(nums[i]);
}else{
right.push(nums[i]);
}
}
//递归
return sortArray(left).concat([centerNum],sortArray(right));
};