为什么我的Java快速排序不移植到Javascript

Why is my Java Quicksort not porting into Javascript?

本文关键字:Javascript 我的 Java 快速排序 为什么      更新时间:2023-09-26

我在Java中实现了快速排序,但是当我将它移植到JS时,它不能正确排序。给什么?

测试用例:{5,86,69,73,11日,17日,5日,86年,74年,34岁的3 1000年1}

排序后

Java: 11 3 5 5 11 17 34 69 73 74 86 86 1000

JS: 1 3 1 34 86 74 1000 5 5 11 69 17 73 86

Java代码
public class QuickSort {
/**
 * @param args the command line arguments
 */
public static void main(String[] args) {
    //int[] newArray = Arrays.copyOfRange(oldArray, startIndex, endIndex);
    int[] arr = new int[]{5,86,69,73,11,17,5,86,1,74,34,3, 1000, 1};
    quickSort(arr, 0, arr.length - 1);
    for(int i = 0; i < arr.length; i++) {
        System.out.print(arr[i] + " ");
    }
}
private static void quickSort(int[] arr, int lowerIndex, int higherIndex) {
    int i = lowerIndex;
    int j = higherIndex;
    // calculate pivot number, I am taking pivot as middle index number
    int pivot = arr[lowerIndex+(higherIndex-lowerIndex)/2];
    // Divide into two arrays
    while (i <= j) {
        /**
         * In each iteration, we will identify a number from left side which 
         * is greater then the pivot value, and also we will identify a number 
         * from right side which is less then the pivot value. Once the search 
         * is done, then we exchange both numbers.
         */
        while (arr[i] < pivot) {
            i++;
        }
        while (arr[j] > pivot) {
            j--;
        }
        if (i <= j) {
            swap(arr, i, j);
            //move index to next position on both sides
            i++;
            j--;
        }
    }
    // call quickSort() method recursively
    if (lowerIndex < j)
        quickSort(arr, lowerIndex, j);
    if (i < higherIndex)
        quickSort(arr, i, higherIndex);
}
private static void swap(int[] arr, int i, int j) {
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}
}

JS代码
var arr = [5,86,69,73,11,17,5,86,1,74,34,3,1000,1];
quickSort(arr, 0, arr.length - 1);
function quickSort(arr, lowerIndex, higherIndex) {
  var i = lowerIndex;
  var j = higherIndex;
  var pivot = arr[lowerIndex + (higherIndex - lowerIndex)/2];
  while(i <= j) {
        while(arr[i] < pivot) {
        i++;
      }
      while(arr[j] > pivot) {
        j--;
      }
      if(i <= j) {
        swap(arr, i, j);
        i++;
        j--;
      }
  }
  if(lowerIndex < j)
    quickSort(arr, lowerIndex, j);
  if(i < higherIndex) 
    quickSort(arr, i, higherIndex);
}
function swap(arr, i, j) {
    var tmp = arr[i];
  arr[i] = arr[j];
  arr[j] = tmp;
}

JSFiddle: https://jsfiddle.net/a4oLk4hc/

我在这里更新了您的小提琴,现在应该可以为您工作了。您的端口的问题是这一行:

var pivot = arr[lowerIndex + (higherIndex - lowerIndex)/2];

这是因为在javascript中除以2可能会得到0.5的小数。为了解决这个问题,使用Math.floor()来确保值被正确舍入。例如:

var pivot = arr[Math.floor(lowerIndex + (higherIndex - lowerIndex) / 2)];

JS变量没有明确的类型,所以要小心,你的问题在这里:

var pivot = arr[parseInt(lowerIndex + (higherIndex - lowerIndex)/2)];