【Java -- 算法】十大排序算法之快速排序

简介

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较，但这种状况并不常见。事实上，快速排序通常明显比其他Ο(n log n) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。

快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。

算法步骤

1. 从数列中挑出一个元素，称为 “基准”（pivot），

2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。

3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，但是这个算法总会退出，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。

实例

1. Java 代码

import java.util.Random;
public class Main
{
public static void main(String[] args) {
Random r = new Random();
int[] data = new int[100];
for (int i = 0; i < data.length; i++) {
data[i] = r.nextInt(10);
}
Long startTime = System.currentTimeMillis();
print(data);
Long endTime = System.currentTimeMillis();
//方式一：固定基准元
// sortCommon(data, 0, data.length-1);

//方法二：随机基准元
// sortRandom(data, 0, data.length-1);

//方法三：采用三数取中
//sortMiddleOfThree(data, 0, data.length-1);

//优化一
// sortThreeInsert(data, 0, data.length-1); //当待排序序列的长度分割到一定大小后，使用插入排序

//优化二
sortThreeInsertGather(data, 0, data.length - 1); //在一次分割结束后，可以把与Key相等的元素聚在一起，继续下次分割时，不用再对与key相等元素分割
print(data);
System.out.println("排序用时:" + (endTime - startTime));
}

public static void sortCommon(int[] data, int low, int high) {
if (high > low) {
//进行一次排序，将基准元放置在正确顺序的位置上，并确定当前基准元位置
int key = getStandard(data, low, high);
//分别将基准元左侧和基准元右侧当做一个序列从新进行排序，知道序列的长度为1
sortCommon(data, low, key - 1);
sortCommon(data, key + 1, high);
}
}

public static int getStandard(int[] data, int low, int high) {
//将基准元提取出来
int tmp = data[low];
while (low < high) {
//从右往左查询，查找第一个小于基准元的元素，并将其放置在data[low]位置
while (low < high && data[high] >= tmp) {
high--;
}
data[low] = data[high];
//从左往右查询，查找第一个大于基准元的元素，并将其放置在data[high]位置
while (low < high && data[low] <= tmp) {
low++;
}
data[high] = data[low];
}
//基准元归为
data[low] = tmp;
return low;
}

public static void sortRandom(int[] data, int low, int high) {
if (high > low) {
//进行一次排序，将基准元放置在正确顺序的位置上，并确定当前基准元位置
getStandardRandom(data, low, high);
int key = getStandard(data, low, high);
//分别将基准元左侧和基准元右侧当做一个序列从新进行排序，知道序列的长度为1
sortRandom(data, low, key - 1);
sortRandom(data, key + 1, high);
}
}

private static void getStandardRandom(int[] data, int low, int high) {
Random r = new Random();
int ran = low + r.nextInt(high - low);
//将基准元提取出来
swap(data, low, ran);
}

public static void sortMiddleOfThree(int[] data, int low, int high) {
if (high > low) {
//三数去中，并将中间数换到low位置上
middleOfThree(data, low, high);
//进行一次排序，将基准元放置在正确顺序的位置上，并确定当前基准元位置
int key = getStandard(data, low, high);
//分别将基准元左侧和基准元右侧当做一个序列从新进行排序，知道序列的长度为1
sortMiddleOfThree(data, low, key - 1);
sortMiddleOfThree(data, key + 1, high);
}
}

private static void middleOfThree(int[] data, int low, int high) {
int middle = (high - low) / 2 + low;
if (data[middle] > data[high]) {
swap(data, middle, high);
}
if (data[low] > data[high]) {
swap(data, low, high);
}
if (data[middle] > data[low]) {
swap(data, middle, low);
}
}

public static void sortThreeInsert(int[] data, int low, int high) {
if (high - low + 1 < 10) {
insertSort(data);
return;
} else {
//三数去中，并将中间数换到low位置上
middleOfThree(data, low, high);
//进行一次排序，将基准元放置在正确顺序的位置上，并确定当前基准元位置
int key = getStandard(data, low, high);
//分别将基准元左侧和基准元右侧当做一个序列从新进行排序，知道序列的长度为1
sortThreeInsert(data, low, key - 1);
sortThreeInsert(data, key + 1, high);
}
}

public static void sortThreeInsertGather(int[] data, int low, int high) {
if (high - low + 1 < 10) {
insertSort(data);
return;
} else {
//三数去中，并将中间数换到low位置上
middleOfThree(data, low, high);
//进行一次排序，确定基准元位置，并将和基准元相等的元素，一直数组的两侧
//first 和last 用来计算基准元
int first = low;
int last = high;
//left和right 用来记录和基准元相等的元素
int left = low;
int right = high;
//leftLength和rightLength用来记录左右两侧各有多少和基准元相等的元素
int leftLength = 0;
int rightLength = 0;
int tmp = data[first];
while (first < last) {
while (first < last && data[last] >= tmp) {
if (data[last] == tmp) {
swap(data, last, right);
right--;
rightLength++;
}
last--;
}
data[first] = data[last];
while (first < last && data[first] <= tmp) {
if (data[first] == tmp) {
swap(data, first, left);
left++;
leftLength++;
}
first++;
}
data[last] = data[first];
}
data[first] = tmp;

//一次排序完成，将两侧与基准元相等的元素移到基准元旁边
int i = first - 1;
int j = low;
while (j < left && data[i] != tmp) {
swap(data, i, j);
i--;
j++;
}
i = last + 1;
j = high;
while (j > right && data[i] != tmp) {
swap(data, i, j);
i++;
j--;
}
sortThreeInsert(data, low, first - 1 - leftLength);
sortThreeInsert(data, first + 1 + rightLength, high);
}
}


public static void insertSort(int[] a) {
//从下标为1开始比较，知道数组的末尾
for (int i = 1; i < a.length; i++) {
int j;
//将要比较的元素，拿出待比较过后再插入数组
int tmp = a[i];
//一次与前一元素比较，如果前一元素比要插入的元素大，则互换位置
for (j = i - 1; j >= 0 && a[j] > tmp; j--) {
a[j + 1] = a[j];
}
//将比较的元素插入
a[j + 1] = tmp;
}
}

public static void print(int[] a) {
for (int i = 0; i < a.length; i++) {
System.out.print(a[i] + " ");
}
System.out.println();
}

private static void swap(int[] data, int i, int j) {
if (i == j) {
return;
}
data[i] = data[i] + data[j];
data[j] = data[i] - data[j];
data[i] = data[i] - data[j];
}
}

2. 输出结果