資訊專欄INFORMATION COLUMN
摘要：待排序的記錄序列中可能存在兩個或兩個以上的關鍵字相等的記錄，且在排序前在前面即，若在排序后的序列中任然在前面，則稱所用的排序算法是穩定的。基數排序留各種排序算法比較以上用到的函數函數返回生成的數組結束
排序 Sorting 排序基本概念
排序是計算機程序設計中的一種重要操作，他的功能是將一個數據元素(或記錄)的任意排列，重新排列成一個按關鍵字有序的序列。
待排序的記錄序列中可能存在兩個或兩個以上的關鍵字相等的記錄，且在排序前Ri在Rj前面(即i
如果按照排序過程中依據的不同原則對內部排序進行分類，則可分為
插入排序
交換排序(快速排序)
選擇排序
歸并排序
基數排序
如果按照工作量來區分可以分為3類
簡單的排序算法，時間復雜度為O(n2)
先進的排序算法，時間復雜度為O(nlogn)
基數排序，時間復雜度為O(d*n)
通常，在排序的過程中需要進行下列兩種基本操作，(其中第二種操作可以通過改變記錄的存儲方式來予以避免)
比較兩個關鍵字大小
將記錄從一個位置移動至另一個位置
待排序的記錄序列可有下列3種存儲方式。
存儲在地址連續的一組存儲單元上。
靜態鏈表，記錄之間的次序由指針指示，則實現排序不需要移動記錄
待排序記錄存儲在一組地址連續的存儲單元內，同時，另外設一個指示各個記錄存儲位置的地址向量，在排序過程中不移動記錄本身，而是移動地址向量
中這些記錄的“地址”，在排序結束后再按照地址向量中的值調整記錄的存儲位置。
最為簡單的一種排序，基本操作為將一個記錄插入到已經排好序的有序表中，從而得到一個新的，記錄增1的有序表。
//直接插入排序，更為高效的應該是折半插入排序?≥
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]; //當Arr[i] Arr[j]) {
break; //第一種：如果找到了一個比Arr[i]小的Arr[j],則退出循環，結束
}
//第二種，當j循環，結束
}
//結束j循環，將temp中緩存的待插入元素插入
Arr[j + 1] = temp;
}
}; //insert結束
其他插入排序
折半插入排序 O(n2) 通過減少比較關鍵字大小次數來優化排序算法。
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結束
快速排序
起泡排序 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
