内部排序算法的 JAVA 实现 - 基础

本文整理了【冒泡】、【选择】、【插入】、【快排】四种最基础的排序算法.。

冒泡排序

冒泡排序（Bubble Sort）是一种稳定的排序算法，它每次比较相邻的两个元素并将其按序排列。

冒泡排序的思想：

1. 比较相邻的元素，如果前一个比后一个大，就把它们两个调换位置。
2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
3. 针对所有的元素重复以上的步骤，除了最后一个。
4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

下图为冒泡排序的示意图

下面为冒泡排序的实现代码

public <T extends Comparable<T>> void bubbleSort(T[] array) {
boolean swapped = true;
for (int i = 0; i < array.length && swapped; i++) {
swapped = false;
for (int j = 0; j < array.length - i - 1; j++) {
if (array[j].compareTo(array[j + 1]) > 0) {
T temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
swapped = true;
}
}
}
}

冒泡排序的复杂度

平均	最好	最坏	空间复杂度
O(n^2)	O(n)	O(n^2)	O(1)

选择排序

选择排序(Selection sort)是一种不稳定的排序算法。做法是首先在未排序序列中找到最小元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小元素，然后放到排序序列末尾。以此类推，直到所有元素均排序完毕。

选择排序的思想：

每次从无序序列选取最小的放到指定位置。
下图为选择排序的示意图

下面为选择排序的实现代码

public <T extends Comparable<T>> void selectSort(T[] array) {
if (array == null || array.length < 2) {
return;
}
for (int i = 0; i < array.length; i++) {
int k = i;
for (int j = i + 1; j < array.length; j++) {
if (array[j].compareTo(array[k]) < 0) {
k = j;
}
}
if (i != k) {
T temp = array[k];
array[k] = array[i];
array[i] = temp;
}
}
}

选择排序的复杂度

平均	最好	最坏	空间复杂度
O(n^2)	O(n^2)	O(n^2)	O(1)

插入排序

插入排序（Insertion Sort）的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

插入排序的思想：

1. 从第一个元素开始，该元素可以认为已经被排序
2. 取出下一个元素，在已经排序的元素序列中从后向前扫描
3. 如果该元素（已排序）大于新元素，将该元素移到下一位置
4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
5. 将新元素插入到该位置中
6. 重复步骤2

下图为插入排序的示意图

下面为插入排序的实现代码

public <T extends Comparable<T>> void insertSort(T[] array) {
if (array == null || array.length < 2) {
return;
}
for (int i = 1; i < array.length; i++) {
T ptr = array[i];
int j = i - 1;
while (j >= 0 && ptr.compareTo(array[j]) < 0) {
array[j + 1] = array[j];
j--;
}
array[j + 1] = ptr;
}
}

插入排序的复杂度

平均	最好	最坏	空间复杂度
O(n^2)	O(n)	O(n^2)	O(1)

快速排序

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

快速排序的思想

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

下图为快速排序的示意图


下面为快速排序的实现代码

public class QuickSort {
private static int partition(int data[], int low, int high) {// 分治
int key = data[low];
while (low < high) {
while (low < high && data[high] > key)// 从右向左
high--;
data[low] = data[high];

while (low < high && data[low] < key)// 从左向右
low++;
data[high] = data[low];
}
data[low] = key;// 把轴元素放在轴所在地位置
return low;// 返回轴所在的位置
}

private static void quickSort(int data[], int low, int high) {// 递归
int q;
if (low < high) {
q = partition(data, low, high);
quickSort(data, q + 1, high);
quickSort(data, low, q - 1);
}
}

public static void main(String args[]) {
int a[] = new int[] { 33, 102, 27, 4, 104, 48, 18, 64, 153, 77, 72, 45, 24, 53, 6, 81, 3 };
quickSort(a, 0, a.length - 1);
}
}

快速排序的复杂度

平均	最好	最坏	空间复杂度
O(nlgn)	O(nlgn)	O(n^2)	O(1)