所谓排序，就是要整理文件中的记录，使之按关键字递增(或递减)次序排列起来。其确切定义如下：
输入：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;
}
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：凡扫描到违反本原则的轻气泡，就使其向上"飘浮"。如此反复进行，直到最后任何两个气泡都是轻者在上，重者在下为止。
