国产探花免费观看_亚洲丰满少妇自慰呻吟_97日韩有码在线_资源在线日韩欧美_一区二区精品毛片,辰东完美世界有声小说,欢乐颂第一季,yy玄幻小说排行榜完本

首頁 > 開發(fā) > JS > 正文

javascript 的幾種排序方法

2024-09-06 12:40:48
字體:
供稿:網(wǎng)友

所謂排序,就是要整理文件中的記錄,使之按關(guān)鍵字遞增(或遞減)次序排列起來。其確切定義如下:
  輸入:n個(gè)記錄R1,R2,…,Rn,其相應(yīng)的關(guān)鍵字分別為K1,K2,…,Kn
  輸出:Ril,Ri2,…,Rin,使得Ki1≤Ki2≤…≤Kin。(或Ki1≥Ki2≥…≥Kin)。

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

直接插入排序基本思想
    假設(shè)待排序的記錄存放在數(shù)組R[1..n]中。初始時(shí),R[1]自成1個(gè)有序區(qū),無序區(qū)為R[2..n]。從i=2起直至i=n為止,依次將R[i]插入當(dāng)前的有序區(qū)R[1..i-1]中,生成含n個(gè)記錄的有序區(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;
 }

希爾排序基本思想
   先取一個(gè)小于n的整數(shù)d1作為第一個(gè)增量,把文件的全部記錄分成d1個(gè)組。所有距離為dl的倍數(shù)的記錄放在同一個(gè)組中。先在各組內(nèi)進(jìn)行直接插人排序;然后,取第二個(gè)增量d2<d1重復(fù)上述的分組和排序,直至所取的增量dt=1(dt<dt-l<…<d2<d1),即所有記錄放在同一組中進(jìn)行直接插入排序?yàn)橹埂?BR>   該方法實(shí)質(zhì)上是一種分組插入方法。

    算法描述

 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í)行函數(shù)
  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;
 }

冒泡排序基本思想
    將被排序的記錄數(shù)組R[1..n]垂直排列,每個(gè)記錄R[i]看作是重量為R[i].key的氣泡。根據(jù)輕氣泡不能在重氣泡之下的原則,從下往上掃描數(shù)組R:凡掃描到違反本原則的輕氣泡,就使其向上"飄浮"。如此反復(fù)進(jìn)行,直到最后任何兩個(gè)氣泡都是輕者在上,重者在下為止。

    算法描述
 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;
 }

快速排序基本思想
    將原問題分解為若干個(gè)規(guī)模更小但結(jié)構(gòu)與原問題相似的子問題。遞歸地解這些子問題,然后將這些子問題的解組合為原問題的解。
    在R[low..high]中任選一個(gè)記錄作為基準(zhǔn)(Pivot),以此基準(zhǔn)將當(dāng)前無序區(qū)劃分為左、右兩個(gè)較小的子區(qū)間R[low..pivotpos-1)和R[pivotpos+1..high],并使左邊子區(qū)間中所有記錄的關(guān)鍵字均小于等于基準(zhǔn)記錄(不妨記為pivot)的關(guān)鍵字pivot.key,右邊的子區(qū)間中所有記錄的關(guān)鍵字均大于等于pivot.key,而基準(zhǔn)記錄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個(gè)記錄的文件的直接選擇排序可經(jīng)過n-1趟直接選擇排序得到有序結(jié)果:
 ①初始狀態(tài):無序區(qū)為R[1..n],有序區(qū)為空。
 ②第1趟排序
    在無序區(qū)R[1..n]中選出關(guān)鍵字最小的記錄R[k],將它與無序區(qū)的第1個(gè)記錄R[1]交換,使R[1..1]和R[2..n]分別變?yōu)橛涗泜€(gè)數(shù)增加1個(gè)的新有序區(qū)和記錄個(gè)數(shù)減少1個(gè)的新無序區(qū)。
  ……
 ③第i趟排序
  第i趟排序開始時(shí),當(dāng)前有序區(qū)和無序區(qū)分別為R[1..i-1]和R[i..n](1≤i≤n-1)。該趟排序從當(dāng)前無序區(qū)中選出關(guān)鍵字最小的記錄R[k],將它與無序區(qū)的第1個(gè)記錄R[i]交換,使R[1..i]和R[i+1..n]分別變?yōu)橛涗泜€(gè)數(shù)增加1個(gè)的新有序區(qū)和記錄個(gè)數(shù)減少1個(gè)的新無序區(qū)。
    這樣,n個(gè)記錄的文件的直接選擇排序可經(jīng)過n-1趟直接選擇排序得到有序結(jié)果。

    算法描述
 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;
 }

發(fā)表評論 共有條評論
用戶名: 密碼:
驗(yàn)證碼: 匿名發(fā)表
主站蜘蛛池模板: 灵寿县| 蒲江县| 色达县| 楚雄市| 长兴县| 红河县| 巫山县| 洛宁县| 小金县| 徐水县| 无为县| 江永县| 大丰市| 洛川县| 荃湾区| 运城市| 乳山市| 德安县| 宁化县| 青浦区| 耿马| 北宁市| 轮台县| 蓬安县| 汤阴县| 九台市| 绥宁县| 互助| 颍上县| 尚志市| 文山县| 河间市| 中西区| 上蔡县| 于田县| 永宁县| 庆城县| 阳东县| 绥中县| 兰考县| 石楼县|