冒泡排序，选择排序，插入排序，希尔排序，基数排序，堆排序代码分析（归并排序和快速排序后续更新）

所有的算法都是这样，算法思想最重要，其次是实现过程，最后才是实现的代码

上战伐谋，我们只要明确了其算法思想和实现过程，所有算法都是纸老虎，所有算法题都是纸老虎

笔者才疏学浅，也算是刚刚接触算法，暂时总结不出思想，但是笔者相信只要坚持下去，总有一天一定可以领悟到

冒泡排序和选择排序

手撕冒泡排序和选择排序

之前写的这篇博客讲的很清楚了，这里只展示代码

public static void bubbleSort(int[] arr){for(int j = 0; j<arr.length; j++){for(int i = 0;i<arr.length - 1; i++) {// 唯一需要注意的点，循环n-1次，让i+1遍历到数组末尾即可if(arr[i+1] > arr[i]) {int temp = arr[i];arr[i] = arr[i+1];arr[i+1] = arr[i];}}}
}

public static void selectSort(int[] arr){for (int i = 0; i < arr.length; i++) {// 假设第一个是最小的，所以当然minIndex = iint min = arr[i];int minIndex = i;// 内层抓数字和未排好的数字序列的第一个数字进行比较，下标当然从i+1开始for (int j = i + 1; j < arr.length; j++) {if (arr[j] < min) {// 替换新的minmin = arr[j];// 记录更小数字的下标minIndex = j;}}// 普通交换/*int temp = arr[i];arr[i] = arr[minIndex];arr[minIndex] = temp;*/// 进阶交换，我们发现arr[minIndex] = min，所以不需要再定义一个中间变量temp// 同时，arr[i]只有一份，所以不能先辅助arr[i]arr[minIndex] = arr[i];arr[i] = min;}}
}

插入排序

插入排序，不断插入后续数字并且保证有序性，所以被称为插入排序

要点：

1. 默认第一个数字有序，逐渐递增有序序列
2. 内层循环实际上是冒泡排序的倒排

 public static void insertSort(int[] arr) {// 因为默认第一个数字有序，所以i从1开始，i指针循环n-1次for (int i = 1; i < arr.length; i++) {// j从i开始，逐渐向后移动// 因为比较的是arr[j]和arr[j-1]，所以j要>=1 for (int j = i; j >= 1; j--) {// 如果arr[j]前一个数字比arr[j]大，就交换位置if (arr[j] < arr[j - 1]) {int temp = arr[j];arr[j] = arr[j - 1];arr[j - 1] = temp;}}}}

希尔排序

插入排序存在插入的小数字越小，位置越靠后，后移的次数越多的问题，实际上会形成很多多余的交换位置

希尔排序就是为了解决这个问题而诞生的，在**“最后的交换”**之前，先让大数字尽可能往后移动，小数字尽可能往前移动

这里的**“最后的交换”**，实际上就是插入排序

是的，你没听错，希尔排序的最后一轮交换，实际上就是插入排序

希尔排序运用了分组的思想

先分成n/2组，然后是n/4……最后step = 1时，就是插入排序

public static void shellSort(int[] arr) {int step = arr.length / 2;// 只要步长不是0，就一直循环while (step != 0) {// i指针先从步长位置开始循环for (int i = step; i < arr.length; i++) {// 比较arr[j]和arr[j+step]的大小，保证组内有序for (int j = i - step; j >=0; j--) {if (arr[j] > arr[j + step]) {int temp = arr[j];arr[j] = arr[j + step];arr[j + step] = temp;}}}// 每次循环步长减半step /= 2;}}

基数排序

又叫桶排序

排序方法很简单，就是先比较数字的个位，然后比较十位，比较百位……，最后就能排号序

但是实现起来比较复杂，有很多需要注意的细节

个人认为，八大排序里面，除了快排和归并，其次最难写的就是基数排序

public static void bucketSort(int[] arr) {int max = arr[0];for (int ele : arr) {max = Math.max(ele, max);}int maxLength = ("" + max).length();// 1. 先定义好0~9十个桶,桶高是数组的长度int[][] baseBucket = new int[10][arr.length];// 2. 桶计数器int[] bucketCount = new int[10];for (int m = 1; m <= maxLength; m++) {int m1 = 1;// 循环数组获取个位数据，放到桶中for (int i = 0; i < arr.length; i++) {// 求余数int left = (arr[i] / m1) % 10;// 查询目前桶中本列下一个插入位置int height = bucketCount[left];// 插入baseBucket[left][height] = arr[i];// 桶计数器+1bucketCount[left] = ++bucketCount[left];}m1 = m1 * 10;// 下策：遍历二维数组取出数字// 上策：遍历桶计数器,不等于0就放进arrint i = 0;for (int j = 0; j < 10; j++) {if (bucketCount[j] != 0) {for (int k = 0; k < bucketCount[j]; k++) {arr[i] = baseBucket[j][k];i++;}// 下策：新创建一个桶计数器// 上策：清空桶计数器// 用完就清空bucketCount[j] = 0;}}}}

堆排序

堆排序（排序思想+排序流程+代码）

这篇博客写的很清楚了，这里只展示代码

public static void heapSort(int[] arr) {for (int p = arr.length; p >= 0; p--) {sort(arr, p, arr.length);}for (int i = arr.length - 1; i > 0; i--) {int temp = arr[0];arr[0] = arr[i];arr[i] = temp;sort(arr, 0, i);}}public static void sort(int[] arr, int parent, int length) {int maxChild = 2 * parent + 1;while (maxChild < length) {int rightChild = maxChild + 1;if (rightChild < length && arr[rightChild] > arr[maxChild]) {maxChild = rightChild;}if (arr[parent] < arr[maxChild]) {int temp = arr[parent];arr[parent] = arr[maxChild];arr[maxChild] = temp;parent = maxChild;maxChild = 2 * maxChild + 1;} else {break;}}}