常用的 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²) |不稳定|
---------------------------------------------------------------