排序算法是將一列數(shù)據(jù)按照從小到大仍源，或從大到小的順序有序排列童本；更準(zhǔn)確地說，是按照某個(gè)關(guān)鍵字進(jìn)行排序
冒泡排序（Bubble Sort）
思想：兩個(gè)相鄰的元素進(jìn)行比較几颜，若要求數(shù)據(jù)從小到大排列倍试，如果前一個(gè)元素大于后一個(gè)元素則兩者交換位置，反之不變
假設(shè)現(xiàn)在有一組數(shù)據(jù)[3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]蛋哭，對(duì)其排序县习，從小到大
排序過程：
JavaScript 代碼如下：
var arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
// 冒泡排序
function sort(arr){
for(var i = 0; i < arr.length - 1; i++){
var changeFlag = false;
for(var j = 0; j < arr.length - i - 1; j++){
if(arr[j] > arr[j+1]){
swap(j, j+1, arr);
changeFlag = true;
}
}
if(!changeFlag){
break;
}
}
return arr;
}
function swap(a, b, arr){
var temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
console.log(sort(arr));
排序結(jié)果：
選擇排序
思想：首先將第1位數(shù)與它右邊的所有數(shù)比較，得到最芯咦场（大）的數(shù)就放在第1位准颓；接下來將第2位數(shù)與它右邊的所有數(shù)比較，得到最泄准恕（大）的數(shù)就放在第1位......以此類推攘已，當(dāng)?shù)趎-1位數(shù)與第n位數(shù)比較好之后，將較辛堋（大）者放在第n-1位即可样勃，此時(shí)選擇排序完成
假設(shè)現(xiàn)在有一組數(shù)據(jù)[3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]，對(duì)其排序性芬，從小到大
排序過程：
JavaScript 代碼如下：
var arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
// 選擇排序
function sort(arr){
for(var i = 0; i < arr.length - 1; i++){
var min = i;
for(var j = i+1; j < arr.length; j++){
if(arr[min] > arr[j]){
min = j;
}
}
if(i !== min){
swap(i, min, arr);
}
}
return arr;
}
function swap(a, b, arr){
var temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
console.log(sort(arr));
排序結(jié)果：
插入排序
思想：與取撲克牌的原理相同峡眶。取第1張牌，無需排序植锉；取第2張牌辫樱，與第1張比較，若比第1張小則將牌放在第1張前面俊庇，1挪到了2的位置狮暑；取第3張牌鸡挠，與第2張比較，若比第2張小則將第2張牌放右挪1位搬男，若比第1張還小拣展，則將第1張也往右挪1位，插入到第1張的位置......以此類推缔逛，當(dāng)取到第n張時(shí)备埃，將與它前面的牌相比較，比前面的小就往前挪褐奴，插入適當(dāng)?shù)奈恢眉纯砂唇牛藭r(shí)插入排序完成
假設(shè)現(xiàn)在有一組數(shù)據(jù)[3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]，對(duì)其排序歉糜，從小到大
排序過程：
JavaScript 代碼如下：
var arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
// 插入排序
function sort(arr){
for(var i = 1; i < arr.length; i++){
var current = arr[i];
for(var j = i-1; j >= 0; j--){
if(current < arr[j]){
arr[j+1] = arr[j];
arr[j] = current;
}else {
arr[j+1] = current;
break;
}
}
}
return arr;
}
console.log(sort(arr));
排序結(jié)果：
歸并排序
思想：跟公司管理人員的思想類似乘寒，以一個(gè)部門為例，部門總監(jiān)將手頭任務(wù)派給部門經(jīng)理匪补，部門經(jīng)理再將任務(wù)分配給各個(gè)小組的組長(zhǎng)，組長(zhǎng)再將任務(wù)派給組員烂翰，組員之間合作完成夯缺，等任務(wù)完成匯總再匯報(bào)給總監(jiān)。該算法是采用分治法的一個(gè)非常典型的應(yīng)用甘耿，將已有序的子序列合并踊兜，得到完全有序的序列；即先使每個(gè)子序列有序佳恬，再使子序列段間有序捏境。若將兩個(gè)有序表合并成一個(gè)有序表，稱為2-路歸并（先遞歸的分解數(shù)列毁葱，再合并數(shù)列）
假設(shè)現(xiàn)在有一組數(shù)據(jù)[3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]垫言，對(duì)其排序，從小到大
排序過程：
JavaScript 代碼如下：
var arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
// 歸并排序
function sort(arr){
var n = arr.length;
if(n < 2){
return arr;
}
var i = Math.ceil(n/2);
var arr1 = arr.slice(0, i);
var arr2 = arr.slice(i);
return mergeArr(sort(arr1), sort(arr2));
}
function mergeArr(arr1, arr2){
var arr = [];
while(arr1.length > 0 && arr2.length > 0){
if(arr1[0] <= arr2[0]){
arr.push(arr1.shift());
}else {
arr.push(arr2.shift());
}
}
while(arr1.length > 0){
arr.push(arr1.shift());
}
while(arr2.length > 0){
arr.push(arr2.shift());
}
return arr;
}
console.log(sort(arr));
排序結(jié)果：
快速排序
思想：在數(shù)列中選一個(gè)元素作為基準(zhǔn)倾剿，將比基準(zhǔn)小的元素放在基準(zhǔn)左側(cè)筷频，比基準(zhǔn)大的元素放在基準(zhǔn)右側(cè)，再分別對(duì)基準(zhǔn)左側(cè)和右側(cè)的數(shù)列以同樣的方法排序前痘，最后再將基準(zhǔn)左側(cè)的有序列表和基準(zhǔn)右側(cè)的有序列表整合到一起排序即可凛捏。快速排序每次都以第一個(gè)元素作為基準(zhǔn)芹缔，隨機(jī)快速排序則隨機(jī)選取基準(zhǔn)
假設(shè)現(xiàn)在有一組數(shù)據(jù)[3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]坯癣，對(duì)其排序，從小到大
排序過程：
JavaScript 代碼如下：
var arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
// 快速排序
function sort(arr, left, right){
var n = arr.length;
var left = typeof left === 'number' ? left : 0;
var right = typeof right === 'number' ? right : n - 1;
var pivorIndex = 0;
if(left < right){
pivorIndex = setPart(arr, left, right);
sort(arr, left, pivorIndex);
sort(arr, pivorIndex+1, right);
}
return arr;
}
function setPart(arr, left, right){
var pivor = arr[left];
var index = left+1;
for(var i = index; i <= right; i++){
if(arr[i] < pivor){
swap(index, i, arr);
index ++;
}
}
swap(index-1, left, arr);
return index-1;
}
function swap(a, b, arr){
var temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
console.log(sort(arr));
排序結(jié)果：
計(jì)數(shù)排序
思想：是一種穩(wěn)定的排序算法最欠。使用一個(gè)額外的數(shù)組C示罗，其中第i個(gè)元素是待排序數(shù)組A中值等于i的元素的個(gè)數(shù)蓬网。然后根據(jù)數(shù)組C來將A中的元素排到正確的位置。它只能對(duì)有確定范圍的整數(shù)進(jìn)行排序
假設(shè)現(xiàn)在有一組數(shù)據(jù)[2, 3, 8, 7, 1, 2, 2, 2, 7, 3, 9, 8, 2, 1, 4, 2, 4, 6, 9, 2]鹉勒，對(duì)其排序帆锋，從小到大
排序過程：
JavaScript 代碼如下：
var arr = [2, 3, 8, 7, 1, 2, 2, 2, 7, 3, 9, 8, 2, 1, 4, 2, 4, 6, 9, 2];
// 計(jì)數(shù)排序
function sort(arr){
var min = max = arr[0];
var c = [];
for(var i = 0; i < arr.length; i++){
if(min > arr[i]){
min = arr[i];
}
if(max < arr[i]){
max = arr[i];
}
c[arr[i]] = c[arr[i]] ? c[arr[i]] + 1 : 1;
}
var result = [];
for(var j = min; j <= max; j++){
if(c[j]){
for(var k = 0; k < c[j]; k++){
result.push(j);
}
}
}
return result;
}
console.log(sort(arr));
排序結(jié)果：
基數(shù)排序
思想：按照數(shù)的高低位排序，先按低位進(jìn)行排序禽额，然后收集锯厢；再按高位排序，然后收集脯倒；依次類推实辑，直到最高位。
假設(shè)現(xiàn)在有一組數(shù)據(jù)[3221, 1, 10, 9680, 577, 9420, 7, 5622, 4793, 2030, 3138, 82, 2599, 743, 4127]藻丢，對(duì)其排序剪撬，從小到大
排序過程：
JavaScript 代碼如下：
var arr = [3221, 1, 10, 9680, 577, 9420, 7, 5622, 4793, 2030, 3138, 82, 2599, 743, 4127];
// 基數(shù)排序
function sort(arr){
var max = arr[0];
var len = 0;
var result = [];
for(var i = 0; i < arr.length; i++){
if(max < arr[i]){
max = arr[i];
}
}
console.log(max);
while(max/10 >= 1){
len ++;
max = max/10;
}
console.log(len);
for(var m = 0; m <= len; m++){
for(var n = 0; n < arr.length; n++){
var point = parseInt(arr[n]%Math.pow(10, m+1)/Math.pow(10, m));
if(result[point] == null){
result[point] = [];
}
result[point].push(arr[n]);
}
var pos = 0;
for(var k = 0; k < result.length; k++){
var value = null;
if(result[k] != null){
while((value = result[k].shift()) != null){
arr[pos] = value;
pos++;
}
}
}
}
return arr;
}
console.log(sort(arr));
排序結(jié)果：
