排序算法說(shuō)明:
（1）對(duì)于評(píng)述算法優(yōu)劣術(shù)語(yǔ)的說(shuō)明
穩(wěn)定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面；
不穩(wěn)定：如果a原本在b的前面，而a=b，排序之后a可能會(huì)出現(xiàn)在b的后面；
內(nèi)排序：所有排序操作都在內(nèi)存中完成；
外排序：由于數(shù)據(jù)太大，因此把數(shù)據(jù)放在磁盤中，而排序通過(guò)磁盤和內(nèi)存的數(shù)據(jù)傳輸才能進(jìn)行；
時(shí)間復(fù)雜度: 一個(gè)算法執(zhí)行所耗費(fèi)的時(shí)間。
空間復(fù)雜度: 運(yùn)行完一個(gè)程序所需內(nèi)存的大小。
(2)排序算法圖片總結(jié):
1..冒泡排序（Bubble Sort）
平均復(fù)雜度：o(n^2)? ? 空間復(fù)雜度：o(1)? ? 穩(wěn)定性：穩(wěn)定
冒泡排序是一種簡(jiǎn)單的排序算法。它重復(fù)地走訪過(guò)要排序的數(shù)列，一次比較兩個(gè)元素，如果它們的順序錯(cuò)誤就把它們交換過(guò)來(lái)。走訪數(shù)列的工作是重復(fù)地進(jìn)行直到?jīng)]有再需要交換，也就是說(shuō)該數(shù)列已經(jīng)排序完成。這個(gè)算法的名字由來(lái)是因?yàn)樵叫〉脑貢?huì)經(jīng)由交換慢慢“浮”到數(shù)列的頂端。
算法描述
? 比較相鄰的元素。如果第一個(gè)比第二個(gè)大，就交換它們兩個(gè)；
? 對(duì)每一對(duì)相鄰元素作同樣的工作，從開(kāi)始第一對(duì)到結(jié)尾的最后一對(duì)，這樣在最后的元素應(yīng)該會(huì)是最大的數(shù)；
? 針對(duì)所有的元素重復(fù)以上的步驟，除了最后一個(gè)；
? 重復(fù)步驟1~3，直到排序完成。
function bubbleSort(arr) {
? ? var len = arr.length;
? ? for (var i = 0; i < len - 1; i++) {
? ? ? ? for (var j = 0; j < len - 1 - i; j++) {
? ? ? ? ? ? if (arr[j] > arr[j+1]) {? ? ? // 相鄰元素兩兩對(duì)比
? ? ? ? ? ? ? ? var temp = arr[j+1];? ? ? // 元素交換
? ? ? ? ? ? ? ? arr[j+1] = arr[j];
? ? ? ? ? ? ? ? arr[j] = temp;
? ? ? ? ? ? }
? ? ? ? }
? ? }
? ? return arr;
}
2.選擇排序（Selection Sort）
【首先從原始數(shù)組中找到最小的元素，并把該元素放在數(shù)組的最前面，然后再?gòu)氖Ｏ碌脑刂袑ふ易钚〉脑?，放在之前最小元素的后面，知道排序完畢?！?/p>
? 平均復(fù)雜度：o(n^2)? ? 空間復(fù)雜度：o(1)? ? 穩(wěn)定性：不穩(wěn)定
選擇排序(Selection-sort)是一種簡(jiǎn)單直觀的排序算法。它的工作原理：首先在未排序序列中找到最?。ù螅┰兀娣诺脚判蛐蛄械钠鹗嘉恢?，然后，再?gòu)氖Ｓ辔磁判蛟刂欣^續(xù)尋找最?。ù螅┰?，然后放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。
算法描述
n個(gè)記錄的直接選擇排序可經(jīng)過(guò)n-1趟直接選擇排序得到有序結(jié)果。具體算法描述如下：
? 初始狀態(tài)：無(wú)序區(qū)為R[1..n]，有序區(qū)為空；
? 第i趟排序(i=1,2,3…n-1)開(kāi)始時(shí)，當(dāng)前有序區(qū)和無(wú)序區(qū)分別為R[1..i-1]和R(i..n）。該趟排序從當(dāng)前無(wú)序區(qū)中-選出關(guān)鍵字最小的記錄 R[k]，將它與無(wú)序區(qū)的第1個(gè)記錄R交換，使R[1..i]和R[i+1..n)分別變?yōu)橛涗泜€(gè)數(shù)增加1個(gè)的新有序區(qū)和記錄個(gè)數(shù)減少1個(gè)的新無(wú)序區(qū)；
? n-1趟結(jié)束，數(shù)組有序化了。
代碼實(shí)現(xiàn)
function selectionSort(arr) {
? ? var len = arr.length;
? ? var minIndex, temp;
? ? for (var i = 0; i < len - 1; i++) {
? ? ? ? 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;
}
3.插入排序（Insertion Sort）
平均復(fù)雜度：o(n^2)? ? 空間復(fù)雜度：o(1)? ? 穩(wěn)定性：穩(wěn)定
插入排序（Insertion-Sort）的算法描述是一種簡(jiǎn)單直觀的排序算法。它的工作原理是通過(guò)構(gòu)建有序序列，對(duì)于未排序數(shù)據(jù)，在已排序序列中從后向前掃描，找到相應(yīng)位置并插入。
算法描述
一般來(lái)說(shuō)，插入排序都采用in-place在數(shù)組上實(shí)現(xiàn)。具體算法描述如下：
? 從第一個(gè)元素開(kāi)始，該元素可以認(rèn)為已經(jīng)被排序；
? 取出下一個(gè)元素，在已經(jīng)排序的元素序列中從后向前掃描；
? 如果該元素（已排序）大于新元素，將該元素移到下一位置；
? 重復(fù)步驟3，直到找到已排序的元素小于或者等于新元素的位置；
? 將新元素插入到該位置后；
? 重復(fù)步驟2~5。
function insertionSort(arr) {
? ? var len = arr.length;
? ? var preIndex, current;
? ? for (var i = 1; i < len; i++) {
? ? ? ? preIndex = i - 1;
? ? ? ? current = arr[i];
? ? ? ? while (preIndex >= 0 && arr[preIndex] > current) {
? ? ? ? ? ? arr[preIndex + 1] = arr[preIndex];
? ? ? ? ? ? preIndex--;
? ? ? ? }
? ? ? ? arr[preIndex + 1] = current;
? ? }
? ? return arr;
}
4.快速排序
var quickSort = function(arr) {?
? if (arr.length <= 1) {return arr; }//判斷數(shù)組，一個(gè)長(zhǎng)度直接返回
? var pivotIndex = Math.floor(arr.length / 2);
? var pivot = arr.splice(pivotIndex, 1)[0];//找出基準(zhǔn)元素
? var left = [];?
? var right = [];? ?
? for (var i = 0; i < arr.length; i++){
//循環(huán)把元素分別放入左邊和右邊數(shù)組? ? ? ?
? if (arr[i] < pivot) {?
? ? left.push(arr[i]);? ?
? } else {? ?
? ? right.push(arr[i]);? ?
? }?
}? ?
return quickSort(left).concat([pivot], quickSort(right));
};
