假设待排序的记录存放在数组R[1..n]中。初始时，R[1]自成1个有序区，无序区为R[2..n]。从i=2起直至i=n为止，依次将R[i]插入当前的有序区R[1..i-1]中，生成含n个记录的有序区。
先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为dl的倍数的记录放在同一个组中。先在各组内进行直接插人排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量dt=1(dt<dt-l<…<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。SbcLinux联盟
该方法实质上是一种分组插入方法。
function ShellSort(arr) { //插入排序->希儿排序SbcLinux联盟
var st = new Date();SbcLinux联盟
var increment = arr.length;SbcLinux联盟
do {SbcLinux联盟
increment = (increment/3|0) + 1;SbcLinux联盟
arr = ShellPass(arr, increment);SbcLinux联盟
}SbcLinux联盟
while (increment > 1)SbcLinux联盟
status = (new Date() - st) + ' ms';SbcLinux联盟
return arr;SbcLinux联盟
}SbcLinux联盟
function ShellPass(arr, d) { //希儿排序分段执行函数SbcLinux联盟
var temp, j;SbcLinux联盟
for(var i=d; i<arr.length; i++) {SbcLinux联盟
if((arr[i]) < (arr[i-d])) {SbcLinux联盟
temp = arr[i]; j = i-d;SbcLinux联盟
do {SbcLinux联盟
arr[j+d] = arr[j];SbcLinux联盟
j = j-d;SbcLinux联盟
}SbcLinux联盟
while (j>-1 && (temp) < (arr[j]));SbcLinux联盟
arr[j+d] = temp;SbcLinux联盟
}//endifSbcLinux联盟
}SbcLinux联盟
return arr;SbcLinux联盟
}
冒泡排序基本思想
将被排序的记录数组R[1..n]垂直排列，每个记录R[i]看作是重量为R[i].key的气泡。根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R：凡扫描到违反本原则的轻气泡，就使其向上"飘浮"。如此反复进行，直到最后任何两个气泡都是轻者在上，重者在下为止。
SbcLinux联盟
算法描述SbcLinux联盟
function BubbleSort(arr) { //
交换排序->冒泡排序
SbcLinux联盟 var st = new Date();
SbcLinux联盟 var temp;
SbcLinux联盟 var exchange;
SbcLinux联盟 for(var i=0; i<arr.length; i++) {
SbcLinux联盟 exchange = false;
SbcLinux联盟 for(var j=arr.length-2; j>=i; j--) {
SbcLinux联盟 if((arr[j+1]) < (arr[j])) {
SbcLinux联盟 temp = arr[j+1];
SbcLinux联盟 arr[j+1] = arr[j];
SbcLinux联盟 arr[j] = temp;
SbcLinux联盟 exchange = true;
SbcLinux联盟 }
SbcLinux联盟 }
SbcLinux联盟 if(!exchange) break;
SbcLinux联盟 }
SbcLinux联盟 status = (new Date() - st) + ' ms';
SbcLinux联盟 return arr;
SbcLinux联盟 }
快速排序基本思想
将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题，然后将这些子问题的解组合为原问题的解。SbcLinux联盟
在R[low..high]中任选一个记录作为基准(Pivot)，以此基准将当前无序区划分为左、右两个较小的子区间R[low..pivotpos-1)和R[pivotpos+1..high]，并使左边子区间中所有记录的关键字均小于等于基准记录(不妨记为pivot)的关键字pivot.key，右边的子区间中所有记录的关键字均大于等于pivot.key，而基准记录pivot则位于正确的位置(pivotpos)上，它无须参加后续的排序。
算法描述SbcLinux联盟
function QuickSort(arr) { //
交换排序->快速排序
SbcLinux联盟 if (arguments.length>1) {
SbcLinux联盟 var low = arguments[1];
SbcLinux联盟 var high = arguments[2];
SbcLinux联盟 } else {
SbcLinux联盟 var low = 0;
SbcLinux联盟 var high = arr.length-1;
SbcLinux联盟 }
SbcLinux联盟 if(low < high){
SbcLinux联盟 // function Partition
SbcLinux联盟 var i = low;
SbcLinux联盟 var j = high;
SbcLinux联盟 var pivot = arr[i];
SbcLinux联盟 while(i<j) {
SbcLinux联盟 while(i<j && arr[j]>=pivot)
SbcLinux联盟 j--;
SbcLinux联盟 if(i<j)
SbcLinux联盟 arr[i++] = arr[j];
SbcLinux联盟 while(i<j && arr[i]<=pivot)
SbcLinux联盟 i++;
SbcLinux联盟 if(i<j)
SbcLinux联盟 arr[j--] = arr[i];
SbcLinux联盟 }//endwhile
SbcLinux联盟 arr[i] = pivot;
SbcLinux联盟 // end function
SbcLinux联盟 var pivotpos = i; //Partition(arr，low，high);
SbcLinux联盟 QuickSort(arr, low, pivotpos-1);
SbcLinux联盟 QuickSort(arr, pivotpos+1, high);
SbcLinux联盟 } else
SbcLinux联盟 return;
SbcLinux联盟 return arr;
SbcLinux联盟 }
直接选择排序基本思想
n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果：SbcLinux联盟
①初始状态：无序区为R[1..n]，有序区为空。SbcLinux联盟
②第1趟排序SbcLinux联盟
在无序区R[1..n]中选出关键字最小的记录R[k]，将它与无序区的第1个记录R[1]交换，使R[1..1]和R[2..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。SbcLinux联盟
……SbcLinux联盟
③第i趟排序SbcLinux联盟
第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个的新无序区。SbcLinux联盟
这样，n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果。
算法描述SbcLinux联盟
function SelectSort(arr) { //选择排序->直接选择排序
SbcLinux联盟 var st = new Date();
SbcLinux联盟 var temp;
SbcLinux联盟 for(var i=0; i<arr.length; i++) {
SbcLinux联盟 var k = i;
SbcLinux联盟 for(var j=i+1; j<arr.length; j++) {
SbcLinux联盟 if((arr[j]) < (arr[k]))
SbcLinux联盟 k = j;
SbcLinux联盟 }
SbcLinux联盟 if (k != i){
SbcLinux联盟 temp = arr[i];
SbcLinux联盟 arr[i] = arr[k];
SbcLinux联盟 arr[k] = temp;
SbcLinux联盟 }
SbcLinux联盟 }
SbcLinux联盟 status = (new Date() - st) + ' ms';
SbcLinux联盟 return arr;
SbcLinux联盟 }
SbcLinux联盟
<style>SbcLinux联盟
fieldset {SbcLinux联盟
font-size:12px;SbcLinux联盟
padding:10px;SbcLinux联盟
width:80%;SbcLinux联盟
margin:auto;SbcLinux联盟
}SbcLinux联盟
input {SbcLinux联盟
font-size:12px;SbcLinux联盟
font-family:Tahoma;SbcLinux联盟
}SbcLinux联盟
</style>SbcLinux联盟
<title>排序</title><h3 align="center">排序</h3><fieldset>SbcLinux联盟
<legend>插入排序</legend><p><b>直接插入排序</b>SbcLinux联盟
请输入一段要排序的字符，用半角逗号隔开SbcLinux联盟
<input name=insert type=text size=100 value="g,v,u,f,p,o,i,a,t,j,e,l,k">SbcLinux联盟
<br><input type=button value=" 排序 " onclick="alert(InsertSort(insert.value.split(',')));"><p><b>希儿排序</b><br> <input name=Shell type=text size=100 value="g,v,u,f,p,o,i,a,t,j">SbcLinux联盟
<br><input type=button value=" 排序 " onclick="alert(ShellSort(Shell.value.split(',')));"></fieldset><p><fieldset><legend>交换排序</legend><b>冒泡排序</b><br>SbcLinux联盟
<input name=bubble type=text size=100 value="g,v,u,f,p,o,i,a,t,j,e,l,k">SbcLinux联盟
<br><input type=button value=" 排序 " onclick="alert(BubbleSort(bubble.value.split(',')));"><p><b>快速排序<br></b> <input name=quick type=text size=100 value="3,1,5,4,6">SbcLinux联盟
<br><input type=button value=" 排序 " onclick="alert(QuickSortDemo(quick.value.split(',')));"></fieldset><p><fieldset>SbcLinux联盟
<legend>选择排序</legend><b>直接选择排序</b><br>SbcLinux联盟
<input name=select1 type=text size=100 value="g,v,u,f,p,o,i,a,t,j,e,l,k">SbcLinux联盟
<br><input type=button value=" 排序 " onclick="alert(SelectSort(select1.value.split(',')));"><p>... ...</fieldset><script>SbcLinux联盟
function InsertSort(arr) { //插入排序->直接插入法排序SbcLinux联盟
var st = new Date();SbcLinux联盟
var temp, j;SbcLinux联盟
for(var i=1; i<arr.length; i++) {SbcLinux联盟
if((arr[i]) < (arr[i-1])) {SbcLinux联盟
temp = arr[i];SbcLinux联盟
j = i-1;SbcLinux联盟
do {SbcLinux联盟
arr[j+1] = arr[j];SbcLinux联盟
j--;SbcLinux联盟
}SbcLinux联盟
while (j>-1 && (temp) < (arr[j]));SbcLinux联盟
arr[j+1] = temp;SbcLinux联盟
}//endifSbcLinux联盟
}SbcLinux联盟
status = (new Date() - st) + ' ms';SbcLinux联盟
return arr;SbcLinux联盟
}SbcLinux联盟
SbcLinux联盟
function ShellSort(arr) { //插入排序->希儿排序SbcLinux联盟
var st = new Date();SbcLinux联盟
var increment = arr.length;SbcLinux联盟
do {SbcLinux联盟
increment = (increment/3|0) + 1;SbcLinux联盟
arr = ShellPass(arr, increment);SbcLinux联盟
}SbcLinux联盟
while (increment > 1)SbcLinux联盟
status = (new Date() - st) + ' ms';SbcLinux联盟
return arr;SbcLinux联盟
}SbcLinux联盟
SbcLinux联盟
function ShellPass(arr, d) { //希儿排序分段执行函数SbcLinux联盟
var temp, j;SbcLinux联盟
for(var i=d; i<arr.length; i++) {SbcLinux联盟
if((arr[i]) < (arr[i-d])) {SbcLinux联盟
temp = arr[i]; j = i-d;SbcLinux联盟
do {SbcLinux联盟
arr[j+d] = arr[j];SbcLinux联盟
j = j-d;SbcLinux联盟
}SbcLinux联盟
while (j>-1 && (temp) < (arr[j]));SbcLinux联盟
arr[j+d] = temp;SbcLinux联盟
}//endifSbcLinux联盟
}SbcLinux联盟
return arr;SbcLinux联盟
}SbcLinux联盟
SbcLinux联盟
function BubbleSort(arr) { //交换排序->冒泡排序SbcLinux联盟
var st = new Date();SbcLinux联盟
var temp;SbcLinux联盟
var exchange;SbcLinux联盟
for(var i=0; i<arr.length; i++) {SbcLinux联盟
exchange = false;SbcLinux联盟
for(var j=arr.length-2; j>=i; j--) {SbcLinux联盟
if((arr[j+1]) < (arr[j])) {SbcLinux联盟
temp = arr[j+1];SbcLinux联盟
arr[j+1] = arr[j];SbcLinux联盟
arr[j] = temp;SbcLinux联盟
exchange = true;SbcLinux联盟
}SbcLinux联盟
}SbcLinux联盟
if(!exchange) break;SbcLinux联盟
}SbcLinux联盟
status = (new Date() - st) + ' ms';SbcLinux联盟
return arr;SbcLinux联盟
}SbcLinux联盟
SbcLinux联盟
function QuickSortDemo(arr) {SbcLinux联盟
var st = new Date();SbcLinux联盟
var result = QuickSort(arr);SbcLinux联盟
status = (new Date() - st) + ' ms';SbcLinux联盟
return result;SbcLinux联盟
} SbcLinux联盟
SbcLinux联盟
function QuickSort(arr) { //交换排序->快速排序SbcLinux联盟
if (arguments.length>1) {SbcLinux联盟
var low = arguments[1];SbcLinux联盟
var high = arguments[2];SbcLinux联盟
} else {SbcLinux联盟
var low = 0;SbcLinux联盟
var high = arr.length-1;SbcLinux联盟
}SbcLinux联盟
if(low < high){SbcLinux联盟
// function PartitionSbcLinux联盟
var i = low;SbcLinux联盟
var j = high;SbcLinux联盟
var pivot = arr[i];SbcLinux联盟
while(i<j) {SbcLinux联盟
while(i<j && arr[j]>=pivot)SbcLinux联盟
j--;SbcLinux联盟
if(i<j)SbcLinux联盟
arr[i++] = arr[j];SbcLinux联盟
while(i<j && arr[i]<=pivot)SbcLinux联盟
i++;SbcLinux联盟
if(i<j)SbcLinux联盟
arr[j--] = arr[i];SbcLinux联盟
}//endwhileSbcLinux联盟
arr[i] = pivot;SbcLinux联盟
// end functionSbcLinux联盟
var pivotpos = i; //Partition(arr，low，high);SbcLinux联盟
QuickSort(arr, low, pivotpos-1);SbcLinux联盟
QuickSort(arr, pivotpos+1, high);SbcLinux联盟
} elseSbcLinux联盟
return;SbcLinux联盟
return arr;SbcLinux联盟
}SbcLinux联盟
SbcLinux联盟
/*function Partition(arr, i, j) { //快速排序, 对待排序的数组进行划分SbcLinux联盟
var pivot = arr[i];SbcLinux联盟
while(i<j) {SbcLinux联盟
while(arr[j]>=pivot)SbcLinux联盟
j--;SbcLinux联盟
if(i<j)SbcLinux联盟
arr[i++] = arr[j];SbcLinux联盟
while(arr[i]<=pivot)SbcLinux联盟
i++;SbcLinux联盟
if(i<j)SbcLinux联盟
arr[j--] = arr[i];SbcLinux联盟
}SbcLinux联盟
arr[i] = pivot;SbcLinux联盟
return arr;SbcLinux联盟
}*/SbcLinux联盟
SbcLinux联盟
function SelectSort(arr) { //选择排序->直接选择排序SbcLinux联盟
var st = new Date();SbcLinux联盟
var temp;SbcLinux联盟
for(var i=0; i<arr.length; i++) {SbcLinux联盟
var k = i;SbcLinux联盟
for(var j=i+1; j<arr.length; j++) {SbcLinux联盟
if((arr[j]) < (arr[k]))SbcLinux联盟
k = j;SbcLinux联盟
}SbcLinux联盟
if (k != i){SbcLinux联盟
temp = arr[i];SbcLinux联盟
arr[i] = arr[k];SbcLinux联盟
arr[k] = temp;SbcLinux联盟
}SbcLinux联盟
}SbcLinux联盟
status = (new Date() - st) + ' ms';SbcLinux联盟
return arr;SbcLinux联盟
}SbcLinux联盟
SbcLinux联盟
function unicode(str) {//求字符串的unicode码SbcLinux联盟
var uni=0;SbcLinux联盟
for(var i=0; i<str.length; i++){SbcLinux联盟
uni += str.charCodeAt(i)/6553.5 * Math.pow(10, str.length-i);SbcLinux联盟
}SbcLinux联盟
return uni;SbcLinux联盟
}SbcLinux联盟
</script>
