所謂排序，就是要整理文件中的記錄，使之按關鍵字遞增(或遞減)次序排列起來。其確切定義如下：
輸入：n個記錄R1，R2，…，Rn，其相應的關鍵字分別為K1，K2，…，Kn。
輸出：Ril，Ri2，…，Rin，使得Ki1≤Ki2≤…≤Kin。(或Ki1≥Ki2≥…≥Kin)。
??? 這里，我們簡單介紹幾種排序方法，直接插入排序、希兒排序、冒泡排序、快速排序、直接選擇排序，文中所提及的代碼在IE6下測試通過。
直接插入排序基本思想
??? 假設待排序的記錄存放在數組R[1..n]中。初始時，R[1]自成1個有序區，無序區為R[2..n]。從i=2起直至i=n為止，依次將R[i]插入當前的有序區R[1..i-1]中，生成含n個記錄的有序區。
??? 算法描述
?function?InsertSort(arr)?{?//插入排序->直接插入法排序
??var?st?=?new?Date();
??var?temp,?j;
??for(var?i=1;?i<arr.length;?i++)?{
???if((arr[i])?<?(arr[i-1]))?{
????temp?=?arr[i];
????j?=?i-1;
????do?{
?????arr[j+1]?=?arr[j];
?????j--;
????}
????while?(j>-1?&&?(temp)?<?(arr[j]));
????arr[j+1]?=?temp;
???}//endif
??}
??status?=?(new?Date()?-?st)?+?'?ms';
??return?arr;
?}
希爾排序基本思想
??先取一個小于n的整數d1作為第一個增量，把文件的全部記錄分成d1個組。所有距離為dl的倍數的記錄放在同一個組中。先在各組內進行直接插人排序；然后，取第二個增量d2<d1重復上述的分組和排序，直至所取的增量dt=1(dt<dt-l<…<d2<d1)，即所有記錄放在同一組中進行直接插入排序為止。
? 該方法實質上是一種分組插入方法。
??? 算法描述
?
function?ShellSort(arr)?{?//插入排序->希兒排序
??var?st?=?new?Date();
??var?increment?=?arr.length;
??do?{
???increment?=?(increment/3|0)?+?1;
???arr?=?ShellPass(arr,?increment);
??}
??while?(increment?>?1)
??status?=?(new?Date()?-?st)?+?'?ms';
??return?arr;
?}
?function?ShellPass(arr,?d)?{?//希兒排序分段執行函數
??var?temp,?j;
??for(var?i=d;?i<arr.length;?i++)?{
???if((arr[i])?<?(arr[i-d]))?{
????temp?=?arr[i];?j?=?i-d;
????do?{
?????arr[j+d]?=?arr[j];
?????j?=?j-d;
????}
????while?(j>-1?&&?(temp)?<?(arr[j]));
????arr[j+d]?=?temp;
???}//endif
??}
??return?arr;
?}
冒泡排序基本思想
???
將被排序的記錄數組R[1..n]垂直排列，每個記錄R[i]看作是重量為R[i].key的氣泡。根據輕氣泡不能在重氣泡之下的原則，從下往上掃描數組
R：凡掃描到違反本原則的輕氣泡，就使其向上"飄浮"。如此反復進行，直到最后任何兩個氣泡都是輕者在上，重者在下為止。
??? 算法描述
?function?BubbleSort(arr)?{?//交換排序->冒泡排序
??var?st?=?new?Date();
??var?temp;
??var?exchange;
??for(var?i=0;?i<arr.length;?i++)?{
???exchange?=?false;
???for(var?j=arr.length-2;?j>=i;?j--)?{
????if((arr[j+1])?<?(arr[j]))?{
?????temp?=?arr[j+1];
?????arr[j+1]?=?arr[j];
?????arr[j]?=?temp;
?????exchange?=?true;
????}
???}
???if(!exchange)?break;
??}
??status?=?(new?Date()?-?st)?+?'?ms';
??return?arr;
?}
快速排序基本思想
??? 將原問題分解為若干個規模更小但結構與原問題相似的子問題。遞歸地解這些子問題，然后將這些子問題的解組合為原問題的解。
???
在R[low..high]中任選一個記錄作為基準(Pivot)，以此基準將當前無序區劃分為左、右兩個較小的子區間R[low..pivotpos-
1)和R[pivotpos+1..high]，并使左邊子區間中所有記錄的關鍵字均小于等于基準記錄(不妨記為pivot)的關鍵字
pivot.key，右邊的子區間中所有記錄的關鍵字均大于等于pivot.key，而基準記錄pivot則位于正確的位置(pivotpos)上，它無
須參加后續的排序。
??? 算法描述
?function?QuickSort(arr)?{?//交換排序->快速排序
??if?(arguments.length>1)?{
???var?low?=?arguments[1];
???var?high?=?arguments[2];
??}?else?{
???var?low?=?0;
???var?high?=?arr.length-1;
??}
??if(low?<?high){
???//?function?Partition
???var?i?=?low;
???var?j?=?high;
???var?pivot?=?arr[i];
???while(i<j)?{
????while(i<j?&&?arr[j]>=pivot)
?????j--;
????if(i<j)
?????arr[i++]?=?arr[j];
????while(i<j?&&?arr[i]<=pivot)
?????i++;
????if(i<j)
?????arr[j--]?=?arr[i];
???}//endwhile
???arr[i]?=?pivot;
???//?end?function
???var?pivotpos?=?i;?//Partition(arr，low，high);
???QuickSort(arr,?low,?pivotpos-1);
???QuickSort(arr,?pivotpos+1,?high);
??}?else
???return;
???return?arr;
?}
直接選擇排序基本思想
?? n個記錄的文件的直接選擇排序可經過n-1趟直接選擇排序得到有序結果：
?①初始狀態：無序區為R[1..n]，有序區為空。
?②第1趟排序
????在無序區R[1..n]中選出關鍵字最小的記錄R[k]，將它與無序區的第1個記錄R[1]交換，使R[1..1]和R[2..n]分別變為記錄個數增加1個的新有序區和記錄個數減少1個的新無序區。
……
?③第i趟排序
第i趟排序開始時，當前有序區和無序區分別為R[1..i-1]和R[i..n](1≤i≤n-1)。該趟排序從當前無序區中選出關鍵字最小的記錄R?[k]，將它與無序區的第1個記錄R[i]交換，使R[1..i]和R[i+1..n]分別變為記錄個數增加1個的新有序區和記錄個數減少1個的新無序區。
????這樣，n個記錄的文件的直接選擇排序可經過n-1趟直接選擇排序得到有序結果。
????算法描述
?function?SelectSort(arr)?{?//選擇排序->直接選擇排序
??var?st?=?new?Date();
??var?temp;
??for(var?i=0;?i<arr.length;?i++)?{
???var?k?=?i;
???for(var?j=i+1;?j<arr.length;?j++)?{
????if((arr[j])?<?(arr[k]))
?????k?=?j;
???}
???if?(k?!=?i){
????temp?=?arr[i];
????arr[i]?=?arr[k];
????arr[k]?=?temp;
???}
??}
??status?=?(new?Date()?-?st)?+?'?ms';
??return?arr;
?}