中文字幕二区_国产精品免费在线观看_黄色网站观看_人人草人人澡_日本真实娇小xxxx

所謂排序，就是要整理文件中的記錄，使之按關鍵字遞增(或遞減)次序排列起來。其確切定義如下：
　　輸入：n個記錄R₁，R₂，…，R_n，其相應的關鍵字分別為K₁，K₂，…，K_n。
　　輸出：R_il，R_i2，…，R_in，使得K_i1≤K_i2≤…≤K_in。(或K_i1≥K_i2≥…≥K_in)。

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

直接插入排序基本思想
    假設待排序的記錄存放在數組R[1..n]中。初始時，R[1]自成1個有序區(qū)，無序區(qū)為R[2..n]。從i=2起直至i=n為止，依次將R[i]插入當前的有序區(qū)R[1..i-1]中，生成含n個記錄的有序區(qū)。

    算法描述
 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的整數d₁作為第一個增量，把文件的全部記錄分成d₁個組。所有距離為d_l的倍數的記錄放在同一個組中。先在各組內進行直接插人排序；然后，取第二個增量d₂<d₁重復上述的分組和排序，直至所取的增量d_t=1(d_t<d_t-l<…<d₂<d₁)，即所有記錄放在同一組中進行直接插入排序為止。
  　該方法實質上是一種分組插入方法。

    算法描述

 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) { //希兒排序分段執(zhí)行函數
  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;
 }

快速排序基本思想
    將原問題分解為若干個規(guī)模更小但結構與原問題相似的子問題。遞歸地解這些子問題，然后將這些子問題的解組合為原問題的解。
    在R[low..high]中任選一個記錄作為基準(Pivot)，以此基準將當前無序區(qū)劃分為左、右兩個較小的子區(qū)間R[low..pivotpos-1)和R[pivotpos+1..high]，并使左邊子區(qū)間中所有記錄的關鍵字均小于等于基準記錄(不妨記為pivot)的關鍵字pivot.key，右邊的子區(qū)間中所有記錄的關鍵字均大于等于pivot.key，而基準記錄pivot則位于正確的位置(pivotpos)上，它無須參加后續(xù)的排序。

    算法描述
 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趟直接選擇排序得到有序結果：
 ①初始狀態(tài)：無序區(qū)為R[1..n]，有序區(qū)為空。
 ②第1趟排序
    在無序區(qū)R[1..n]中選出關鍵字最小的記錄R[k]，將它與無序區(qū)的第1個記錄R[1]交換，使R[1..1]和R[2..n]分別變?yōu)橛涗泜�數增加1個的新有序區(qū)和記錄個數減少1個的新無序區(qū)。
　　……
 ③第i趟排序
　　第i趟排序開始時，當前有序區(qū)和無序區(qū)分別為R[1..i-1]和R[i..n](1≤i≤n-1)。該趟排序從當前無序區(qū)中選出關鍵字最小的記錄R[k]，將它與無序區(qū)的第1個記錄R[i]交換，使R[1..i]和R[i+1..n]分別變?yōu)橛涗泜�數增加1個的新有序區(qū)和記錄個數減少1個的新無序區(qū)。
    這樣，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;
 }

運行代碼框
<style> fieldset { font-size:12px; padding:10px; width:80%; margin:auto; } input { font-size:12px; font-family:Tahoma; } </style> <title>排序</title> <h3 align="center">排序</h3> <fieldset> <legend>插入排序</legend> <p><b>直接插入排序</b> 請輸入一段要排序的字符，用半角逗號隔開 <input name=insert type=text size=100 value="g,v,u,f,p,o,i,a,t,j,e,l,k"> <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"> <br><input type=button value=" 排序 " onclick="alert(ShellSort(Shell.value.split(',')));"> </fieldset> <p> <fieldset> <legend>交換排序</legend> <b>冒泡排序</b><br> <input name=bubble type=text size=100 value="g,v,u,f,p,o,i,a,t,j,e,l,k"> <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"> <br><input type=button value=" 排序 " onclick="alert(QuickSortDemo(quick.value.split(',')));"> </fieldset> <p> <fieldset> <legend>選擇排序</legend> <b>直接選擇排序</b><br> <input name=select1 type=text size=100 value="g,v,u,f,p,o,i,a,t,j,e,l,k"> <br><input type=button value=" 排序 " onclick="alert(SelectSort(select1.value.split(',')));"> <p>... ... </fieldset> <script> 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; } 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) { //希兒排序分段執(zhí)行函數 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 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; } function QuickSortDemo(arr) { var st = new Date(); var result = QuickSort(arr); status = (new Date() - st) + ' ms'; return result; } 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; } /*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=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; } function unicode(str) {//求字符串的unicode碼 var uni=0; for(var i=0; i<str.length; i++){ uni += str.charCodeAt(i)/6553.5 * Math.pow(10, str.length-i); } return uni; } </script>
[Ctrl+A 全部選擇 提示：你可先修改部分代碼，再按運行]

出處：藍色理想
責任編輯：藍色

◎進入論壇網絡編程版塊參加討論