經(jīng)典排序算法和JS實(shí)現(xiàn)案例分析

經(jīng)典排序算法 冒泡排序 原理：

1.比較相鄰的元素，如果第一個(gè)比第二個(gè)大，就交換位置。
2.重復(fù)以上步驟，依次得出最大值，次大值。。。。
3.重復(fù)以上步驟，直到?jīng)]有任何一對(duì)數(shù)字需要比較

算法分析：

1.若文件的初始狀態(tài)是正序，一趟掃描完成排序。所需要的關(guān)鍵字的比較次數(shù)C和記錄移動(dòng)的次數(shù)M達(dá)到最小值：Cmin=n-1,Mmin=0,故冒泡排序的時(shí)間復(fù)雜度O(n);
2.若初始文件是反序的，需要進(jìn)行n-1趟排序。每趟排序要進(jìn)行n-i(1<=i<=n-1)次關(guān)鍵字的比較，且每次比較都必須移動(dòng)記錄3次（比如交換a[i-1]和a[i];tmp=a[i-1];a[i-1]=a[i];a[i]=tmp）來達(dá)到交換記錄的位置。此時(shí)，比較和移動(dòng)次數(shù)都達(dá)到最大值:Cmax=n*(n-1)/2=O(n2);Mmax=3n*(n-1)/2=O(n2), (根據(jù)等差數(shù)列求得) 故冒泡排序的最壞的時(shí)間復(fù)雜度是O(n2)。
綜上兩點(diǎn)，冒泡排序總的平均時(shí)間復(fù)雜度為O(n2);
總結(jié)：平均時(shí)間復(fù)雜度：O(n2)， 穩(wěn)定度：穩(wěn)定， 空間復(fù)雜度：O(1)

代碼實(shí)現(xiàn)：vararr=[1,5,3,2];functionbubbleSort(arr){for(leti=0,l=arr.length;ifor(letj=i+1;jif(arr[i]>arr[j]){lettemp=arr[i]; arr[i]=arr[j]; arr[j]=temp; } } }returnarr; } bubbleSort(arr); 選擇排序 原理：每趟從待排序的記錄中選出關(guān)鍵字最小的記錄，順序放到末尾，直到全部排序結(jié)束

1.從待排序中，找到最小的元素
2.如果最小元素不在排序序列的第一個(gè)元素，和第一個(gè)元素進(jìn)行交換
3.從剩下的n-1個(gè)元素中，找出最小的元素，重復(fù)1,2步驟

算法分析：

1.時(shí)間復(fù)雜度：O(n2)
2.空間復(fù)雜度：O(1)