常用的 JS 排序算法 整理版
1.冒泡排序
varbubbleSort=function(arr){
for(vari=0,len=arr.length;iarr[j]){
vartemp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
}
}
returnarr;
};
2.选择排序
varselectSort=function(arr){
varmin;
for(vari=0;iarr[j]){
min=j;
}
}
if(i!=min){
swap(arr,i,min);
}
console.log(i+1,":"+arr);
}
returnarr;
};
functionswap(arr,index1,index2){
vartemp=arr[index1];
arr[index1]=arr[index2];
arr[index2]=temp;
};
3.插入排序
varinsertSort=function(arr){
varlen=arr.length,
key;
for(vari=1;i-1){
if(arr[j]>key){
arr[j+1]=arr[j];
}else{
break;
}
}
arr[j+1]=key;
}
returnarr;
};
4.希尔排序
functionshellSort(arr){
if(arr.length<2){
returnarr;
};
varn=arr.length;
for(gap=Math.floor(n/2);gap>0;gap=Math.floor(gap/=2)){
for(i=gap;i=0&&arr[j+gap]
5.归并排序
functionmerge(left,right){
varresult=[];
while(left.length>0&&right.length>0){
if(left[0]
6.快速排序
varquickSort=function(arr){
if(arr.length<=1){
returnarr;
}
varpivotIndex=Math.floor(arr.length/2);
varpivot=arr.splice(pivotIndex,1)[0];
varleft=[];
varright=[];
for(vari=0;i
算法效率比较
---------------------------------------------------------------
|排序算法|平均情况 |最好情况 |最坏情况 |稳定性|
---------------------------------------------------------------
|冒泡排序| O(n²) | O(n) | O(n²) |稳定 |
---------------------------------------------------------------
|选择排序| O(n²) | O(n²) | O(n²) |不稳定|
---------------------------------------------------------------
|插入排序| O(n²) | O(n) | O(n²) |稳定 |
---------------------------------------------------------------
|希尔排序| O(nlogn)~O(n²)| O(n^1.5)| O(n²) |不稳定|
---------------------------------------------------------------
|归并排序| O(nlogn) | O(nlogn)| O(nlogn)|稳定 |
---------------------------------------------------------------
|快速排序| O(nlogn) | O(nlogn)| O(n²) |不稳定|
---------------------------------------------------------------