第JavaScript實(shí)現(xiàn)基礎(chǔ)排序算法的示例詳解目錄前言正文1、冒泡排序2、選擇排序3、插入排序4、快速排序

前言

文本來(lái)總結(jié)常見的排序算法，通過(guò)JvavScript來(lái)實(shí)現(xiàn)

正文

1、冒泡排序

算法思想：比較相鄰兩個(gè)元素的大小，如果第一個(gè)比第二個(gè)大，就交換它們。從頭遍歷到尾部，當(dāng)一輪遍歷完后，數(shù)組最后一個(gè)元素是最大的。除去最后一個(gè)元素，對(duì)剩下的元素重復(fù)執(zhí)行上面的流程，每次找出剩余元素中最大的，遍歷完后，數(shù)組是升序的

算法分析：總共需要進(jìn)行l(wèi)ength*(length-1)/2次比較，所以時(shí)間復(fù)雜度為O(n^2)，因?yàn)橹恍枰幸粋€(gè)存放常量的空間，元素本身在原數(shù)組上進(jìn)行交換，所以空間復(fù)雜度為O(1)

functionbubbleSort(array){

if(!Array.isArray(array)){

thrownewError('參數(shù)必須為數(shù)組');

return;

varn=0,m=0//n表示趟數(shù),m表示比較次數(shù)

for(leti=array.length-1;ii--){//外層for表示遍歷的趟數(shù)

for(letj=0;jj++){//內(nèi)層for表示每趟需要比較的j和j+1對(duì)應(yīng)的數(shù)

if(arr[j]arr[j+1]){

[arr[j+1],arr[j]]=[arr[j],arr[j+1]]

console.log("遍歷趟數(shù)"+n,"比較次數(shù)"+m);//遍歷趟數(shù)8比較次數(shù)36

returnarray

vararr=[7,3,6,9,24,0,1,45,8]

console.log(bubbleSort(arr));//[0,1,3,6,7,8,9,24,45]

我們?cè)诿恳惠喲h(huán)中，可以記住最后一次交換的元素，這之后的元素就肯定是已經(jīng)排完序的，這樣可以減少總的循環(huán)次數(shù)

functionbubbleSort2(array){

if(!Array.isArray(array)){

thrownewError('參數(shù)必須為數(shù)組');

return;

varn=0,m=0//n表示趟數(shù),m表示比較次數(shù)

for(vari=array.length-1;i){//用來(lái)表示遍歷n-1趟

varcursor=0;//用來(lái)記錄本輪最后一次交換的元素位置

for(varj=0;jj++){

if(array[j]array[j+1]){

cursor=j;

[arr[j+1],arr[j]]=[arr[j],arr[j+1]]

i=cursor;

console.log("遍歷趟數(shù)"+n,"比較次數(shù)"+m);//遍歷趟數(shù)6比較次數(shù)29

returnarray

vararr=[7,3,6,9,24,0,1,45,8]

console.log(bubbleSort2(arr));//[0,1,3,6,7,8,9,24,45]

2、選擇排序

實(shí)現(xiàn)思路

（1）從頭遍歷到尾部，找出所有項(xiàng)中最大的一個(gè)元素

（2）將這個(gè)元素和第一個(gè)元素交換

（3）對(duì)剩下的元素重復(fù)進(jìn)行上面的操作，每次找出剩余中最大的最后的數(shù)組是降序排列的

（4）算法分析

總共需要進(jìn)行l(wèi)ength*(length-1)/2次比較，所以時(shí)間復(fù)雜度為O(n^2)，因?yàn)橹恍枰袃蓚€(gè)存放常量的空間，元素本身在原數(shù)組上進(jìn)行交換，所以空間復(fù)雜度為O(1)

functionselectSort(array){

if(!Array.isArray(array)){

thrownewError('參數(shù)必須為數(shù)組');

return;

for(leti=0;iarray.length;i++){

varmaxIndex=i,maxValue=array[i]//設(shè)置i為最大元素下標(biāo)

//找出剩下元素中的最大值,第一次循環(huán)找出最大值

for(letj=i+1;jarray.length;j++){

if(array[j]maxValue){

maxIndex=j

maxValue=array[j]

//如果剩下的元素中最大值下標(biāo)大于i則發(fā)生交換

if(maxIndexi){

[array[i],array[maxIndex]]=[array[maxIndex],array[i]]

returnarray

vararr=[7,3,6,9,24,0,1,45,8]

console.log(selectSort(arr));//[45,24,9,8,7,6,3,1,0]

3、插入排序

實(shí)現(xiàn)思路

（1）將數(shù)組前面部分看做有序數(shù)組

（2）每次將后面部分的第一個(gè)與已排序數(shù)組作比較，插入到合適的位置

（3）有序數(shù)組初始狀態(tài)有1個(gè)數(shù)字

（4）算法分析

（5）時(shí)間復(fù)雜度為O(n^2)

functioninsertSort(array){

if(!Array.isArray(array)){

thrownewError('參數(shù)必須為數(shù)組');

return;

for(vari=1;iarray.length;i++){

vartemp=array[i]//當(dāng)前值

for(varj=i;j0temparray[j-1];j--){

//當(dāng)前值和之前的每個(gè)值進(jìn)行比較，發(fā)現(xiàn)有比當(dāng)前值小的值就進(jìn)行重新賦值

array[j]=array[j-1];

array[j]=temp;

returnarray;

vararr=[7,3,6,9,24,0,1,45,8]

console.log(insertSort(arr));//[45,24,9,8,7,6,3,1,0]

4、快速排序

算法思想：將數(shù)組的第一個(gè)數(shù)字作為基準(zhǔn)，最后使得基準(zhǔn)數(shù)字位于數(shù)組中間某個(gè)位置，它的左邊的數(shù)字都比它小，它的右邊的數(shù)字都比它大。

算法實(shí)現(xiàn)：設(shè)置兩個(gè)分別指向數(shù)組頭部和尾部的指針i和j，首先向左移動(dòng)j，使得array[j]小于基準(zhǔn)。然后向右移動(dòng)i，使得array[i]大于基準(zhǔn)，交換這兩個(gè)元素。當(dāng)i和j的值相等時(shí)，交換基準(zhǔn)與位置i上的元素，然后對(duì)i左邊以及右邊的元素分別進(jìn)行快速排序。

functionquickSort(array){

constsort=function(arr,left=0,right=arr.length-1){

if(left=right){//遞歸退出條件

return

leti=left,j=right//定義兩個(gè)指針

letpivot=arr[i]//定義基準(zhǔn)數(shù)據(jù)

while(ij){//把所有比基準(zhǔn)數(shù)

while(jiarr[j]=pivot){//找到一個(gè)比基準(zhǔn)值小的數(shù)位置為j

arr[i]=arr[j]//將j的值給了i位置的元素，此時(shí)j位置還是原來(lái)的數(shù)

while(ijarr[i]pivot){

arr[j]=arr[i]//將i位置的值給了j位置的元素，此時(shí)i的位置還是原來(lái)的數(shù)

//本次交換完畢，此時(shí)ij兩個(gè)指針重合,把基準(zhǔn)值賦值給i即可

arr[i]=pivot

sort(arr,left,j-1)//將左邊的無(wú)序數(shù)組重復(fù)上面的操作

sort(arr,j+1,right)//將右邊的無(wú)序數(shù)組重復(fù)上面的操作

co