前端开发中常见排序算法
冒泡排序
思路： 从索引0开始 依次和下一个元素比较，如果前面元素大于后面的（升序）就交换位置。循环完成后比较下一轮。
优化：添加一个标志位，如果单轮循环中没有发生位置交换，就说明已经是有序的，则排序结束。可以
将时间复杂度 在最佳状态时降低到O(n)(本身就是一个有序数组)
时间复杂度：O(n) 至 O(n^2)
代码实现
let arr = [30, 32, 6, 24, 37, 32, 45, 21, 38, 23, 47],conut=0;
/**
* 冒泡排序
* @param {*} arr
*/
function bubbleSort(arr){
for(let i=0;i<arr.length;i++)
{
let hasSrap=false; // 没有发生过交换的标识
for(let j=0;j<arr.length-i;j++)
{
if(arr[j]>arr[j+1])
{
//交换元素位置
[arr[j],arr[j+1]]= [arr[j+1],arr[j]];
//发生过交换
hasSrap=true;
}
conut++;
}
//如果没有发生过交换
if(!hasSrap)
{
return arr;
}
}
return arr;
}
console.log(bubbleSort(arr)); //[ 6, 21, 23, 24, 30, 32, 32, 37, 38, 45, 47 ]
console.log(`循环次数：${conut}`) //60
选择排序
思路:：循环数组中的每一项，依次遍历后面的元素，选出后面元素与之相比最小的和当前元素交换位置
时间复杂度: O(n^2)
代码实现：
//选择排序
let arr = [30, 32, 6, 24, 37, 32, 45, 21, 38, 23, 47],conut=0;
function selectedSort(arr){
for(let i=0;i<arr.length;i++)
{
let n=i+1,index=i;
while(n<arr.length){
//依次找 取得比 当前被比较元素最小的索引
if(arr[index]>arr[n])
{
index=n;
}
n++;
conut++;
}
//交换位置
[arr[i],arr[index]]=[arr[index],arr[i]];
}
return arr;
}
console.log(selectedSort(arr)); //[ 6, 21, 23, 24, 30, 32, 32, 37, 38, 45, 47 ]
console.log(`循环次数：${conut}`) //55
插入排序
思路：循环元素，比较当前元素 找到某一位置与被比较元素小，和比该位置元素后一位大的，然后插入。
例如：[1,2,5,4,5,32]:循环到 索引3，值为 4的位置。 4与5比较，小于 ，5后移，此时数组 为【1,2,5,5】，
然后接着比较 2与4比较 小于4，则不需要继续插入了。插入 为【1,2,4，5,32】
复杂度： O(n^2)
let arr = [30, 32, 6, 24, 37, 32, 45, 21, 38, 23, 47],conut=0;
function insertSort(arr){
for(let i=0;i<arr.length;i++)
{
let j=i-1, //需要比较元素的前一个索引
value=arr[i], //当前需要比较的值
flag=true; //是否需要再次遍历
while(flag && j>=0)
{
//如果 大于需要比较的元素
if(arr[j]>value)
{
//该元素后移
arr[j+1]=arr[j]
j--;
}
else{
//此时表示前后没有交换了，说明之前已经是有序数组，不需要再遍历
flag=false;
}
conut++;
}
//将比较的元素插入至索引
arr[j+1]=value;
}
return arr;
}
console.log(insertSort(arr));
console.log(`循环次数：${conut}`) //28
快速排序
思路：根据一个基数，然后将比基数小的值放在基数的左边，将比基数大的值放在基数的右边，之后进行递归那两组已经归类好的数组。
时间复杂度：O(nlogn)
/**
* 快速排序
*
* @param {*} arr
*/
function quickSort(arr){
if(arr.length<2)
{
return arr;
}
//小于当前元素的放在左边，大于的放在右边数组
let left=[],right=[],temp=arr[0];
for(let i=1;i<arr.length;i++)
{
if(arr[i]<temp)
{
left.push(arr[i])
}
else{
right.push(arr[i])
}
conut++;
}
//递归
return quickSort(left).concat([temp],quickSort(right))
}
console.log(quickSort(arr));
console.log(`循环次数：${conut}`)
归并排序
思路：递归分割数组，然后比较两个数组互相比较。比较时候的数组内部是有序的，依次比较，最后比较的数组长度越来越大。
不好描述也不容易理解，看以下例子的描述。
//直到两个数组 有一个被取空
// [3,9,10] [2,6,7,8]
//第一轮 3和 2比较 2小 从右边数组 取出 result=[2] L [3,4,5] R Z中 [6,7,8]
// 3 和6 比较 左小 左边数组 出对列 result=[2,3] L:[9,10] R:[6,7,8]
// 9 和 6 比较 右小 右边数组出对列 result=[2,3,6] L:[9,10] R:[7,8]
// 9 和 7 比较 右小 右边数组出对列 result=[2,3,6,7] L:[9,10] R:[8]
// 9 和 8 比较 右小 右边数组出对列 result=[2,3,6,7,8] L:[9,10] R:[]
// 比较结束
// result 和剩余元素合并
时间复杂度：O(nlogn)
let arr = [30, 32, 6, 24, 37, 32, 45, 21, 38, 23, 47],conut=0;
function mergeSort(unsorted) {
function merge(leftArr, rightArr) {
let result = [];
//直到两个数组 有一个被取空
// [3,9,10] [2,6,7,8]
//第一轮 3和 2比较 2小 从右边数组 取出 result=[2] L [3,4,5] R Z中 [6,7,8]
// 3 和6 比较 左小 左边数组 出对列 result=[2,3] L:[9,10] R:[6,7,8]
// 9 和 6 比较 右小 右边数组出对列 result=[2,3,6] L:[9,10] R:[7,8]
// 9 和 7 比较 右小 右边数组出对列 result=[2,3,6,7] L:[9,10] R:[8]
// 9 和 8 比较 右小 右边数组出对列 result=[2,3,6,7,8] L:[9,10] R:[]
// 比较结束
// result 和剩余元素合并
while(leftArr.length>0 && rightArr.length>0)
{
if(leftArr[0]<rightArr[0])
{
result.push(leftArr.shift());
}
else{
result.push(rightArr.shift());
}
}
//合并剩余元素
leftArr &&(result=result.concat(leftArr));
rightArr&&(result= result.concat(rightArr)) ;
return result;
}
//分割数组，然后依次比较
function split(array) {
const len = array.length;
if (len <= 1) {
return array;
}
//依次取中值
const mid = Math.floor(len / 2);
const leftArr = array.slice(0, mid);
const rightArr = array.slice(mid, len);
//分割元素 不断递归比较
return merge( split(leftArr), split(rightArr) );
}
return split(unsorted);
}
console.log(mergeSort(arr))
