javascript的幾種排序方法

　　所謂排序就是要整理文件中的記錄使之按關鍵字遞增(或遞減)次序排列起來其確切定義如下
　　輸入n個記錄RR…Rn其相應的關鍵字分別為KK…Kn
　　輸出RilRi…Rin使得Ki≤Ki≤…≤Kin(或Ki≥Ki≥…≥Kin)

　　這裡我們簡單介紹幾種排序方法直接插入排序希兒排序冒泡排序快速排序直接選擇排序文中所提及的代碼在IE下測試通過

　　直接插入排序基本思想

　　假設待排序的記錄存放在數組R[n]中初始時R[]自成個有序區無序區為R[n]從i=起直至i=n為止依次將R[i]插入當前的有序區R[i]中生成含n個記錄的有序區

　　算法描述

 function InsertSort(arr) { //插入排序>直接插入法排序
  var st = new Date();
  var temp j;
  for(var i=; i<arrlength; i++) {
   if((arr[i]) < (arr[i])) {
    temp = arr[i];
    j = i;
    do {
     arr[j+] = arr[j];
     j;
    }
    while (j> && (temp) < (arr[j]));
    arr[j+] = temp;
   }//endif
  }
  status = (new Date() st) + ms;
  return arr;
 }

　　希爾排序基本思想

　　先取一個小於n的整數d作為第一個增量把文件的全部記錄分成d個組所有距離為dl的倍數的記錄放在同一個組中先在各組內進行直接插人排序然後取第二個增量d<d重復上述的分組和排序直至所取的增量dt=(dt<dtl<…<d<d)即所有記錄放在同一組中進行直接插入排序為止
  　該方法實質上是一種分組插入方法

　　算法描述

　　function ShellSort(arr) { //插入排序>希兒排序
  var st = new Date();
  var increment = arrlength;
  do {
   increment = (increment/|) + ;
   arr = ShellPass(arr increment);
  }
  while (increment > )
  status = (new Date() st) + ms;
  return arr;
 }
 function ShellPass(arr d) { //希兒排序分段執行函數
  var temp j;
  for(var i=d; i<arrlength; i++) {
   if((arr[i]) < (arr[id])) {
    temp = arr[i]; j = id;
    do {
     arr[j+d] = arr[j];
     j = jd;
    }
    while (j> && (temp) < (arr[j]));
    arr[j+d] = temp;
   }//endif
  }
  return arr;
 }

　　冒泡排序基本思想

　　將被排序的記錄數組R[n]垂直排列每個記錄R[i]看作是重量為R[i]key的氣泡根據輕氣泡不能在重氣泡之下的原則從下往上掃描數組R凡掃描到違反本原則的輕氣泡就使其向上飄浮如此反復進行直到最後任何兩個氣泡都是輕者在上重者在下為止

　　算法描述

 function BubbleSort(arr) { //交換排序>冒泡排序
  var st = new Date();
  var temp;
  var exchange;
  for(var i=; i<arrlength; i++) {
   exchange = false;
   for(var j=arrlength; j>=i; j) {
    if((arr[j+]) < (arr[j])) {
     temp = arr[j+];
     arr[j+] = arr[j];
     arr[j] = temp;
     exchange = true;
    }
   }
   if(!exchange) break;
  }
  status = (new Date() st) + ms;
  return arr;
 }

　　快速排序基本思想

　　將原問題分解為若干個規模更小但結構與原問題相似的子問題遞歸地解這些子問題然後將這些子問題的解組合為原問題的解
    在R[lowhigh]中任選一個記錄作為基准(Pivot)以此基准將當前無序區劃分為左右兩個較小的子區間R[lowpivotpos)和R[pivotpos+high]並使左邊子區間中所有記錄的關鍵字均小於等於基准記錄(不妨記為pivot)的關鍵字pivotkey右邊的子區間中所有記錄的關鍵字均大於等於pivotkey而基准記錄pivot則位於正確的位置(pivotpos)上它無須參加後續的排序

　　算法描述

 function QuickSort(arr) { //交換排序>快速排序
  if (argumentslength>) {
   var low = arguments[];
   var high = arguments[];
  } else {
   var low = ;
   var high = arrlength;
  }
  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(arrlowhigh);
   QuickSort(arr low pivotpos);
   QuickSort(arr pivotpos+ high);
  } else
   return;
   return arr;
 }

　　直接選擇排序基本思想

　　n個記錄的文件的直接選擇排序可經過n趟直接選擇排序得到有序結果
 ①初始狀態無序區為R[n]有序區為空
 ②第趟排序
    在無序區R[n]中選出關鍵字最小的記錄R[k]將它與無序區的第個記錄R[]交換使R[]和R[n]分別變為記錄個數增加個的新有序區和記錄個數減少個的新無序區
　　……
 ③第i趟排序
　　第i趟排序開始時當前有序區和無序區分別為R[i]和R[in](≤i≤n)該趟排序從當前無序區中選出關鍵字最小的記錄R[k]將它與無序區的第個記錄R[i]交換使R[i]和R[i+n]分別變為記錄個數增加個的新有序區和記錄個數減少個的新無序區
    這樣n個記錄的文件的直接選擇排序可經過n趟直接選擇排序得到有序結果

