冒泡排序

算法思想：通過一系列的“交換”動(dòng)作完成的，首先第一個(gè)記錄與第二個(gè)記錄比較，如果第一個(gè)大，則二者交換，否則不交換；然后第二個(gè)記錄和第三個(gè)記錄比較，如果第二個(gè)大，則二者交換，否則不交換，以此類推，最終最大的那個(gè)記錄被交換到了最后，一趟冒泡排序完成。在這個(gè)過程中，大的記錄就像一塊石頭一樣沉底，小的記錄逐漸向上浮動(dòng)。冒泡排序算法結(jié)束的條件是一趟排序沒有發(fā)生元素交換。

1. //冒泡排序 
2. Array.prototype.bubbleSort = function() { 
3.     for (var i = this.length - 1; i > 0; --i) 
4.     { 
5.         for (var j = 0; j < i; ++j) 
6.             if (this[j] > this[j + 1]) 
7.                 this.swap(j, j + 1); 
8.     } 
9. } 

算法性能：最內(nèi)層循環(huán)的元素交換操作是算法的基本操作。最壞情況，待排序列逆序，則基本操作的總執(zhí)行次數(shù)為(n-1+1)*(n-1)/2=n(n-1)/2，其時(shí)間復(fù)雜度為O(n*n)；最好情況，待排序列有序，則時(shí)間復(fù)雜度為O(n)，因此平均情況下的時(shí)間復(fù)雜度為O(n*n)。算法的額外輔助空間只有一個(gè)用于交換的temp，所以空間復(fù)雜度為O(1)。

快速排序

算法思想：以軍訓(xùn)排隊(duì)為例，教官說以第一個(gè)同學(xué)為中心，比他矮的站他左邊，比他高的站他右邊，這就是一趟快速排序。因此，一趟快速排序是以一個(gè)樞軸，將序列分成兩部分，樞軸的一邊比它小（或小于等于），另一邊比它大（或大于等于）。

1. //遞歸快速排序 
2. Array.prototype.quickSort = function(s, e) { 
3.     if (s == null) 
4.         s = 0; 
5.     if (e == null) 
6.         e = this.length - 1; 
7.     if (s >= e) 
8.         return; 
9.     this.swap((s + e) >> 1, e); 
10.     var index = s - 1; 
11.     for (var i = s; i <= e; ++i)   
12.         if (this[i] <= this[e]) this.swap(i, ++index); 
13.     this.quickSort(s, index - 1); 
14.     this.quickSort(index + 

     3/6   首頁 上一頁 1 2 3 4 5 6 下一頁 尾頁