快速排序(Quick Sort)
通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,则可分别对这两部分记录进行排序,以达到整个序列有序的目的。
枢轴(pivot)
先选取序列当中的一个关键字,想尽办法将其放在一个位置,使得它左边的值都比它小,右边的值都比它大,我们将这样子的关键字称为枢轴。
函数构成
partition
选出枢轴,将比枢轴小的数字放在左边,将比枢轴大的数字放在右边,所有坐标遍历之后,返回此时枢轴的坐标
swap
交换两个坐标的值
算法图解
以{50,10,90,30}的数组为例,以下是初次交换的过程图解
快速排序.jpeg
代码(java)实现
public class QuickSortDemo { public static void main(String[] args) { int[] list = {50, 10, 90, 30, 70, 40, 80, 60, 20}; quickSort(list); for (int a : list) { System.out.println(a); } } private static void quickSort(int[] list) { if (list == null || list.length == 0) { return; } qSort(list, 0, list.length - 1); } private static void qSort(int[] list, int low, int high) { if (low < high) { int pivot = partition(list, low, high); qSort(list, low, pivot - 1); qSort(list, pivot + 1, high); } } /** * 我们这里以list[low]作为参考,所以肯定要先从high开始进行交换 * @param list * @param low * @param high * @return */ private static int partition(int[] list, int low, int high) { int pivotKey = list[low]; while (low < high) { while (low < high && list[high] >= pivotKey) { high--; } swap(list, low, high); while (low < high && list[low] <= pivotKey) { low++; } swap(list, low, high); } return low; } /** * 交换两个坐标的值 * @param list * @param index1 * @param index2 */ private static void swap(int[] list, int index1, int index2) { int data = list[index1]; list[index1] = list[index2]; list[index2] = data; }}