常见的排序算法
目录
将不同的排序算法封装并继承共同的抽象类 Sorter，使它们可以相互替换：
public abstract class Sorter<T> {
private Comparator<? super T> comparator;
protected Sorter() {}
protected Sorter(Comparator<? super T> comparator) {
this.comparator = comparator;
}
public void setComparator(Comparator<? super T> comparator) {
this.comparator = comparator;
}
public abstract void sort(T[] array);
public void sort(T[] array, Comparator<T> comparator) {
this.setComparator(comparator);
this.sort(array);
this.setComparator(null);
}
@SuppressWarnings("unchecked")
protected int compare(T t1, T t2) {
if (comparator != null) {
return comparator.compare(t1, t2);
}
return ((Comparable<? super T>) t1).compareTo(t2);
}
protected void swap(T[] array, int i, int j) {
if (i == j) {
return;
}
T temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
选择排序
首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
public class SelectionSorter<T> extends Sorter<T> {
public SelectionSorter() {}
public SelectionSorter(Comparator<? super T> comparator) {
super(comparator);
}
@Override
public void sort(T[] array) {
int length = array.length;
for (int i = 0; i < length - 1; i++) {
int max = length - i - 1;
for (int j = 0; j < length - i - 1; j++) {
if (compare(array[j], array[max]) > 0) {
max = j;
}
}
swap(array, max, length - i - 1);
}
}
}
堆排序
public class HeapSorter<T> extends Sorter<T> {
private List<T> heap;
public HeapSorter() {}
public HeapSorter(Comparator<? super T> comparator) {
super(comparator);
}
@Override
public void sort(T[] array) {
int length = array.length;
heap = new ArrayList<>();
for (T t : array) {
heap.add(t);
}
for (int i = getParent(length - 1); i >= 0; i--) {
heapify(i);
}
for (int i = length - 1; i >= 0; i--) {
swap(0, i);
array[i] = heap.remove(i);
heapify(0);
}
}
private int getParent(int i) {
return (i - 1) >>> 1;
}
private int getLeft(int i) {
return (i << 1) + 1;
}
private int getRight(int i) {
return (i + 1) << 1;
}
private void swap(int i, int j) {
if (i == j) {
return;
}
T temp = heap.get(i);
heap.set(i, heap.get(j));
heap.set(j, temp);
}
private void heapify(int i) {
int max = i;
int left = getLeft(i);
int right = getRight(i);
if (left < heap.size() && compare(heap.get(left), heap.get(max)) > 0) {
max = left;
}
if (right < heap.size() && compare(heap.get(right), heap.get(max)) > 0) {
max = right;
}
if (max != i) {
swap(max, i);
heapify(max);
}
}
}
冒泡排序
比较相邻的元素。如果第一个比第二个大，就交换它们两个。
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的。
针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对元素需要比较。
public class BubbleSorter<T> extends Sorter<T> {
public BubbleSorter() {}
public BubbleSorter(Comparator<? super T> comparator) {
super(comparator);
}
@Override
public void sort(T[] array) {
int length = array.length;
boolean finished = false;
for (int i = 0; i < length - 1 && !finished; i++) {
finished = true;
for (int j = 0; j < length - i - 1; j++) {
if (compare(array[j], array[j + 1]) > 0) {
swap(array, j, j + 1);
finished = false;
}
}
}
}
}
快速排序
在数据集之中，选择一个元素作为枢轴（pivot）元素。
分区（partition）：将所有小于枢轴的元素，都移到枢轴的左边；将所有大于枢轴的元素，都移到枢轴的右边。分区操作后，枢轴元素所处的位置就是最终排序后它所在的位置。
对枢轴元素左右两侧的两个子集，分别重复第一步和第二步（递归），直到所有子集都只剩下一个元素为止。
分区（partition）是快速排序的主要内容，步骤如下：
把枢轴元素移到末尾（如果直接选择最后一个元素作为枢轴元素，则不需要移动）。
从左到右（除了最后的枢轴元素），将小于等于枢轴的元素依次移动到数组的开头，每次移动后将 index 加 1，表示下一个小于等于枢轴的元素将要移动到的位置。
循环结束后 index 所代表的位置就是最终排序后枢轴元素所在的位置，所以将枢轴元素（末尾）与 index 处的元素交换。
public class QuickSorter<T> extends Sorter<T> {
public QuickSorter() {}
public QuickSorter(Comparator<? super T> comparator) {
super(comparator);
}
@Override
public void sort(T[] array) {
partition(array, 0, array.length - 1);
}
private void partition(T[] array, int head, int tail) {
if (head >= tail) {
return;
}
T pivot = array[tail];
int index = head;
for (int i = head; i < tail; i++) {
if (compare(array[i], pivot) <= 0) {
swap(array, i, index++);
}
}
swap(array, index, tail);
partition(array, head, index - 1);
partition(array, index + 1, tail);
}
}
插入排序
从第一个元素开始，该元素可以认为已经被排序
取出下一个元素，在已经排序的元素序列中从后向前扫描
如果该元素（已排序）大于新元素，将该元素移到下一位置
重复步骤 3，直到找到已排序的元素小于或者等于新元素的位置
将新元素插入到该位置后
重复步骤 2 - 5
public class InsertionSorter<T> extends Sorter<T> {
public InsertionSorter() {}
public InsertionSorter(Comparator<? super T> comparator) {
super(comparator);
}
@Override
public void sort(T[] array) {
int length = array.length;
for (int i = 1; i < length; i++) {
T temp = array[i];
int j = i - 1;
for (; j >= 0 && compare(array[j], temp) > 0; j--) {
array[j + 1] = array[j];
}
array[j + 1] = temp;
}
}
}
希尔排序
希尔排序是基于插入排序的以下两点性质而提出改进方法的：
插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率。
插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位。
希尔排序通过将全部元素分为几个区域来提升插入排序的性能，这样可以让一个元素可以一次性地朝最终位置前进一大步。然后算法再取越来越小的步长进行排序，算法的最后一步就是普通的插入排序，但是到了这步，需排序的数据几乎是已排好的了（此时插入排序较快）。
public class ShellSorter<T> extends Sorter<T> {
public ShellSorter() {}
public ShellSorter(Comparator<? super T> comparator) {
super(comparator);
}
@Override
public void sort(T[] array) {
int length = array.length;
int gap = 1;
while (gap < length / 3) {
gap = gap * 3 + 1;
}
for (; gap > 0; gap /= 3) {
for (int i = gap; i < length; i++) {
T temp = array[i];
int j = i - gap;
for (; j >= 0 && compare(array[j], temp) > 0; j -= gap) {
array[j + gap] = array[j];
}
array[j + gap] = temp;
}
}
}
}
归并排序
将序列每相邻两个元素进行归并操作，形成 floor(n/2) 个序列，排序后每个序列包含两个元素
将上述序列再次归并，形成 floor(n/4) 个序列，每个序列包含四个元素
重复步骤2，直到所有元素排序完毕
public class MergeSorter<T> extends Sorter<T> {
public MergeSorter() {}
public MergeSorter(Comparator<? super T> comparator) {
super(comparator);
}
@Override
public void sort(T[] array) {
merge(array, 0, array.length - 1);
}
private void merge(T[] array, int head, int tail) {
if (head >= tail) {
return;
}
int middle = (head + tail) >>> 1;
merge(array, head, middle);
merge(array, middle + 1, tail);
Object[] temp = new Object[tail - head + 1];
int i = head;
int j = middle + 1;
int index = 0;
while (i <= middle && j <= tail) {
temp[index++] = (compare(array[i], array[j]) < 0)
? array[i++]
: array[j++];
}
if (i <= middle) {
System.arraycopy(array, i, temp, index, middle - i + 1);
}
if (j <= tail) {
System.arraycopy(array, j, temp, index, tail - j + 1);
}
System.arraycopy(temp, 0, array, head, tail - head + 1);
}
}
基数排序
基数排序是一种非比较型整数排序算法，其原理是将整数按位切割，然后按每个位数分别比较。
public class RadixSorter<T> extends Sorter<T> {
public RadixSorter() {}
@Override
public void sort(T[] arr) {
if (!(arr instanceof Integer[])) {
throw new IllegalArgumentException("只能对非负整数排序");
}
Integer[] array = (Integer[]) arr;
int length = array.length;
int digit = getDigit(array);
for (int count = 0; count < digit; count++) {
Integer[][] bucket = new Integer[10][length];
for (int i = 0; i < length; i++) {
int j = array[i] / pow(count) % 10;
int k = 0;
while (bucket[j][k] != null) {
k++;
}
bucket[j][k] = array[i];
}
for (int i = 0, j = 0; j < 10; j++) {
int k = 0;
while (bucket[j][k] != null) {
array[i++] = bucket[j][k++];
}
}
}
}
@Override
public void setComparator(Comparator<? super T> comparator) {
throw new IllegalArgumentException("只能以自然顺序排序");
}
@Override
public void sort(T[] array, Comparator<T> comparator) {
throw new IllegalArgumentException("只能以自然顺序排序");
}
private int getDigit(Integer[] array) {
int maxIndex = 0;
for (int i = 0; i < array.length; i++) {
if (array[i] < 0) {
throw new IllegalArgumentException("只能对非负整数排序");
}
if (array[i] > array[maxIndex]) {
maxIndex = i;
}
}
int digit = 1;
Integer max = array[maxIndex];
while ((max /= 10) > 0) {
digit++;
}
return digit;
}
private int pow(int count) {
int result = 1;
for (int i = 0; i < count; i++) {
int a = result << 1;
int b = result << 3;
result = a + b;
}
return result;
}
}
测试用例
public class SorterTest {
private final int length = 100;
private Integer[] array = new Integer[length];
private Integer[] actuals = null;
private Sorter<Integer> sorter = null;
private Comparator<Integer> comparator = null;
@Rule
public ExpectedException expectedException = ExpectedException.none();
@Before
public void setUp() {
sorter = new ShellSorter<>();
Random random = new Random();
for (int i = 0; i < length; i++) {
array[i] = random.nextInt(length);
}
actuals = Arrays.copyOf(array, length);
comparator = new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2 - o1;
}
};
}
@Test
public void testSort_Comparable() {
Arrays.sort(actuals);
sorter.sort(array);
Assert.assertArrayEquals(array, actuals);
}
@Test
public void testSort_Comparator() {
if (sorter instanceof RadixSorter) {
expectedException.expect(IllegalArgumentException.class);
expectedException.expectMessage("只能以自然顺序排序");
}
Arrays.sort(actuals, comparator);
sorter.sort(array, comparator);
Assert.assertArrayEquals(array, actuals);
}
}
复杂度和稳定性
| 排序算法 | 时间复杂度 | 空间复杂度 | 稳定性 | 复杂性 | ||
| 平均 | 最好 | 最坏 | ||||
| 选择排序 | O(n2) | O(n2) | O(n2) | O(1) | 不稳定 | 简单 |
| 堆排序 | O(nlog2n) | O(nlog2n) | O(nlog2n) | O(1) | 不稳定 | 复杂 |
| 冒泡排序 | O(n2) | O(n) | O(n2) | O(1) | 稳定 | 简单 |
| 快速排序 | O(nlog2n) | O(nlog2n) | O(n2) | O(log2n) | 不稳定 | 复杂 |
| 插入排序 | O(n2) | O(n) | O(n2) | O(1) | 稳定 | 简单 |
| 希尔排序 | O(n1.3) | O(n) | O(n2) | O(1) | 不稳定 | 复杂 |
| 归并排序 | O(nlog2n) | O(nlog2n) | O(nlog2n) | O(n) | 稳定 | 复杂 |
| 基数排序 | O(d(n+r)) | O(d(n+r)) | O(d(n+r)) | O(r) | 稳定 | 复杂 |