nodejs中快速排序的问题

Question

下面是我的代码，用CMD运行的时候发现不输出结果。但是如果去掉递归是可以正常输出结果的。真诚希望可以得到各位的帮助，非常感谢。下面是我写的代码：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));

Answer 1

看你的题目应该是想用原地排序，那我就顺着你的思路来。

1.为了保证递归能记住位置，必须传上一次排序的位置进去，你想到了这一点，但是参数没有传对。因为你是原地排序，那么每次都要把arr传进去，同时还有本次排序的left和right

2.添加边界条件，判断是否进行下次排序，可以在函数开始判断，也可以在调用递归之前判断

3.当然第一次是不会传left和right的，因此要判断这两个参数，并赋默认值

修改过后的方法如下：

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

  // 是否进行本次排序

  if (right <= left) return

  // 默认值处理

  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

};

原地排序节省空间，但是理解起来比另开空间的做法要困难一点，因为全程都是在原数组上进行操作的