冒泡排序

冒泡的原理是讓最大元素或者最小元素”浮起來“

插入排序，選擇排序，快速排序，冒泡排序都是比較排序

思路

依次比較相鄰的兩個數(shù)，將小數(shù)放在前面，大數(shù)放在后面。

step1：比較第1個和第2個數(shù)，將小數(shù)放前，大數(shù)放后。比較第2個數(shù)和第3個數(shù)，將小數(shù)放前，大數(shù)放后，如此繼續(xù)，直至比較最后兩個數(shù)，將小數(shù)放前，大數(shù)放后。
step2：在第二趟：仍從第一對數(shù)開始比較（因為可能由于第2個數(shù)和第3個數(shù)的交換，使得第1個數(shù)不再小于第2個數(shù)），將小數(shù)放前，大數(shù)放后，一直比較到倒數(shù)第二個數(shù)（倒數(shù)第一的位置上已經(jīng)是最大的），第二趟結束，在倒數(shù)第二的位置上得到一個新的最大數(shù)（其實在整個數(shù)列中是第二大的數(shù)）。
如此下去，重復以上過程，直至最終完成排序。
由于在排序過程中總是小數(shù)往前放，大數(shù)往后放，相當于氣泡往上升，所以稱作冒泡排序。
冒泡排序的動畫效果

實現(xiàn)：此段代碼比較簡單，是屬于算法里面最基礎最基礎最基礎的代碼。。。
要注意三點

1.交換類的方法在javascript中可以用 a=[b,b=a][0] 這個非常巧妙的方法來解決，
代替

這種交換方法
2.要注意循環(huán)變量的緩存，這里緩存了array.length
3.要注意內(nèi)嵌的那個循環(huán)，是從第一個數(shù)比較到倒數(shù)第n個數(shù)，n則為比較的step數(shù)

function bubbleSort(array) {
var l=array.length;
for (var i = 0; i < l; i++) {//比較的step數(shù)為數(shù)組的長度
for (var j = 0; j < l-i; j++) {//內(nèi)嵌交換的次數(shù)是從第一個數(shù)比較到倒數(shù)第總長-n個數(shù)，n則為比較的step數(shù)
if (array[j] < array[j - 1]) {
array[j] = [array[j - 1], array[j - 1] = array[j]][0]//在這里交換元素
}
}
for (var k = 0; k < l; k++) {
console.log(array[k] + ",");
}
console.log('這是第'+(i+1)+'次排序')
}
}
var a = [6,54,6,22,5,7,8,2,34];
bubbleSort(a);

動畫效果

插入排序（Insertion Sort）
非常簡單，就是我們摸牌插牌的步驟！
思路：

1首先假設我們摸了一張牌，我們手里目前所有牌設為empty = []摸了一張push(arr[0])
2取出下一個牌，設為a，在我們所有的牌empty(已經(jīng)排序)從后向前掃描
3如果手里這張牌empty[empty.length-n]（已排序）大于新元素，將該牌移到下一位置(騰空間)empty[empty.length-n]= empty[empty.length-n+1]
4重復步驟3，直到找到已排序的牌empty[empty.length-n]小于或者等于a
5將a插入到該位置中 empty[empty.length-n]=a
6重復步驟2
但是javascript代碼實現(xiàn)起來還是稍微有些難度的，代碼如下：

function insert(arr) {
var l = arr.length;
var empty = [];//空數(shù)組，表示我們的手
empty.push(arr[0]);//我們先摸起來一張
for (var i = 1; i < l; i++) {//注意這里起點是1，因為我們已經(jīng)摸了一張了！
if (arr[i] > empty[empty.length - 1]) {
empty[empty.length] = arr[i]
} //如果比有序數(shù)組empty還大，直接放到末尾
for (var j = empty.length; j > 0 && arr[i] < empty[j - 1]; j--) { //從最大值跟arr進行比較，為了給arr騰空。當arr<有序數(shù)組的某一位時，就不用移動了。
empty[j] = empty[j - 1]; //向右移動
empty[j - 1] = arr[i]; //把值放到空出來的位置上
}
//console.log(empty)
}
return empty
}

那么這里比較重要的知識點是&&符號，表示“與”，即兩邊的條件都要滿足，表達式才成立。
&&符號也可以代替if比如 if(a){fun()} 等于 a&&b
另外一點非常重要
設數(shù)組是arr，則他的“最后一項” 是arr[arr.length-1]。

排序動畫

