排序算法穩(wěn)定性
假定在待排序的記錄序列中类嗤，存在多個具有相同的關鍵字的記錄罕容，若經(jīng)過排序，這些記錄的相對次序保持不變，即在原序列中仇轻，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前辉川，則稱這種排序算法是穩(wěn)定的；否則稱為不穩(wěn)定的拴测。
Array.prototype.sort
js標準庫中的排序方法乓旗，可傳入一個函數(shù)自定義比較規(guī)則。流行的瀏覽器實現(xiàn)都是穩(wěn)定的排序算法集索。（例如chrome之前使用的是快排屿愚，在7.0版本之后換成了Timsort
）
關于Array.prototype.sort()詳細介紹見 MDN。
冒泡排序
最蠢的排序务荆。遍歷數(shù)組妆距，依次對比相鄰的兩個數(shù)，如果兩個數(shù)的順序錯誤則交換位置函匕。平均時間復雜度為 O（n2）娱据，穩(wěn)定排序。
function Bubble (arr){
if (!arr || !arr.length ) return arr;
for (let i = arr.length; i > 0; i--) {
for (let j = 1; j < i; j++) {
if (arr[j] < arr[j - 1]) {
const tem = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = tem;
}
}
}
return arr;
}
雞尾酒排序
冒泡排序改良版盅惜，又稱雙向冒泡排序中剩。在每一輪遍歷中，進行兩次冒泡抒寂。一次將最大值置于一端结啼，一次將最小值置于另一端。性能略為優(yōu)化蓬推，平均時間復雜度仍然是 O（n2）妆棒。穩(wěn)定排序。
function Cocktail(arr) {
if (!arr || !arr.length ) return arr;
for (let i = arr.length; i > 0; i--) {
for (let j = i - 1; j > 0; j--) {
if (arr[j] < arr[j - 1]) {
const tem = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = tem;
}
}
for (let j = arr.length - i + 1; j < i; j++) {
if (arr[j] < arr[j - 1]) {
const tem = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = tem;
}
}
}
return arr;
}
插入排序
類似打撲克將牌排序的手法沸伏，外層循環(huán)從第一個元素開始遍歷糕珊，內層循環(huán)將下一個元素與左側元素依次比較，插入到應處的位置毅糟。因為進行內層循環(huán)時红选，元素位置對的情況下無需繼續(xù)進行遍歷，所以效率比冒泡高很多姆另。特別是在數(shù)組大部分元素有序情況下效率很高喇肋。但在極端情況下依然需要進行完全遍歷，所以平均時間復雜度也還是O（n2）迹辐。穩(wěn)定排序蝶防。
function Insertion (arr){
for (let i = 0; i < arr.length; i++) {
for (let j = i + 1; j > 0; j--) {
if (arr[j] < arr[j - 1]) {
const tem = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = tem;
}else{
break;
}
}
}
return arr;
}
選擇排序
外層循環(huán)依次遍歷數(shù)組，內層循環(huán)遍歷未排序部分找出最小/大的元素與前面的元素交換明吩。與插入排序比較间学，選擇排序無需進行頻繁的元素交換動作，內層循環(huán)只是標記最小元素，遍歷完成后進行一次交換低葫。減少了交換的開銷详羡。但選擇排序無論如何都需要完全遍歷數(shù)組，在大部分有序情況下效率低于插入排序嘿悬。平均時間復雜度也還是O（n2）实柠。不穩(wěn)定排序。
class Selection(arr){
for (let i = 0; i < arr.length; i++) {
let min = arr[i];
let minIndex = i;
for (let j = i; j < arr.length; j++) {
if (arr[j] < min) {
min = arr[j];
minIndex = j;
}
}
if (minIndex != i) {
let tem = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = tem;
}
}
return arr;
}
希爾排序
to be continued
歸并排序
歸并排序一種基于分治法思路的排序善涨。通過將數(shù)組兩兩劃分窒盐，排序后再合并。平均時間復雜度為O(nlogn)躯概，需要申請空間進行合并操作登钥，空間復雜度為T(n)。是一種穩(wěn)定的排序算法娶靡。穩(wěn)定排序牧牢。
function Merge(arr) {
if (arr.length <= 1) {
return arr;
}
const mid = Math.floor(arr.length / 2);
const left = arr.slice(0, mid);
const right = arr.slice(mid);
return sort(Merge(left), Merge(right));
}
function sort(arrA, arrB) {
let i = 0;
let j = 0;
const arr = [];
while (arrA.length > 0 && arrB.length > 0) {
if (arrA[0] < arrB[0]) {
arr.push(arrA.shift());
} else {
arr.push(arrB.shift());
}
if (arrA.length == 0) {
arr = arr.concat(arrB);
} else if (arrB.length == 0) {
arr = arr.concat(arrA);
}
}
return arr;
}
快速排序
最快的排序算法。思路是先取一個基準值姿锭，然后雙指針遍歷數(shù)組塔鳍。右指針負責找到比基準值小的值，左指針負責找到比基準值大的值呻此，兩值交換轮纫。使得數(shù)組一邊是比基準值小的，一邊是比基準值大的焚鲜。然后再分別對這兩邊進行排序掌唾。平均時間復雜度為O(nlogn)，不穩(wěn)定排序忿磅∨幢颍快的原理是通過雙指針，使得每一輪循環(huán)可以使多個元素大致歸位葱她。
快排遞歸版本
function QuickSortRecursion(arr) {
partition(arr, 0, arr.length - 1);
return arr;
}
function partition(arr, start, end) {
if (arr.length <= 1 || start === end) {
return;
}
let left = start, right = end;
let key = arr[start];
while(left < right){
while(left < right && key <= arr[right]){//右指針往左走撩扒，尋找比基準值小的值
right--;
}
while(left < right && key >= arr[left]){//左指針向右走，尋找比基準值大的值
left++;
}
//交換元素
const tem = arr[right];
arr[right] = arr[left];
arr[left] = tem;
}
if(left == right && key > arr[right]){//如果指針所指比基準值小
arr[start] = arr[right];
arr[right] = key;
}
if(left - 1 > start){
partition(arr, start, left - 1);
}
if(right + 1 < end){
partition(arr, right + 1, end);
}
}
非遞歸版本
似乎遞歸的算法變不遞歸都是利用棧來解決的吨些。其實遞歸也就是函數(shù)調用棧搓谆，原理是完全一樣的。但函數(shù)調用棧里保存了每一個函數(shù)的執(zhí)行上下文豪墅，占用內存會比循環(huán)+棧的方式大得多泉手，當多重嵌套時會導致爆棧。改為循環(huán)+棧的形式可以處理更大的數(shù)組偶器。
function QuickSort(arr){
const stack = [];
let start = 0, end = arr.length - 1;
do {
let indexData = null;
if (stack.length != 0) {
let data = stack.pop();
start = data.start;
end = data.end;
}
indexData = this.partition(arr, start, end);
if (indexData != null) {
if (indexData - 1 > start) {
stack.push({ start: start, end: indexData - 1 });
}
if (indexData + 1 < end) {
stack.push({ start: indexData + 1, end: end });
}
}
} while (stack.length != 0);
return arr;
}
function partition(arr, start, end) {
if (arr.length <= 1 || start === end) {
return null;
}
let left = start, right = end;
let key = arr[start];
while(left < right){
while(left < right && key <= arr[right]){//右指針往左走螃诅，尋找比基準值小的值
right--;
}
while(left < right && key >= arr[left]){//左指針向右走啡氢，尋找比基準值大的值
left++;
}
const tem = arr[right];
arr[right] = arr[left];
arr[left] = tem;//交換元素
}
if(left == right && key > arr[right]){//如果指針所指比基準值小
arr[start] = arr[right];
arr[right] = key;
}
return left;
}
