快速排序 - Java示例

快速排序基于分而治之(divide-and-conquer)的思想,从数组中选择一个元素作为分区点,与其它元素作比较,小的放左边,大的放右边。

一般为了方便,直接取数组下标为0的数值做为分区点(pivot)。

从左(从下标1开始)向右将元素与pivot进行比较,小于pivot的依次放左边(从下标1开始),大于分区点的保持位置不变。

一轮遍历结束后,将中心点移到正确的位置,就完成了“治”的过程。

递归或循环这个过程,完成排序。

void quick_sort(int arr[], int start, int end) {
  if (start < end) {
   int piv_pos = partition(arr, start, end);
   quick_sort(arr, start, piv_pos - 1); // left
   quick_sort(arr, piv_pos + 1, end); // right
  }
 }

int partition(int arr[], int s, int e) {
  int i = s + 1;
  int piv = arr[s];// 分区点,
  for (int j = s + 1; j <= e; j++) {
   // 对s至e的区间进行排序,与分区点比较,小的放左边
   if (arr[j] < piv) {
    swap(arr, i, j);
    i++;
   }
  }
  // 将分区点放在正确的位置上
  swap(arr, s, i - 1);
  return i - 1;// 将分区点返回
 }

private void swap(int[] arr, int a, int b) {
  int t = arr[a];
  arr[a] = arr[b];
  arr[b] = t;
}


int[] arr = new int[] {5, 0, 11, 9, 3, 8, 8, 7, 5, 17};
quick_sort(arr, 0, arr.length - 1);

快排时间复杂度为O(nlogn), 最坏情况时间复杂度为O(n2) ,空间复杂度为O(1)。

稳定性

快排默认实现不稳定,若将索引作为比较的一部分,可以使任何排序算法稳定。