　　算法描述

 function SelectSort(arr) { //選擇排序>直接選擇排序
  var st = new Date();
  var temp;
  for(var i=; i<arrlength; i++) {
   var k = i;
   for(var j=i+; j<arrlength; 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;
 }

　　<style>
fieldset {
 fontsize:px;
 padding:px;
 width:%;
 margin:auto;
}
input {
 fontsize:px;
 fontfamily:Tahoma;
}
</style>
<title>排序</title><h align=center>排序</h><fieldset>
<legend>插入排序</legend><p><b>直接插入排序</b>
請輸入一段要排序的字符用半角逗號隔開
<input name=insert type=text size= value=gvufpoiatjelk>
<br><input type=button value= 排序 onclick=alert(InsertSort(insertvaluesplit()));><p><b>希兒排序</b><br>  <input name=Shell type=text size= value=gvufpoiatj>
<br><input type=button value= 排序 onclick=alert(ShellSort(Shellvaluesplit()));></fieldset><p><fieldset><legend>交換排序</legend><b>冒泡排序</b><br>
<input name=bubble type=text size= value=gvufpoiatjelk>
<br><input type=button value= 排序 onclick=alert(BubbleSort(bubblevaluesplit()));><p><b>快速排序<br></b>  <input name=quick type=text size= value=>
<br><input type=button value= 排序 onclick=alert(QuickSortDemo(quickvaluesplit()));></fieldset><p><fieldset>
<legend>選擇排序</legend><b>直接選擇排序</b><br>
<input name=select type=text size= value=gvufpoiatjelk>
<br><input type=button value= 排序 onclick=alert(SelectSort(selectvaluesplit()));><p> </fieldset><script>
 function InsertSort(arr) { //插入排序>直接插入法排序
  var st = new Date();
  var temp j;
  for(var i=; i<arrlength; i++) {
   if((arr[i]) < (arr[i])) {
    temp = arr[i];
    j = i;
    do {
     arr[j+] = arr[j];
     j;
    }
    while (j> && (temp) < (arr[j]));
    arr[j+] = temp;
   }//endif
  }
  status = (new Date() st) + ms;
  return arr;
 }

 function ShellSort(arr) { //插入排序>希兒排序
  var st = new Date();
  var increment = arrlength;
  do {
   increment = (increment/|) + ;
   arr = ShellPass(arr increment);
  }
  while (increment > )
  status = (new Date() st) + ms;
  return arr;
 }

 function ShellPass(arr d) { //希兒排序分段執行函數
  var temp j;
  for(var i=d; i<arrlength; i++) {
   if((arr[i]) < (arr[id])) {
    temp = arr[i]; j = id;
    do {
     arr[j+d] = arr[j];
     j = jd;
    }
    while (j> && (temp) < (arr[j]));
    arr[j+d] = temp;
   }//endif
  }
  return arr;
 }

 function BubbleSort(arr) { //交換排序>冒泡排序
  var st = new Date();
  var temp;
  var exchange;
  for(var i=; i<arrlength; i++) {
   exchange = false;
   for(var j=arrlength; j>=i; j) {
    if((arr[j+]) < (arr[j])) {
     temp = arr[j+];
     arr[j+] = arr[j];
     arr[j] = temp;
     exchange = true;
    }
   }
   if(!exchange) break;
  }
  status = (new Date() st) + ms;
  return arr;
 }

 function QuickSortDemo(arr) {
  var st = new Date();
  var result = QuickSort(arr);
  status = (new Date() st) + ms;
  return result;
 } 

 function QuickSort(arr) { //交換排序>快速排序
  if (argumentslength>) {
   var low = arguments[];
   var high = arguments[];
  } else {
   var low = ;
   var high = arrlength;
  }
  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(arrlowhigh);
   QuickSort(arr low pivotpos);
   QuickSort(arr pivotpos+ high);
  } else
   return;
   return arr;
 }
 
 /*function Partition(arr i j) { //快速排序 對待排序的數組進行劃分
  var pivot = arr[i];
  while(i<j) {
   while(arr[j]>=pivot)
    j;
   if(i<j)
    arr[i++] = arr[j];
   while(arr[i]<=pivot)
    i++;
   if(i<j)
    arr[j] = arr[i];
  }
  arr[i] = pivot;
  return arr;
 }*/

 function SelectSort(arr) { //選擇排序>直接選擇排序
  var st = new Date();
  var temp;
  for(var i=; i<arrlength; i++) {
   var k = i;
   for(var j=i+; j<arrlength; 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;
 }

  function unicode(str) {//求字符串的unicode碼
  var uni=;
  for(var i=; i<strlength; i++){
   uni += strcharCodeAt(i)/ * Mathpow( strlengthi);
  }
  return uni;
 }
</script>

From:http://tw.wingwit.com/Article/program/Java/JSP/201311/19224.html