資訊專欄INFORMATION COLUMN
摘要：待排序的記錄序列中可能存在兩個或兩個以上的關(guān)鍵字相等的記錄，且在排序前在前面即，若在排序后的序列中任然在前面，則稱所用的排序算法是穩(wěn)定的。基數(shù)排序留各種排序算法比較以上用到的函數(shù)函數(shù)返回生成的數(shù)組結(jié)束
排序 Sorting 排序基本概念
排序是計算機程序設(shè)計中的一種重要操作，他的功能是將一個數(shù)據(jù)元素(或記錄)的任意排列，重新排列成一個按關(guān)鍵字有序的序列。
待排序的記錄序列中可能存在兩個或兩個以上的關(guān)鍵字相等的記錄，且在排序前Ri在Rj前面(即i
如果按照排序過程中依據(jù)的不同原則對內(nèi)部排序進行分類，則可分為
插入排序
交換排序(快速排序)
選擇排序
歸并排序
基數(shù)排序
如果按照工作量來區(qū)分可以分為3類
簡單的排序算法，時間復(fù)雜度為O(n2)
先進的排序算法，時間復(fù)雜度為O(nlogn)
基數(shù)排序，時間復(fù)雜度為O(d*n)
通常，在排序的過程中需要進行下列兩種基本操作，(其中第二種操作可以通過改變記錄的存儲方式來予以避免)
比較兩個關(guān)鍵字大小
將記錄從一個位置移動至另一個位置
待排序的記錄序列可有下列3種存儲方式。
存儲在地址連續(xù)的一組存儲單元上。
靜態(tài)鏈表，記錄之間的次序由指針指示，則實現(xiàn)排序不需要移動記錄
待排序記錄存儲在一組地址連續(xù)的存儲單元內(nèi)，同時，另外設(shè)一個指示各個記錄存儲位置的地址向量，在排序過程中不移動記錄本身，而是移動地址向量
中這些記錄的“地址”，在排序結(jié)束后再按照地址向量中的值調(diào)整記錄的存儲位置。
最為簡單的一種排序，基本操作為將一個記錄插入到已經(jīng)排好序的有序表中，從而得到一個新的，記錄增1的有序表。
//直接插入排序，更為高效的應(yīng)該是折半插入排序?≥
function insertSort (Arr) {
if (Arr.length <= 1) {
return Arr;
}
var temp;
for (var i = 1; i < Arr.length; i++) { //從1開始，第一個不用排序
temp = Arr[i]; //用temp緩存待插入的元素
for (var j = i; j >= 0; j--) {
if (temp < Arr[j]) {
Arr[j + 1] = Arr[j]; //當(dāng)Arr[i] Arr[j]) {
break; //第一種：如果找到了一個比Arr[i]小的Arr[j],則退出循環(huán)，結(jié)束
}
//第二種，當(dāng)j循環(huán)，結(jié)束
}
//結(jié)束j循環(huán)，將temp中緩存的待插入元素插入
Arr[j + 1] = temp;
}
}; //insert結(jié)束
其他插入排序
折半插入排序 O(n2) 通過減少比較關(guān)鍵字大小次數(shù)來優(yōu)化排序算法。
2路插入排序
表插入排序
希爾排序 O(n3/2)又被稱為"縮小增量排序"。基本思想：先將整個待排記錄序列分割成若干個子序列分別進行直接插入排序，待整個序列中的記錄
“基本有序”時，再對全體記錄進行一次直接插入排序。
function shellSort(Arr) {
var gap = Math.floor(Arr.length / 2);
while (gap > 0) {
for (var i = 0; i < Arr.length; i++) {
var temp = Arr[i];
for (var j = i; j >= gap && Arr[j - gap] > temp; j -= gap) {
Arr[j] = Arr[j - gap];
}
Arr[j] = temp;
}
gap = Math.floor(gap / 2);
}
return Arr;
}; //shell結(jié)束
快速排序
起泡排序 bubble sort
// 起泡排序,
function bibbleSort(Arr) {
for (var i = Arr.length - 1; i >= 0; i--) {
for (var j = 0; j < i; j++) {
if (Arr[j] > Arr[j + 1]) {
swap(j, j + 1, Arr);
}
}
}
return Arr;
};
快速排序 quick sort
