排序算法可以分為內(nèi)部排序和外部排序，內(nèi)部排序是數(shù)據(jù)記錄在內(nèi)存中進行排序，而外部排序是因排序的數(shù)據(jù)很大菜枷，一次不能容納全部的排序記錄称鳞，在排序過程中需要訪問外存涮较。常見的內(nèi)部排序算法有：插入排序、希爾排序冈止、選擇排序狂票、冒泡排序、歸并排序熙暴、快速排序闺属、堆排序慌盯、基數(shù)排序等。用一張圖概括：
冒泡排序
冒泡排序（Bubble Sort）也是一種簡單直觀的排序算法掂器。它重復地走訪過要排序的數(shù)列亚皂，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來国瓮。走訪數(shù)列的工作是重復地進行直到?jīng)]有再需要交換灭必，也就是說該數(shù)列已經(jīng)排序完成。這個算法的名字由來是因為越小的元素會經(jīng)由交換慢慢“浮”到數(shù)列的頂端乃摹。
算法步驟
1禁漓、比較相鄰的元素。如果第一個比第二個大孵睬，就交換他們兩個播歼。
2、對每一對相鄰元素作同樣的工作掰读，從開始第一對到結尾的最后一對秘狞。這步做完后，最后的元素會是最大的數(shù)磷支。
3谒撼、針對所有的元素重復以上的步驟，除了最后一個雾狈。
4廓潜、持續(xù)每次對越來越少的元素重復上面的步驟，直到?jīng)]有任何一對數(shù)字需要比較善榛。
var arr = [9,1,5,23,-1,2,14,6];
console.log(arr);
bubbleSort(arr);
console.log(arr);
function bubbleSort(arr) {
var len = arr.length;
for (var i = 0; i < len - 1; i++) {
/* debugger*/
for (var j = 0; j < len - 1 - i; j++) {
if (arr[j] > arr[j+1]) { // 相鄰元素兩兩對比
var temp = arr[j+1]; // 元素交換
arr[j+1] = arr[j];
arr[j] = temp;
}
}
}
return arr;
}
//上面的冒泡排序最好的情況（數(shù)據(jù)排列正序）也是O(n^2)的時間復雜度
//可以改進一下辩蛋，加一個flag判斷，如果已經(jīng)排好序了移盆，就退出循環(huán)
function bubbleSort(arr) {
var len = arr.length;
var flag;
for (var i = 0; i < len - 1; i++) {
/* debugger*/
flag = false;
for (var j = 0; j < len - 1 - i; j++) {
if (arr[j] > arr[j+1]) { // 相鄰元素兩兩對比
var temp = arr[j+1]; // 元素交換
arr[j+1] = arr[j];
arr[j] = temp;
flag = true; //有變動悼院，則變更flag
}
}
if(flag === false) return arr;
}
return arr;
}
選擇排序
選擇排序是一種簡單直觀的排序算法，無論什么數(shù)據(jù)進去都是 O(n2) 的時間復雜度咒循。所以用到它的時候据途，數(shù)據(jù)規(guī)模越小越好。唯一的好處可能就是不占用額外的內(nèi)存空間了吧叙甸。
算法步驟
1颖医、首先在未排序序列中找到最小（大）元素裆蒸，存放到排序序列的起始位置
2熔萧、再從剩余未排序元素中繼續(xù)尋找最小（大）元素，然后放到已排序序列的末尾佛致。
3贮缕、重復第二步，直到所有元素均排序完畢俺榆。
function selectionSort(arr) {
var len = arr.length;
var minIndex, temp;
for (var i = 0; i < len - 1; i++) {
/*debugger*/
minIndex = i;
for (var j = i + 1; j < len; j++) {
if (arr[j] < arr[minIndex]) { // 尋找最小的數(shù)
minIndex = j; // 將最小數(shù)的索引保存
}
}
temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
return arr;
}
插入排序
插入排序的代碼實現(xiàn)雖然沒有冒泡排序和選擇排序那么簡單粗暴感昼，但它的原理應該是最容易理解的了，因為只要打過撲克牌的人都應該能夠秒懂肋演。插入排序是一種最簡單直觀的排序算法抑诸，它的工作原理是通過構建有序序列烂琴，對于未排序數(shù)據(jù)爹殊，在已排序序列中從后向前掃描，找到相應位置并插入奸绷。
??插入排序和冒泡排序一樣梗夸，也有一種優(yōu)化算法，叫做拆半插入号醉。拆半插入排序所需要的輔助空間和直接插入排序相同反症，從時間上比較，折半插入排序僅減少了關鍵字間的比較次數(shù)畔派，而記錄的移動次數(shù)不變铅碍。它可以更快的確定第i個元素的插入位置。會快一些线椰，但時間復雜度仍為O(n^2)
算法步驟
1胞谈、將第一待排序序列第一個元素看做一個有序序列，把第二個元素到最后一個元素當成是未排序序列憨愉。
2烦绳、從頭到尾依次掃描未排序序列，將掃描到的每個元素插入有序序列的適當位置配紫。（如果待插入的元素與有序序列中的某個元素相等径密，則將待插入元素插入到相等元素的后面。）
function insertionSort(arr) {
var len = arr.length;
var preIndex, current;
for (var i = 1; i < len; i++) {
//debugger
preIndex = i - 1;
current = arr[i];
while(preIndex >= 0 && arr[preIndex] > current) {
arr[preIndex+1] = arr[preIndex];
preIndex--;
}
arr[preIndex+1] = current;
}
return arr;
}
希爾排序
希爾排序躺孝，也稱遞減增量排序算法享扔，是插入排序的一種更高效的改進版本。但希爾排序是非穩(wěn)定排序算法植袍。
??希爾排序是基于插入排序的以下兩點性質(zhì)而提出改進方法的：
??插入排序在對幾乎已經(jīng)排好序的數(shù)據(jù)操作時惧眠，效率高，即可以達到線性排序的效率奋单；
??但插入排序一般來說是低效的锉试，因為插入排序每次只能將數(shù)據(jù)移動一位；
??希爾排序的基本思想是：先將整個待排序的記錄序列分割成為若干子序列分別進行直接插入排序，待整個序列中的記錄“基本有序”時呆盖，再對全體記錄進行依次直接插入排序拖云。
算法步驟
1、選擇一個增量序列 t1应又，t2宙项，……，tk株扛，其中 ti > tj, tk = 1尤筐；
2、按增量序列個數(shù) k洞就，對序列進行 k 趟排序盆繁；
3、每趟排序旬蟋，根據(jù)對應的增量 ti油昂，將待排序列分割成若干長度為 m 的子序列，分別對各子表進行直接插入排序倾贰。僅增量因子為 1 時冕碟，整個序列作為一個表來處理，表長度即為整個序列的長度匆浙。
function shellSort(arr) {
var len = arr.length,
temp,
gap = 1;
//debugger
while(gap < len/3) { //動態(tài)定義間隔序列
gap =gap*3+1;
}
for (gap; gap > 0; gap = Math.floor(gap/3)) {
for (var i = gap; i < len; i++) {
temp = arr[i];
for (var j = i-gap; j >= 0 && arr[j] > temp; j-=gap) {
arr[j+gap] = arr[j];
}
arr[j+gap] = temp;
}
}
return arr;
}
//換一個增量因子值
function shellSort(array) {
function swap(array, i, k) {
var temp = array[i];
array[i] = array[k];
array[k] = temp;
}
var length = array.length,
gap = Math.floor(length / 2);
while (gap > 0) {
for (var i = gap; i < length; i++) {
for (var j = i; 0 < j; j -= gap) {
if (array[j - gap] > array[j]) {
swap(array, j - gap, j);
} else {
break;
}
}
}
gap = Math.floor(gap / 2);
}
return array;
}
歸并排序
歸并排序（Merge sort）是建立在歸并操作上的一種有效的排序算法安寺。該算法是采用分治法（Divide and Conquer）的一個非常典型的應用。
??作為一種典型的分而治之思想的算法應用首尼，歸并排序的實現(xiàn)由兩種方法：
??自上而下的遞歸（所有遞歸的方法都可以用迭代重寫挑庶，所以就有了第 2 種方法）；
??自下而上的迭代饰恕；
算法步驟
1挠羔、申請空間，使其大小為兩個已經(jīng)排序序列之和埋嵌，該空間用來存放合并后的序列破加；
2、設定兩個指針雹嗦，最初位置分別為兩個已經(jīng)排序序列的起始位置范舀；
3、比較兩個指針所指向的元素了罪，選擇相對小的元素放入到合并空間锭环，并移動指針到下一位置；
4泊藕、重復步驟 3 直到某一指針達到序列尾辅辩；
5、將另一序列剩下的所有元素直接復制到合并序列尾。
function mergeSort(arr) { // 采用自上而下的遞歸方法
var len = arr.length;
if(len < 2) {
return arr;
}
debugger
var middle = Math.floor(len / 2),
left = arr.slice(0, middle),
right = arr.slice(middle);
return merge(mergeSort(left), mergeSort(right));
}
function merge(left, right)
{
var result = [];
while (left.length && right.length) {
if (left[0] <= right[0]) {
result.push(left.shift());
} else {
result.push(right.shift());
}
}
while (left.length)
result.push(left.shift());
while (right.length)
result.push(right.shift());
return result;
}
快速排序
快速排序是由東尼·霍爾所發(fā)展的一種排序算法玫锋。在平均狀況下蛾茉，排序 n 個項目要 Ο(nlogn) 次比較。在最壞狀況下則需要 Ο(n2) 次比較撩鹿，但這種狀況并不常見谦炬。事實上，快速排序通常明顯比其他 Ο(nlogn) 算法更快节沦，因為它的內(nèi)部循環(huán)（inner loop）可以在大部分的架構上很有效率地被實現(xiàn)出來键思。
??快速排序使用分治法（Divide and conquer）策略來把一個串行（list）分為兩個子串行（sub-lists）。
??快速排序又是一種分而治之思想在排序算法上的典型應用甫贯。本質(zhì)上來看吼鳞，??快速排序應該算是在冒泡排序基礎上的遞歸分治法。
??快速排序的名字起的是簡單粗暴获搏，因為一聽到這個名字你就知道它存在的意義赖条，就是快失乾，而且效率高常熙！它是處理大數(shù)據(jù)最快的排序算法之一了。雖然 Worst Case 的時間復雜度達到了 O(n2)碱茁，但是人家就是優(yōu)秀裸卫，在大多數(shù)情況下都比平均時間復雜度為 O(n logn) 的排序算法表現(xiàn)要更好。
??快速排序的最壞運行情況是 O(n2)纽竣，比如說順序數(shù)列的快排墓贿。但它的平攤期望時間是 O(nlogn)，且 O(nlogn) 記號中隱含的常數(shù)因子很小蜓氨，比復雜度穩(wěn)定等于 O(nlogn) 的歸并排序要小很多聋袋。所以，對絕大多數(shù)順序性較弱的隨機數(shù)列而言穴吹，快速排序總是優(yōu)于歸并排序幽勒。
算法步驟
1、從數(shù)列中挑出一個元素港令，稱為 “基準”（pivot）;
2啥容、重新排序數(shù)列，所有元素比基準值小的擺放在基準前面顷霹，所有元素比基準值大的擺在基準的后面（相同的數(shù)可以到任一邊）咪惠。在這個分區(qū)退出之后，該基準就處于數(shù)列的中間位置淋淀。這個稱為分區(qū)（partition）操作遥昧；
遞歸地（recursive）把小于基準值元素的子數(shù)列和大于基準值元素的子數(shù)列排序；
3、遞歸的最底部情形炭臭，是數(shù)列的大小是零或一叫乌，也就是永遠都已經(jīng)被排序好了。雖然一直遞歸下去徽缚，但是這個算法總會退出憨奸，因為在每次的迭代（iteration）中，它至少會把一個元素擺到它最后的位置去凿试。
var arr = [9,1,5,23,-1,2,14,6];
console.log(arr);
quick_sort(arr,0,arr.length-1);
console.log(arr);
//兩個指針交替走排宰，
//邏輯上是緩存left值，右邊指針往左走那婉，直到找到比緩存值更小的數(shù)板甘，交換兩個指針當前位置的值。
//然后左邊指針往右走详炬，直到找到比緩存值更大的數(shù),交換兩個指針當前位置的值盐类。
//再輪到右邊指針往左走。呛谜。在跳。
//重復上面步驟，直到指針相遇隐岛，相遇的位置就是緩存值應該放的位置猫妙。
//因為左邊的數(shù)比緩存值小，右邊數(shù)比緩存值大聚凹。
function quick_sort(s, left, right)
{
//debugger
if (left < right)
{
var i = left,
j = right,
temp= s[left]; //保存的是左邊的值割坠，要從右邊開始找
//否則找到兩個指針相遇時會丟失一個數(shù)
while (i < j)
{
while(i < j && s[j] >=temp){
// 從右向左找第一個小于x的數(shù)，不小于就跳過（j--）
//找到數(shù)據(jù)就交換位置
j--;
}
s[i] = s[j];
while(i < j && s[i] < temp) {
// 從左向右找第一個大于等于x的數(shù)
i++;
}
s[j] = s[i];
}
s[i] = temp;
//上面執(zhí)行完后妒牙，i位置的數(shù)的位置就是對的了彼哼，
//因為前面的數(shù)比s[i]小，后面的數(shù)比s[i]大
//下面對i兩邊的數(shù)據(jù)遞歸處理
quick_sort(s, left, i - 1);
quick_sort(s, i + 1, right);
}
}
堆排序
待補充
計數(shù)排序
待補充
桶排序
待補充
基數(shù)排序
待補充
轉(zhuǎn)載自十大經(jīng)典排序算法
注：
算法的穩(wěn)定性：
??通俗地講就是能保證排序前兩個相等的數(shù)據(jù)其在序列中的先后位置順序與排序后它們兩個先后位置順序相同湘今。
??再簡單具體一點敢朱，如果A i == A j，Ai 原來在 Aj 位置前象浑，排序后 Ai 仍然是在 Aj 位置前蔫饰。
穩(wěn)定性的好處：
（1）如果排序算法是穩(wěn)定的，那么從一個鍵上排序愉豺，然后再從另一個鍵上排序篓吁，第一個鍵排序的結果可以為第二個鍵排序所利用。
基數(shù)排序就是這樣蚪拦，先按低位排序杖剪，逐次按高位排序冻押，那么，低位相同的數(shù)據(jù)元素其先后位置順序即使在高位也相同時是不會改變的盛嘿。
（2）學習排序原理時洛巢，可能編的程序里面要排序的元素都是簡單類型，實際上真正應用時次兆，可能是對一個復雜類型（自定義類型）的數(shù)組排序稿茉，
而排序的鍵值僅僅只是這個元素中的一個屬性，對于一個簡單類型芥炭，數(shù)字值就是其全部意義漓库，即使交換了也看不出什么不同。
??但是园蝠，對于復雜類型渺蒿，交換的話可能就會使原本不應該交換的元素交換了。比如：一個“學生”數(shù)組彪薛，欲按照年齡排序茂装，“學生”這個對象不僅含有“年齡”，還有其它很多屬性善延。
??假使原數(shù)組是把學號作為主鍵由小到大進行的數(shù)據(jù)整理少态。而穩(wěn)定的排序會保證比較時，如果兩個學生年齡相同挚冤，一定不會交換况增。
??那也就意味著盡管是對“年齡”進行了排序，但是學號順序仍然是由小到大的要求训挡。
