快速排序代码说明

Question

这是我遇到的实现快速排序算法的代码.你能解释一下递归是如何起作用的吗？

 void quickSort(int arr[], int left, int right)
 {
  int i = left, j = right;
  int tmp;
  int pivot = arr[(left + right) / 2];

  /* partition */
  while (i <= j) {
        while (arr[i] < pivot)
              i++;
        while (arr[j] > pivot)
              j--;
        if (i <= j) {
              tmp = arr[i];
              arr[i] = arr[j];
              arr[j] = tmp;
              i++;
              j--;
    }
}
/* recursion */
if (left < j)
    quickSort(arr, left, j);
if (i < right)
        quickSort(arr, i, right);
}

请注意,这不是作业.

Answer 1

不确定你的意思是"解释递归是如何工作的".但是你走了:

您发布的函数采用一组int和两个索引.它不会对整个数组进行排序,只会对两个索引之间的部分进行排序,忽略它们之外的任何内容.这意味着同样的功能,如果你传递一个,如果你通过第一个和最后一个索引,或者只是一个子阵列整个数组排序left值不是阵列和/或第一个元素的索引right值是不最后一个元素的索引.

排序算法是众所周知的快速排序.作为枢轴,它使用中心元素(它也可以使用任何其他元素).它将数组分区为less than (or equal to) pivot子数组和greater than (or equal to) pivot子数组,使元素等于两个分区之间的数据透视.

然后它递归地调用自己来对两个分区进行排序,但只在必要时才进行排序(因此在递归调用之前是ifs).

实施工作,但在许多方面是次优的,可以改进.以下是一些可能的改进:

1. 如果阵列足够短,则切换到另一种排序算法
2. 选择枢轴值作为三个值的中位数(通常是第一个,最后一个和中间)
3. 最初将一个透视值移出数组(将其置于第一个或最后一个位置并将焦点减少到数组的其余部分)然后更改测试以传递等于数据透视的值以减少涉及它们的交换数量.您将把枢轴值重新放入最后的最终交换中.如果您不遵循建议2并选择第一个/最后一个元素而不是像在此实现中的中间元素,则此功能尤其有用.