【算法】八大排序算法
注：
1）本文的所有图解均来自百度图片搜索，侵删
2）代码使用java编写
3）本文主要用于记录我对排序算法的理解，若有错误，望指出
1、冒泡排序
思路
1）每次循环中，比较相邻的两个数，大的往下沉，那么一轮循环后，最大的数就放在最后了
2）由于上一次循环，已经把最大的数沉到最后了，因此下一次循环的需要比较的元素个数就减1
3）直至需要比较的元素个数为0
图解
冒泡排序
代码实现
public static void bubleSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
// 每次循环次数n，每次都比上一次少排一次
for (int e = arr.length - 1; e > 0; e--) {
for (int i = 0; i < e; i++) {
if (arr[i] > arr[i + 1]) {
int tmp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = tmp;
}
}
}
}
2、直接选择排序
思路
对于n次循环，每一次循环都把最小的数，交换到最前面的位置
图解
直接选择排序
代码实现
public static void selectionSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
for(int i = 0; i < arr.length - 1; i++) {
// 默认认为第一个数为最小的index
int minIndex = i;
for(int j = i + 1; j < arr.length; j++) {
if (arr[minIndex] > arr[j]) {
// 比较更新最新的index
minIndex = j;
}
}
// 不相同就交换
if (minIndex != i) {
int tmp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = tmp;
}
}
}
3、直接插入排序
思路
从0开始，逐步从0~arr.length的区域插入一个数，使得原来的数组有序
图解
直接插入排序
代码实现
public static void insertSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
for(int i = 1; i < arr.length; i++) {
// 每次子循环中，j代表当前有序数组中，最大的index
// 因此插入一个数，都要与最大的index，比较交换，直至这个数放在了正确的位置
for(int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
int tmp = arr[j + 1];
arr[j + 1] = arr[j];
arr[j] = tmp;
}
}
}
4、希尔排序
希尔排序也是一种插入排序，是改进后插入排序，也称为缩小增量排序
思路
1） 对数组，按一定的增量gap分组
2）分别对分组进行直接插入排序
3）直至增量gap减少至0，整个排序完成
图解
希尔排序
代码实现
public static void shellSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
for (int gap = arr.length / 2; gap > 0; gap /= 2) {
// 开始对每个分组进行直接插入排序
for(int i = gap; i < arr.length; i++) {
int j = i;
// 从gap元素开始，逐个对其所在组进行直接插入排序
while(j - gap >= 0 && arr[j] < arr[j - gap]) {
int tmp = arr[j - gap];
arr[j - gap] = arr[j];
arr[j] = tmp;
j -= gap;
}
}
}
}
5、桶排序-计数排序，基数排序
计数排序
思路
1）例如：在0~99的范围内，我们划分了100个桶，并且对桶进行编号
2）在遍历过程中，把每个数放在对应的桶里，那么一次遍历后，每个桶就各自装有其范围的数了，因此时间复杂度只要O(N)
3）最后遍历桶，“倒出”里面装有的数字
图解
计数排序
代码实现
/// 只考虑>0的情况
public static void bucketSort(int arr[]) {
int max = Integer.MIN_VALUE;
for (int i = 0; i < arr.length; i++) {
max = Math.max(max, arr[i]);
}
// 准备桶，确保桶可以装完所有数据
// 这样bucket[num]就代表num出现的次数
int[] bucket = new int[max + 1];
for(int i = 0; i < arr.length; i++) {
bucket[arr[i]]++;
}
int i = 0;
// 把桶里面的数据一次倒出来
for (int j = 0; j < bucket.length; j++) {
while (bucket[j] > 0) {
arr[i++] = j;
bucket[j]--;
}
}
}
基数排序
思路
1）将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。
2）然后，从最低位开始，依次进行一次排序。
3）这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列
图解
基数排序
代码实现
public static void sort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
// 求最大数，获得数组中最大的位数
int max = Integer.MIN_VALUE;
for(int i = 0; i < arr.length; i++) {
max = Math.max(arr[i], max);
}
int maxbits = 0;
while(max != 0) {
max /= 10;
maxbits++;
}
radixSort1(arr, maxbits);
}
public static void radixSort1(int[] arr, int maxbits) {
int max = 1;
int n = 1;
while(n != maxbits) {
max *= 10;
n++;
}
n = 1;
// 一个二维数组[i][j]，i表示位数，j是其对应的个数
int[][] bucket = new int[10][arr.length];
// 用于保存每个位数的在bucket数组中的个数
int[] count = new int[10];
while(n <= max) {
for(int i = 0; i < arr.length; i++) {
// 取得n位的位数，例如n=1，取个位数，n=2，取十位数
int digit = (arr[i] / n) % 10;
// 放进对应的桶里
bucket[digit][count[digit]] = arr[i];
// 该位数的计数+1
count[digit]++;
}
int k = 0;
for(int i = 0; i < bucket.length; i++) {
// 表示这个桶里有数据
if(count[i] != 0) {
// 全部倒出来
for(int j = 0; j < count[i]; j++) {
arr[k++] = bucket[i][j];
}
}
// 归零
count[i] = 0;
}
n *= 10;
}
}
桶排序的扩展
相邻最大差值问题，详文见
https://www.jianshu.com/p/e507609ba606
6、堆排序
堆排序需要了解堆的概念，构建堆，调整堆等概念，因此独立写了一份blog。地址如下：
https://www.jianshu.com/p/6513de30c887
7、快速排序
同样地，我也单独写了一篇blog，文中还提到了快排的优化。地址如下：
https://www.jianshu.com/p/9494a3ba1555
8、归并算法
也是单独写了一篇blog，文中提到了归并排序的两个延伸算法问题。地址如下：
https://www.jianshu.com/p/bf854d8160e9
总结
最后对时间复杂度，空间复杂度，稳定性作一个总结
排序总结
