快速排序

概念

快速排序由C. A. R. Hoare在1960年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

步骤分析:

快速排序算法通过多次比较和交换来实现排序，其排序流程如下： (1)首先设定一个分界值，通过该分界值将数组分成左右两部分。 (2)将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值。 (3)然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。 (4)重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。

举例

有一个数组，其中包含 1 5 8 9 11 556 32 587 把他从小到大排序

排序方法

  /**
   * 快速排序，左侧边界应该小于右侧
   *
   * @param array
   * @param left
   * @param right
   */
  public static void quickSort(int[] array, int left, int right) {
    if (array == null) {
      return;
    }
    if (left > right) {
      return;
    }
    int i = left;
    int j = right;
    int temp = array[i];
    while (i < j) {
      // 左侧右侧大于左侧，那么右边界右移
      while (i < j && array[j] >= temp) {
        j--;
      }
      // 如果 i < j，说明 j 处值比基准值小(根据上面循环判断)
      if (i < j) {
        // 交换 j 与 i 处的值，并将 i 向后移动
        array[i++] = array[j];
      }

      // 如果 i 处值小于等于基准值，那么将i向后移动就可以了
      while (i < j && array[i] <= temp) {
        i++;
      }
      // 如果 i < j，说明 i 处值比基准值大(根据上面循环判断)
      if (i < j) {
        // 交换 i 与 j 处的值，并将 i 向前移动
        array[j--] = array[i];
      }

      // 最后将临时基准值填充到 i 处
      array[i] = temp;
      // 对两段各自快速排序
    }
    quickSort(array, left, i - 1);
    quickSort(array, i + 1, right);
  }

使用演示

package com.pv3.springboot_base.Controller;

import com.pv3.springboot_base.Utils.Sort;
import org.springframework.web.bind.annotation.RequestMapping;
import org.springframework.web.bind.annotation.RestController;

import java.util.Arrays;

@RestController
public class SortController {
  
  @RequestMapping("/quickSort")
  public String quickSort() {
    // 1 5 8 9 11 556 32 587
    // 注意知识点: 数组是引用，不是复制
    int[] array = {1, 5, 8, 9, 11, 556, 32, 587};
    //    Sort.quickSort(array, 3, 0);
    Sort.quickSort(array, 0, array.length - 1);
    System.out.println(Arrays.toString(array));
    return "sort.quickSort 快速排序演示";
  }
}

在Java中，所有对象都是通过引用进行操作的。 而数组也是一种对象。当将数组作为参数传递给方法时，传递的实际上就是该数组对象的引用在方法中对数组的所有操作，都会映射到原数组中，这一点也是Java面向对象的一个重要特点。

请注意，除了对象有这种特性外，整型、浮点型、布尔型等基本数据类型都不具备该特性。