Quicksort删除一些条件

-1

public static void quickSort(Integer[] arr, int low, int high) 
    { 
     //check for empty or null array 
     if (arr == null || arr.length == 0){ 
      return; 
     } 

     if (low >= high){ 
      return; 
     } 

     //Get the pivot element from the middle of the list 
     int middle = low + (high - low)/2; 
     int pivot = arr[middle]; 

     // make left < pivot and right > pivot 
     int i = low, j = high; 
     while (i <= j) 
     { 
      //Check until all values on left side array are lower than pivot 
      while (arr[i] < pivot) 
      { 
       i++; 
      } 
      //Check until all values on left side array are greater than pivot 
      while (arr[j] > pivot) 
      { 
       j--; 
      } 
      //Now compare values from both side of lists to see if they need swapping 
      //After swapping move the iterator on both lists 
      //NUMBER (1) 
      if (i <= j) 
      { 
       swap (arr, i, j); 
       i++; 
       j--; 
      } 
     } 
     //Do same operation as above recursively to sort two sub arrays 
     //NUMBER (2) 
     if (low < j){ 
      quickSort(arr, low, j); 
     } 
     //NUMBER (3) 
     if (high > i){ 
      quickSort(arr, i, high); 
     } 
    }

我是快速排序算法的初学者。有人可以告诉我什么是条件的目的，即如果数字（1），如果数字（2）和如果数字（3）在上面的快速排序算法？Quicksort删除一些条件

对于Number（1），我感觉的条件不是必须的，因为我肯定会小于或等于j，因此交换应该执行。

对于数字（2）和数字（3），它是类似的解释。请纠正我，如果我错了，感谢你

来源

2017-02-24 Desmond

你能给我无序的数组元素的一个样本来证明我可以比j，它错误地执行交换，这样我可以想像更大。谢谢 – Desmond

实际上，它看起来像是这样写的，'i <= j'在NUMBER（1）'处将始终为真。我不认为这个算法是正确实现的。 – khelwood

数量1 - 两个前for环路只是检查为右元素交换（从左边和右边）的计算i和j索引位置，所以当这个条件看看他们是否处于需要交换的位置（因为隐式地比另一个更重要）。

数字2和3 - 这些是“分而治之算法”的一部分，这部分只是将数组分成两部分。

看一看this（来源wikipedia）

来源

2017-02-24 09:32:30 freedev

我明白分而治之的方法。但是，我觉得我总是会低于j，低于 i。因此，没有必要把这些条件。请给我一个反例来反驳这个如果可能的话谢谢 – Desmond

不，对不起，这是不正确的方式。我建议你一步一步地调试这个代码并研究算法，这里有详细解释它的文档，文章和视频。 – freedev

在快速排序中的枢轴思想是让这个算法比其他算法更好的突破。 – freedev

Quicksort删除一些条件

回答

相关问题