鍍金池/ 問答/HTML/ nodejs中快速排序的問題

nodejs中快速排序的問題

下面是我的代碼，用CMD運(yùn)行的時(shí)候發(fā)現(xiàn)不輸出結(jié)果。
但是如果去掉遞歸是可以正常輸出結(jié)果的。真誠希望可以得到各位的幫助，非常感謝。下面是我寫的代碼：

var quickSort=function(arr){

  var left=0;
  var right=arr.length-1;
  var leftPoint=left;
  var rightPoint=right;
  var temp=arr[left];

  while(leftPoint!=rightPoint){

    while(arr[rightPoint]>=temp&&leftPoint<rightPoint){
      rightPoint--;
    }
    while(arr[leftPoint]<=temp&&leftPoint<rightPoint){
      leftPoint++;
    }
    if(leftPoint<rightPoint){
      var changeNumber=arr[leftPoint];
      arr[leftPoint]=arr[rightPoint];
      arr[rightPoint]=changeNumber;
    }
  }

  arr[left]=arr[leftPoint];
  arr[leftPoint]=temp;

  quickSort(left,leftPoint-1);
  quickSort(leftPoint+1,right);

  return arr;
};
var numArr=[6,1,2,7,9,3,4,5,10,8];
console.log(quickSort(numArr));
回答
編輯回答
兮顏

看你的題目應(yīng)該是想用原地排序，那我就順著你的思路來。

1.為了保證遞歸能記住位置，必須傳上一次排序的位置進(jìn)去，你想到了這一點(diǎn)，但是參數(shù)沒有傳對。因?yàn)槟闶窃嘏判?，那么每次都要?code>arr傳進(jìn)去，同時(shí)還有本次排序的left和right

2.添加邊界條件，判斷是否進(jìn)行下次排序，可以在函數(shù)開始判斷，也可以在調(diào)用遞歸之前判斷

3.當(dāng)然第一次是不會傳left和right的，因此要判斷這兩個(gè)參數(shù)，并賦默認(rèn)值

修改過后的方法如下：

var quickSort = function (arr, left, right) {

  // 是否進(jìn)行本次排序
  if (right <= left) return

  // 默認(rèn)值處理
  left = left || 0;
  right = right || arr.length - 1;

  var leftPoint = left;
  var rightPoint = right;
  var temp = arr[left];

  while (leftPoint != rightPoint) {

    while (arr[rightPoint] >= temp && leftPoint < rightPoint) {
      rightPoint--;
    }
    while (arr[leftPoint] <= temp && leftPoint < rightPoint) {
      leftPoint++;
    }
    if (leftPoint < rightPoint) {
      var changeNumber = arr[leftPoint];
      arr[leftPoint] = arr[rightPoint];
      arr[rightPoint] = changeNumber;
    }
  }

  arr[left] = arr[leftPoint];
  arr[leftPoint] = temp;

  quickSort(arr, left, leftPoint - 1)
  quickSort(arr, leftPoint + 1, right)

  return arr
};

原地排序節(jié)省空間，但是理解起來比另開空間的做法要困難一點(diǎn)，因?yàn)槿潭际窃谠瓟?shù)組上進(jìn)行操作的

2017年3月1日 14:17