快排的诡异之处

ravenex

浏览: 11565 次
性别:
来自: 体育仓库

最近访客更多访客>>

epanthere

chenqi210

月下独酌

dohkoos

博主相关

博客

微博

相册

留言

关于我

文章分类

社区版块

存档分类

如果in-place做quick sort，选择放置pivot的位置会影响到代码细节。

同样的实现方式，选择第一个元素为pivot时，恢复pivot位置就得以hi为准。

public class TestQuickSort {
  public static void main(String[] args) {
    int[] arr = { 1, 4, 2, 3, 6, 5, 0 };
    quickSort(arr, 0, arr.length - 1);
    for (int i : arr) System.out.println(i);
  }
  
  public static void quickSort(int[] arr, int left, int right) {
    if (left >= right) return;
    int pivot = arr[left];
    int lo = left;
    int hi = right + 1;
    while (true) {
      while (arr[++lo] < pivot) { if (lo == right) break; }
      while (arr[--hi] > pivot) { }
      if (lo >= hi) break;
      swap(arr, lo, hi);
    }
    swap(arr, left, hi);
    quickSort(arr, left, hi - 1);
    quickSort(arr, hi + 1, right);
  }
  
  public static void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
  }
}

反之，以最后一个元素为pivot时，恢复pivot就得以lo为准。

public class TestQuickSort {
  public static void main(String[] args) {
    int[] arr = { 1, 4, 2, 3, 6, 5, 0 };
    quickSort(arr, 0, arr.length - 1);
    for (int i : arr) System.out.println(i);
  }
  
  public static void quickSort(int[] arr, int left, int right) {
    if (left >= right) return;
    int pivot = arr[right];
    int lo = left - 1;
    int hi = right;
    while (true) {
      while (arr[++lo] < pivot) { }
      while (arr[--hi] > pivot) { if (hi == left) break; }
      if (lo >= hi) break;
      swap(arr, lo, hi);
    }
    swap(arr, right, lo);
    quickSort(arr, left, lo - 1);
    quickSort(arr, lo + 1, right);
  }
  
  public static void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
  }
}

这是因为这种实现方式中，在选取恢复pivot的下标时，应选取“安全”的那个，也就是永远不会超过pivot所在位置的那个。
如果选取中间的元素为pivot，则无需恢复pivot，而且无论以lo还是hi为基准继续快排都行，因为在满足循环的结束条件时它们肯定相等。

public class TestQuickSort {
  public static void main(String[] args) {
    int[] arr = { 1, 4, 2, 3, 6, 5, 0 };
    quickSort(arr, 0, arr.length - 1);
    for (int i : arr) System.out.println(i);
  }
  
  public static void quickSort(int[] arr, int left, int right) {
    if (left >= right) return;
    int pivot = arr[(left + right) / 2];
    int lo = left - 1;
    int hi = right + 1;
    while (true) {
      while (arr[++lo] < pivot) { }
      while (arr[--hi] > pivot) { }
      if (lo >= hi) break;
      swap(arr, i, j);
    }
    quickSort(arr, left, lo - 1);
    quickSort(arr, lo + 1, right);
  }
  
  public static void swap(int[] arr, int i, int j) {
    System.out.println("swap " + i + " with " + j);
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
  }
}

分享到：