一、排序思想

将数组中的一个数作为基准，比该数小的放到左边，比该数大的放到右边；
对左右两边再进行上述操作，即把左边当成一个新数组，找新的基准数，右边也一样；
直到不能再分割下去为止。

案例：

假如待排序列如下：

选定6为基准数，然后先从右边开始遍历，找到一个比基准数小的数，如下图：

右边找到比基准数小的时候，右边先停下，再从左边开始遍历，找到比基准数大的，如下图：

这个时候，左右两边都先停下，交换5和7的位置，结果如下：

然后继续从右边开始遍历，即从7的位置开始，找到比基准数小的数，如下：

找到后停下，再从左往右找比基准数大的，即从5开始找，结果如下：

这个时候，左右两边都停下，交换9和4的位置，结果如下：

再从右边开始找比基准数小的，找到了3，然后从左边找比基准数大的，左边指针移动到3的时候，左右指针重合了，如下：

指针重合了，就将基准数和指针重合时所指的数交换位置，即交换6和3的位置，如图：

此时6左边的都是比它小的，右边的都是比它大的。左边部分和右边部分看成是两个新的待排序列，两个序列都按照上述方式再进行排序，先排左边，再排右边。

二、代码实现

结合上面的案例，以及代码中的注释，可以说是思路十分清晰了，完整代码如下：

public static void sort(int[] arr, int left, int right) {
  if (arr == null || arr.length == 1) {
   return;
  }
  if (left > right) {
   return;
  }
  int base = arr[left]; // 最左边的数当作基准数
  int i = left; // 从左往右遍历的指针
  int j = right; // 从右往左遍历的指针
  int temp = 0; // 用来保存临时变量
  // 当左右指针不相遇的时候，就进行检索
  while(i != j) {
   // 先从右往左检索，直到检索到比基准数小的
   while (arr[j] >= base && i < j) {
    j--;
   }
   // 再从左往右检索，直到检索到比基准数大的
   while (arr[i] <= base && i < j) {
    i++;
   }
   // 跳出了上面两个while循环，表示右边找到了基准数小的，左边找到了比基准数大的，交换位置
   temp = arr[i];
   arr[i] = arr[j];
   arr[j] = temp;
  }
  // 跳出了最外层while循环，表示i和j相等，左右指针相遇了，交换基准数和此时指针指的元素
  arr[left] = arr[i];
  arr[i] = base;
  // 此时，第一趟排序完成，左边和右边看成新数组，重复上述步骤
  sort(arr, j+1, right); // 排右边
  sort(arr, left, i-1); // 排左边
}

快速排序之所以成为快速排序，那就是因为它快，经测试，排1千万数据大概是1秒的样子，还真是有两把刷子。

-java开发那些事-

本站仅提供存储服务，所有内容均由用户发布，如发现有害或侵权内容，请点击举报。