選擇排序(Selection sort)
也是一種簡單的排序算法。

思路：

把最小元素找出來-扔到數(shù)組里-再找次小的-扔到數(shù)組里，以此類推。
首先在未排序數(shù)組中找到最小元素，找的方法可以利用不斷判斷并賦值的手段，即：設數(shù)組第一個元素array[0]為最小元素，那么“最小元素”在數(shù)組中的序號就為0
之后遍歷數(shù)組，若數(shù)組第二個元素比他還要小，那么說明第二個為最小元素，把“0” 更新為“1”。
遍歷完畢后，我們就知道這一系列的最小元素下標為“n”；直接拿出來存放到排序序列的起始位置(array[n])
然后，再從剩余未排序元素中繼續(xù)尋找最小元素，然后放到排序序列末尾。注意，此時遍歷的下標就從1開始了。因為我們已經(jīng)挑出了一個最小元素了。
以此類推，直到所有元素均排序完畢。

function selectSort(array) {
var min;
var l = array.length;//緩存長度
for (var i = 0; i < l; i++) {//開始進行循環(huán)，一共循環(huán)l次，就可以找出l個元素了
min = i;//假設第一個為最小元素
for (var j = i + 1; j < l; j++) {//從第一個開始循環(huán)，遍歷
if (array[min] > array[j])//判斷之后的是否比前面的小
min = j;//更新“最小”的下標
}
if (min != i) {//這里因為是在同一個數(shù)組內(nèi)進行操作，所以直接交換元素即可。比如數(shù)組第一項是i，那么我找出了最小元素為array[min],那么我就需要把這個min跟i交換。以此類推。
array[i]= [array[min],array[min]=array[i]][0];//交換元素
}
}
return array;
}

這里仍然注意的是交換的寫法 array[i]= [array[min],array[min]=array[i]][0]
可以方便的把array[i]與array[min]交換~

排序動畫

快速排序
 
快速排序是目前最強大的排序算法，算法利用了遞歸的思想。
 
思路

從數(shù)組中挑出一個元素，稱為 “基準”，這個可以直接利用length/2挑出來
遍歷數(shù)組，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的后面（相同的數(shù)可以到任一邊）。通俗來講：男的站左邊，女的站右邊。。
之后我們得到了一個這樣的數(shù)組 array= 比基準小的部分組成的數(shù)組lArray+基準+比基準大的部分組成的數(shù)組rArray。
那么我們之后只需要再把lArray,rArray進行“同樣的”處理即可~
這就需要用到 遞歸 的寫法了。處理之后，lArray又分成了 lArray的基準，比lArray基準還小的，比lArray基準還大的。。
那么我們不斷的進行操作，男的站左邊，女的站右邊。。
直到我們發(fā)現(xiàn)，lArray的長度變成1了，不足以再分下去了，我們認為排序結束。

function quickSort(arr) {
var l = arr.length;//緩存數(shù)組長度
if(arr.length <= 1){return arr}; //如果我們拿到的lArray,rArray長度比1都小，那就不用排了~
var num = Math.floor(arr.length / 2);//取數(shù)組中間的那個數(shù)。注意length/2不一定是整數(shù)，用Math.floor取整
var numValue = arr.splice(num, 1)[0];//利用splice方法，取一個元素出來，注意語法
var left = [];//創(chuàng)建左邊基準容器
var right = [];//創(chuàng)建右邊基準容器
for (var i = 0; i < l; i += 1) {//開始遍歷數(shù)組
arr[i] < numValue ? left.push(arr[i]) : right.push(arr[i]);//男的站左邊，女的站右邊。。
}
return quickSort(left).concat([numValue], quickSort(right))//遞歸，繼續(xù)對左右數(shù)組進行操作。
}

動畫效果：

這里注意 arr.splice(num,1)雖然只抽了一個數(shù)，但splice的結果也是數(shù)組，需要[0],要不然結果就會很奇葩的出現(xiàn)一堆array(1)的數(shù)組了。。。
splice的參考：http://www.dbjr.com.cn/w3school/js/jsref_splice.htm
Math.floor即Math對象的參考http://www.dbjr.com.cn/w3school/js/js_obj_math.htm
遞歸是什么：http://baike.baidu.com/view/96473.htm

以上四個算法除了快速排序，都是簡單排序算法，而這四個算法在面試中考的都非常頻繁~
在這里仍然要強調(diào)一點，以上的算法大量使用了循環(huán)及數(shù)組的相關知識，一定要背熟！

最新評論