經典排序算法和JS實現案例分析

經典排序算法 冒泡排序 原理：

1.比較相鄰的元素，如果第一個比第二個大，就交換位置。
2.重復以上步驟，依次得出最大值，次大值。。。。
3.重復以上步驟，直到沒有任何一對數字需要比較

算法分析：

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

代碼實現：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); 選擇排序 原理：每趟從待排序的記錄中選出關鍵字最小的記錄，順序放到末尾，直到全部排序結束

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

算法分析：

1.時間復雜度：O(n2)
2.空間復雜度：O(1)