快速排序理解

快速排序算法核心思想,取待排序序列中的某个元素作为分区点,大于分区点的元素挪到分区点右边(从小到大排序),小于分区点的元素挪到分区点左边。然后分区点左右两边的子序列循环以上操作,直至子序列长度为 1

左右指针法实现思路

1、首先定义分区点(pivot)pp 一般为数组 a 的第一个元素或最后一个元素 2、然后定义左(l)、右(r)两个指针分别指向数组的第一个元素(a[0])和最后一个元素 (a[a.length - 1]) 3、如果 a[l] > a[p]l、p 下标元素互换,l 前进 1 位 4、如果 a[r] < a[p]r、p 下标元素互换,r 后退 1 位 5、如果 l >= r,排序结束

快速排序左右指针法图解过程

快速排序左右指针法图解过程

代码实现

以递归方式实现编码,首先找出分析出递归条件:

1、递归方程:quickSort(a[l..r]) = quickSort(a[l..p-1]) + quickSort(a[p+1..r]) 2、递归退出条件:l >= r

注意点:如果选择分区点 p = l,必须先从右边找到小于 a[p] 的第一个元素开始

/**
 * 快速排序
 *
 * @param a 待排序数组
 * @param l 第一个元素下标
 * @param r 最后一个元素下标
 */
public static void sort(int[] a, int l, int r) {
  if (a == null || l >= r) {
    return;
  }

  int i = l, j = r;
  int p = l; // 选择最左边的元素为 pivot
  while (l < r) {
    // 如果选择 p = l 必须先从右边找到小于 a[p] 的第一个元素
    while (l < r && a[r] >= a[p]) {
      r--;
    }
    swap(a, r, p);
    p = r;

    // 从左边找到大于 a[p] 的第一个元素
    while (l < r && a[l] <= a[p]) {
      l++;
    }
    swap(a, l, p);
    p = l;
    System.out.println(Arrays.toString(a));
  }

  sort(a, i, p - 1);
  sort(a, p + 1, j);
}

public static swap(int[] a, int i, int j) {
    int tmp = a[i];
    a[i] = a[j];
    a[j] = tmp;
}