1.背景介紹
雖然排序算法是一個簡單的問題，但是從計算機科學發(fā)展以來聪蘸，在此問題上已經(jīng)有大量的研究宪肖。 更多的新算法仍在不斷的被發(fā)明表制。
2.知識剖析
查找和排序算法是算法的入門知識，其經(jīng)典思想可以用于很多算法當中控乾。因為其實現(xiàn)代碼較短么介，應用較常見。 所以在面試中經(jīng)常會問到排序算法及其相關的問題蜕衡。但萬變不離其宗壤短，只要熟悉了思想，靈活運用也不是難事慨仿。 一般在面試中最尘酶考的是快速排序和歸并排序，并且經(jīng)常有面試官要求現(xiàn)場寫出這兩種排序的代碼镰吆。 對這兩種排序的代碼一定要信手拈來才行帘撰。還有插入排序、冒泡排序万皿、堆排序摧找、基數(shù)排序、桶排序等牢硅。
3.常見問題
問題:如何用JavaScript 如何實現(xiàn)?
4.解決方案
冒泡排序
冒泡排序是一種簡單的排序算法蹬耘。它重復地走訪過要排序的數(shù)列，一次比較兩個元素减余， 如果他們的順序錯誤就把他們交換過來综苔。走訪數(shù)列的工作是重復地進行直到?jīng)]有元素再需要交換， 也就是說該數(shù)列已經(jīng)排序完成位岔。
冒泡排序
var examplearr=[8,94,15,88,55,76,21,39];
function sortarr(arr){
for(i=0;i
for(j=0;j
if(arr[j]>arr[j+1]){
var temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
}
}
return arr;
}
sortarr(examplearr);
console.log(examplearr);
冒泡排序
基本思路：1.依次比較相鄰的兩個數(shù)捉撮，如果第一個比第二個小怕品，不變。如果第一個比第二個大巾遭，調(diào)換順序肉康。一輪下來闯估，最后一個是最大的數(shù)
2.對除了最后一個之外的數(shù)重復第一步，直到只剩一個數(shù)
選擇排序（Selection sort）是一種簡單直觀的排序算法吼和。它的工作原理如下涨薪。 首先在未排序序列中找到最小（大）元素炫乓，存放到排序序列的起始位置刚夺，然后，再從剩余未排序元素中繼續(xù)尋找最心┑贰（大）元素侠姑， 然后放到已排序序列的末尾。以此類推箩做，直到所有元素均排序完畢莽红。
選擇排序的思想其實和冒泡排序有點類似，都是在一次排序后把最小的元素放到最前面卒茬。但是過程不同船老， 冒泡排序是通過相鄰的比較和交換咖熟。而選擇排序是通過對整體的選擇圃酵。
選擇排序
Array.prototype.selectionSort = function() {
var i, j, min;
var temp;
for (i = 0; i < this.length - 1; i++) {
min = i;
for (j = i + 1; j < this.length; j++)
if (this[min] > this[j])
min = j;
temp = this[min];
this[min] = this[i];
this[i] = temp;
}
return this;
};
var num = [22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70]; //定義一個數(shù)組
num.selectionSort(); //數(shù)組定義選擇排序算法
選擇排序
1.找出最小的數(shù)，和第一個交換位置
2.在剩下的數(shù)中馍管，找出最二小的數(shù)郭赐，放在第二個
3.依次類推，排出順序
插入排序也是一個簡單直觀的排序算法确沸。它的 工作原理是通過構建有序序列捌锭，對于未排序數(shù)據(jù)， 在已排序序列中從后向前掃描罗捎，找到相應位置并插入观谦。插入排序在實現(xiàn)上，通常采用in-place排序 （即只需用到O(1)的額外空間的排序）桨菜，因而在從后向前掃描過程中豁状，需要反復把已排序元素逐步向后挪位， 為最新元素提供插入空間倒得。
插入排序
Array.prototype.insertionSort = function () {
for (var i = 1; i < this.length; i++) {
var temp = this[i];
var j = i - 1;
//如果將賦值放到下一行的for循環(huán)內(nèi), 會導致在第13行出現(xiàn)j未聲明的錯誤
for (; j >= 0 && this[j] > temp; j--) {
this[j + 1] = this[j];
}
this[j + 1] = temp;
}
return this;
}
var num = [22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70]; //定義一個數(shù)組
num.insertionSort(); //數(shù)組調(diào)用插入排序算法
插入排序
基本思路：1.把數(shù)組分為[已排序]和[未排序]兩部分,第一個數(shù)為[已排序]谊路，其余為[未排序]
2.從[未排序]抽出第一個數(shù)，和[已排序]部分比較菩彬，插入到合適的位置
快速排序
步驟為：
遞歸到最底部時轻黑，數(shù)列的大小是零或一糊肤，也就是已經(jīng)排序好了。這個演算法一定會結(jié)束氓鄙，因為在每次的迭代（iteration）中馆揉，它至少會把一個元素擺到它最后的位置去。
Array.prototype.quickSort = function() {
var len = this.length;
if (len <= 1)
return this.slice(0);
var left = [];
var right = [];
var mid = [this[0]];
for (var i = 1; i < len; i++)
if (this[i] < mid[0])
left.push(this[i]);
else
right.push(this[i]);
return left.quickSort().concat(mid.concat(right.quickSort()));
};
var arr = [5, 3, 7, 4, 1, 9, 8, 6, 2];
arr = arr.quickSort();
快速排序
1.以一個數(shù)為基準(中間的數(shù))抖拦，比基準小的放到左邊升酣，比基準大的放到右邊
2.再按此方法對這兩部分數(shù)據(jù)分別進行快速排序（遞歸進行
3.不能再分后退出遞歸，并重新將數(shù)組合并
5.編碼實戰(zhàn)
6.擴展思考
如何評價算法的好壞
正確性
算法能滿足具體問題的需求态罪，即對任何合法的輸入算法都會得出正確的結(jié)果噩茄。
可讀性
算法創(chuàng)建后由人來閱讀、理解复颈、使用以及修改绩聘。所以可讀性的好壞直接影響到算法的好壞。如果一個算法涉及的想法很多耗啦，就會給閱讀的人造成困難凿菩，那么這個算法就不能得到更好的交流和推廣，更不便于對算法進行修改帜讲、擴展和維護衅谷。所以要提高算法的可讀性，就要做到簡明易懂似将。
健壯性
一個程序完成后获黔，運行該程序的用戶對程序的理解各有不同，并不能保證每一個人都能按照要求進行輸入玩郊，健壯性就是指對非法輸入的抵抗能力肢执，當輸入的數(shù)據(jù)非法時，算法能識別并做出處理译红，而不會因為輸入的錯誤產(chǎn)生錯誤動作或造成癱瘓
時間復雜度與空間復雜度
時間復雜度簡單地說就是算法運行所需要的時間预茄。不同的算法具有不同的時間復雜度，當一個程序較小時感覺不到時間復雜度的重要性，當一個程序特別大時便會察覺到時間復雜度的重要性耻陕。所以如何寫出更高速的算法一直是算法不斷改進的目標拙徽。空間復雜度是指算法運行所需的存儲空間诗宣，隨著計算機硬件的發(fā)展膘怕，空間復雜度已經(jīng)顯得不再那么重要
7.參考文獻
參考二：常見排序算法之JavaScript實現(xiàn)
參考一：JavaScript 排序算法匯總
