JS排序算法--快排、归并、冒泡、选择、插入
1快速排序
时间复杂度-----最好 平均 O nlogn 最坏 O n2
稳定性：不稳定，因为元素的交换可能改变相同元素间的相对顺序
var sortArray = function(nums) {if (nums.length < 2) {return nums;}let mid = Math.floor(nums.length / 2); let pivot = nums[mid];let left = [];let right = [];for (let i = 0; i < nums.length; i++) {if (i === mid) continue; // 跳过中心元素if (nums[i] < pivot) {left.push(nums[i]);} else {right.push(nums[i]);}}return sortArray(left).concat(pivot, sortArray(right)); // 递归排序左右数组};
2归并排序
时间复杂度 都是O nlogn
稳定性：稳定，因为在合并时，如果遇到相等的元素，保持原有顺序
var sortArray = function(arr) {let len=arr.lengthif(len<2) return arrlet mid=Math.floor(len/2)let left=sortArray(arr.slice(0,mid))let right=sortArray(arr.slice(mid))return merge(left,right)
};
function merge(left,right){let i=0let j=0let res=[]while(i<left.length&&j<right.length){if(left[i]<right[j]){res.push(left[i])i++}else{res.push(right[j])j++}}return res.concat(left.slice(i)).concat(right.slice(j))
}
3冒泡排序
时间复杂度 最好O n 平均和最坏都是 O n2
稳定性：稳定，因为每次交换只涉及相邻元素，相同元素的顺序不会改变
var sortArray = function(arr) {let len=arr.lengthfor(let i=0;i<len-1;i++){for(let j=0;j<len-1;j++){if(arr[j]>arr[j+1]){//交换[arr[j],arr[j+1]]=[arr[j+1],arr[j]]}}}return arr
};
4选择排序
时间复杂度 都是O n2
稳定性：不稳定，因为在选择最小元素进行交换时，可能打破相同元素的相对顺序
function sortArray(arr){let len=arr.lengthfor(let i=0;i<len-1;i++){let minIndex=ifor(let j=i+1;j<len;j++){if(arr[j]<arr[minIndex]){minIndex=j}}if(minIndex!==i){[arr[i],arr[minIndex]]=[arr[minIndex],arr[i]]}}return arr
}
5插入排序
时间复杂度：最好O n 平均最坏 On2
稳定性：稳定，因为插入时，保持相同元素的顺序
function sortArray(arr){let len=arr.lengthfor(let i=1;i<len;i++){let key=arr[i]let j=i-1while(j>=0&&arr[j]>key){arr[j+1]=arr[j]j--}arr[j+1]=key}return arr
}