quickSort快速排序
快速排序
概念
快速排序由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面向对象的一个重要特点。
请注意,除了对象有这种特性外,整型、浮点型、布尔型等基本数据类型都不具备该特性。