冒泡排序
基本思路
- 比较相邻两个元素，如果第一个比第二个大，就交换它们两个；
- 对每一组相邻元素做同样的工作，从开始第一对到结尾最后一对，每次都把相对较大的元素放到后面，看上去就像当前最大的元素“冒”到了后面；
- 重复上述步骤，每次排序都确定一个数的顺序，直到 N 次遍历后完成排序。
代码实现
public void bubbleSort(int[] arr) {
for(int i = 0; i < arr.length; i++) {
// 每一轮都把前 arr.length-1-i 中最大的数放到当前最后一个位置上
for(int j = 0; j < arr.length-1-i; j++) {
// 如果前一个数大于后一个数，则交换它们两个
if(arr[j] > arr[j+1]) {
swap(arr, j, j+1);
}
}
}
}
复杂度分析
- 时间复杂度 ：
T(n) = O(n^2) - 空间复杂度 ：
S(n) = O(1)
补充
使用改进冒泡排序的话，时间复杂度可能达到 O(n)；示例代码如下 ：
public void bubbleSort(int[] arr) {
for(int i = 0; i < arr.length; i++) {
// 是否交换过顺序
boolean didSwap = false;
for(int j = 0; j < arr.length-1-i; j++) {
if(arr[j] > arr[j+1]) {
swap(arr, j, j+1);
didSwap = true;
}
}
// 若这轮执行下来发现没做过交换，说明此时已经是排好序的了
if(!didSwap) {
return;
}
}
}
选择排序
基本思路
- 将整个数组分为“已排序”和“未排序”两个部分；
- 每次遍历找到最小的元素，然后将它放入“已排序”部分的末尾；
- 这样经过 N 遍历，所有的元素就都在“已排序”的部分啦。
代码实现
public void selectionSort(int[] arr){
for(int i = 0; i < arr.length; i++) {
// i 指向有序区末尾，index 是当前最小值的下标
int index = i;
for(int j = i; j < arr.length; j++) {
if(arr[j] < arr[index]) {
index = j;
}
}
// 将无序区的最小值放入有序区末尾
swap(arr, i, index);
}
}
复杂度分析
- 时间复杂度 ：
T(n) = O(n^2) - 空间复杂度 ：
S(n) = O(1)
插入排序
基本思路
- 将整个数组分为“已排序”和“未排序”两个部分；
- 每次从“未排列”部分取一个数，按顺序插入“已排序”部分；
- 这样经过 N 遍历，所有的元素就都在“已排序”的部分啦。
代码实现
public void insertSort(int[] arr) {
for(int i = 0; i < arr.length-1; i++) {
// 取无序部分的第一个元素
int cur = arr[i+1];
// index 指向有序部分的最后一个元素
int index = i;
// 依次移动有序部分的元素，直到找到 cur 应在的位置
while(index >= 0 && cur < arr[index]) {
arr[index+1] = arr[index--];
}
arr[index+1] = cur;
}
}
复杂度分析
- 时间复杂度 ：
- 最佳情况 ：
T(n) = O(n) - 最坏情况 ：
T(n) = O(n^2) - 平均情况 ：
T(n) = O(n^2)
- 最佳情况 ：
- 空间复杂度 ：
S(n) = O(1)
希尔排序
基本思路
希尔排序是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序。与简单插入排序不同，希尔排序会优先比较距离较远的元素。
动图演示如下 ：
代码实现
public void shellSort(int[] arr) {
int gap = arr.length / 2;
while(gap > 0) {
// 这其实就是一个希尔排序，这只是将间隔由 “1” 变成了 “gap”
for(int i = 0; i < arr.length-gap; i++) {
int cur = arr[i + gap];
int index = i;
while(index >= 0 && cur < arr[index]) {
arr[index + gap] = arr[index];
index -= gap;
}
arr[index + gap] = cur;
}
gap /= 2;
}
}
复杂度分析
- 时间复杂度 ：
- 最佳情况 ：
T(n) = O(n) - 最坏情况 ：
T(n) = O(n^2) - 平均情况 ：
T(n) = O(n^1.3)
- 最佳情况 ：
- 空间复杂度 ：
S(n) = O(1)
归并排序
基本思路
- 将长度为 n 的输入序列分成两个长度为 n/2 的子序列；
- 对这两个子序列分别采用归并排序；
- 将两个排好序的子序列合并成一个最终的排序序列。
代码实现
public class MergeSort {
/**
* 采用归并的方法对无序数组进行排序
*/
public int[] MergeSort(int[] arr){
if(arr.length < 2){
return arr;
}
int mid = arr.length / 2;
// 将数组分为左右两部分
int[] left = Arrays.copyOfRange(arr, 0, mid);
int[] right = Arrays.copyOfRange(arr, mid, arr.length);
// 对左右分别进行排序，然后合并
return merge(MergeSort(left), MergeSort(right));
}
/**
* 合并两个有序数组
*/
public int[] merge(int[] left, int[] right){
int[] res = new int[left.length + right.length];
for (int index = 0, i = 0, j = 0; index < res.length; index++) {
// 前两个分支考虑的是是其中一个数组遍历完了的情况
if (i >= left.length) {
res[index] = right[j++];
} else if (j >= right.length) {
res[index] = left[i++];
// 后两个分支直接合并，谁小谁在前
} else if (left[i] < right[j]) {
res[index] = right[i++];
} else {
res[index] = left[j++];
}
}
return res;
}
}
复杂度分析
- 时间复杂度：
T(n) = O(nlog n) - 空间复杂度：
S(n) = O(n)
快速排序
基本思路
- 从数列中挑出一个元素作为“基准数”，一般挑选左边第一个；
- 从后半部分向前扫描，直到找到第一个比 mark 小的数，记为 A，从前半部分向后扫描，直到找到第一个比 mark 大的数，记为 B，交换 A、B；
- 重复步骤 2，直到 left 与 right 相遇，交换基准数与相遇点，则本次“分区”结束；
- 在分区结束后，该基准就处于数列的中间位置；将其左右分别视为两个新数列，递归地进行再分区，直到每个区域只有一个元素，排序就完成了。
代码实现
public class QuickSort {
public void QuickSort(int[] arr, int left, int right){
if (left < right) {
// 对数列进行分区，并获取上一个基准数的下标，也就是这一次操作的分区线
int partition = partition(arr, left, right);
// 对左边递归排序
QuickSort(arr, left, partition-1);
// 对右边递归排序
QuickSort(arr, partition+1, right);
}
}
public int partition(int[] arr, int left, int right){
// 选择范围内的第一个为基准数
int mark = arr[left];
while (left < right) {
// 从后半部分向前扫描，直到找到第一个比 mark 小的数，记为 A
while (left < right && arr[right] >= mark) right--;
arr[left] = arr[right];
// 从前半部分向后扫描，直到找到第一个比 mark 大的数，记为 B
while (left < right && arr[left] <= mark) left++;
// 这句联系上句，其实起到的是一个交换 A、B 的作用
arr[right] = arr[left];
}
arr[left] = mark;
return left;
}
}
复杂度分析
- 时间复杂度：
- 最佳情况：
T(n) = O(nlog n) - 最差情况：
T(n) = O(n^2) - 平均情况：
T(n) = O(nlog n)
- 最佳情况：
- 空间复杂度：
- 平均：
S(n) = O(log n) - 最差：
S(n) = O(n)
- 平均：
堆排序
基本思路
- 将待排序的数列构造成一个大顶堆（或小顶堆），整个序列的最大值（或最小值）就是堆顶的根节点；
- 将根节点的值和堆数组的末尾元素交换，此时末尾元素就是最大值（或最小值）；
- 将剩余的 n-1 个序列重新构造成一个堆，这样就会得到 n 个元素中的次大值（或次小值），如此反复执行，最终就能得到一个有序序列。
代码实现
public class HeapSort {
/**
* 构造/调整最大堆
*/
public void heapAdjust(int[] arr, int index, int length){
// 保存当前结点的下标
int max = index;
// 当前节点左子节点的下标
int lchild = 2*index;
// 当前节点右子节点的下标
int rchild = 2*index + 1;
if(length > lchild && arr[max] < arr[lchild]){
max = lchild;
}
if(length > rchild && arr[max] < arr[rchild]){
max = rchild;
}
// 若此节点比其左右孩子的值小，就将其和最大值交换，并调整堆
if(max != index){
swap(arr, index, max);
heapAdjust(arr, max, length);
}
}
/**
* 堆排序
*/
public int[] heapSort(int[] arr) {
int len = arr.length;
// 初始化堆，构造一个最大堆
for (int i = (len / 2 - 1); i >= 0; i--) {
heapAdjust(arr, i, len);
}
for (int i = len-1; i > 0; i--) {
// 将堆顶的元素和最后一个元素交换，并重新调整堆
swap(arr, 0, i);
heapAdjust(arr, 0, i);
}
return arr;
}
}
复杂度分析
- 时间复杂度：
T(n) = O(nlog n) - 空间复杂度：
S(n) = O(1)
计数排序
基本思路
计数排序不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，它要求输入的数据必须是有确定范围的整数。
代码实现
public class CountingSort {
/**
* 计数排序
* @param arr 该数组中存放的数据都在已知范围内
* @param max 范围的最大值
* @param min 范围的最小值
*/
public static void countingSort(int[] arr, int max, int min){
// 偏差
int bias = 0 - min;
// 新开辟一个数组，并将数据按下标依次存入新数组
int[] bucket = new int[max - min +1];
for (int i = 0; i < arr.length; i++) {
bucket[arr[i] + bias]++;
}
// 将新数组中的数据依次取出，再放回原数组
int index = 0;
for (int i = 0; i < bucket.length; i++){
int len = bucket[i];
while (len-- > 0) {
arr[index++] = i - bias;
}
}
}
}
复杂度分析
当输入的元素是 n 个 0 到 k 之间的整数时，
- 时间复杂度：
T(n) = O(n+k) - 空间复杂度：
S(n) = O(k)
桶排序
基本思路
桶排序是计数排序的升级版，其原理在于 ：
假设输入数据服从均匀分布，将数据分配到有限数量的桶里，每个桶再分别排序（可以是使用别的排序算法，或是以递归方式继续使用桶排序）。
代码实现
public class BucketSort {
public static ArrayList<Integer> bucketSort(ArrayList<Integer> array, int bucketSize) {
if (array == null || array.size() < 2)
return array;
int max = array.get(0), min = array.get(0);
// 找到最大值最小值
for (int i = 0; i < array.size(); i++) {
if (array.get(i) > max)
max = array.get(i);
if (array.get(i) < min)
min = array.get(i);
}
// 桶数量
int bucketCount = (max - min) / bucketSize + 1;
ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketCount);
ArrayList<Integer> resultArr = new ArrayList<>();
// 构造桶
for (int i = 0; i < bucketCount; i++) {
bucketArr.add(new ArrayList<>());
}
// 将元素装入桶中
for (int i = 0; i < array.size(); i++) {
bucketArr.get((array.get(i) - min) / bucketSize).add(array.get(i));
}
// 依次对桶中元素进行排序
for (int i = 0; i < bucketCount; i++) {
if (bucketSize == 1) {
resultArr.addAll(bucketArr.get(i));
} else {
if (bucketCount == 1) {
bucketSize--;
}
// 这里是采用的递归的方法进行排序
ArrayList<Integer> temp = bucketSort(bucketArr.get(i), bucketSize);
resultArr.addAll(temp);
}
}
return resultArr;
}
}
复杂度分析
桶排序的时间复杂度，取决与对各个桶之间数据进行排序的时间复杂度，因为其它部分的时间复杂度都为O(n)。显然，桶划分的越小，各个桶之间的数据越少，排序所用的时间也会越少，但相应的空间消耗就会增大。
当输入的元素是 n 个 0 到 k 之间的整数，一共划分 m 个桶时，
- 时间复杂度：
- 最佳情况：
T(n) = O(n+k) - 最差情况：
T(n) = O(n^2) - 平均情况：
T(n) = O(n+k)
- 最佳情况：
- 空间复杂度：
S(n) = O(n+m)
基数排序
基本思路
- 取得数组中的最大数，并取得该数的位数；
- arr 为原始数组，从最低位开始取每个位组成 radix 数组；
- 利用计数排序适用于小范围数的特点，分别在每个位上对 radix 进行计数排序。
代码实现
public class RadixSort {
public void RadixSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
// 首先计算出最大数的位数
int max = arr[0];
for (int i = 1; i < arr.length; i++) {
max = Math.max(max, arr[i]);
}
int maxDigit = 0;
while (max != 0) {
max /= 10;
maxDigit++;
}
int mod = 10, div = 1;
// 然后对每一位进行计数排序
ArrayList<ArrayList<Integer>> bucketList = new ArrayList<>();
for(int i = 0; i < 10; i++) {
bucketList.add(new ArrayList<>());
}
for(int i = 0; i < maxDigit; i++, mod *= 10 , div *= 10){
for (int value : arr) {
int num = (value % mod) / div;
bucketList.get(num).add(value);
}
int index = 0;
for (ArrayList<Integer> integers : bucketList) {
for (Integer integer : integers) {
arr[index++] = integer;
}
integers.clear();
}
}
}
}
复杂度分析
当输入的元素是 n 个 0 到 k 之间的整数时，
- 时间复杂度：
T(n) = O(n * k) - 空间复杂度：
S(n) = O(n + k)
总结
总而言之先放一张图 ：
术语说明 ：
- 稳定 ：如果原本 a 在 b 之前，而 a = b，则排序后 a 仍在 b 前面；
- 不稳定 ：如果 a 原本在 b 前面，而 ａ = b，排序之后 a 有可能会出现在 b 的后面；
- 内排序 ：所有排序操作都在内存中完成；
- 外排序 ：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行；
- 时间复杂度 ：描述算法运行时间的函数，用大 O 符号表示；
- 空间复杂度 ：描述算法所需要的内存空间大小。
