今日立春，一年之计从码字开始吧~
今年一定要更加努力呀
目录
一、前言
二、八大排序算法
三、历史文章指路
一、前言
时隔4年，我终于把八大排序算法梳理了一遍，比起大学时零零散散的学习，现在就是一个大规范，当然代码是从优秀小伙伴那里Ctrl+C过来的，就是当我复习了一遍好多年没考过的题吧，哈哈哈。
笔记里还有2018年学习的痕迹，当时还在maopao。
当然要是现杀的话，估计只能现杀maopao，菜…
二、八大排序算法
一、交换排序
1、冒泡排序
2、快速排序
二、插入排序
1、直接插入排序
2、希尔排序
三、选择排序
1、简单选择排序
2、堆排序
四、归并排序
五、基数排序
1、冒泡排序（交换排序）
public class BubbleSort { public static void main(String[] args) { int[] arr = new int[]{3, 4, 5, 7, 1, 2, 0, 3, 6, 8}; System.out.printf("排序前：" + Arrays.toString(arr) + "n"); bubbleSort(arr); System.out.printf("排序后：" + Arrays.toString(arr)); } public static void bubbleSort(int[] arr) { for (int i = 0; i < arr.length - 1; i++) { for (int j = 0; j < arr.length - 1 - i; j++) { if (arr[j] > arr[j + 1]) { int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } } }}
2、快速排序（交换排序）
public class QuickSort { public static void main(String[] args) { int[] arr = new int[]{3, 4, 5, 7, 1, 2, 0, 3, 6, 8}; System.out.printf("排序前：" + Arrays.toString(arr) + "n"); quickSort(arr, 0, arr.length - 1); System.out.printf("排序后：" + Arrays.toString(arr)); } public static void quickSort(int[] arr, int low, int high) { int i, j, temp, t; if (low > high) { return; } i = low; j = high; //temp就是基准位 temp = arr[low]; while (i < j) { //从右往左扫描，找到第一个比基准值小的元素 while (temp <= arr[j] && i < j) { j--; } //从左往右扫描，找到第一个比基准值大的元素 while (temp >= arr[i] && i < j) { i++; } //如果满足条件则交换 if (i < j) { t = arr[j]; arr[j] = arr[i]; arr[i] = t; } } //最后将基准为与i和j相等位置的数字交换 arr[low] = arr[i]; arr[i] = temp; //递归调用左半数组 quickSort(arr, low, j - 1); //递归调用右半数组 quickSort(arr, j + 1, high); }}
3、直接插入排序（插入排序）
public class InsertSort { public static void main(String[] args) { int[] arr = new int[]{3, 4, 5, 7, 1, 2, 0, 3, 6, 8}; System.out.printf("排序前：" + Arrays.toString(arr) + "n"); insertSort(arr); System.out.printf("排序后：" + Arrays.toString(arr)); } public static void insertSort(int[] arr) { for (int i = 1; i < arr.length; i++) { if (arr[i] < arr[i - 1]) { int temp = arr[i]; int j; //插入的位置 for (j = i - 1; j >= 0 && temp < arr[j]; j--) { arr[j + 1] = arr[j]; //移动数据 } arr[j + 1] = temp; //插入数据 } } }}
4、希尔排序（插入排序）
public class ShellSort { public static void main(String[] args) { int[] arr = new int[]{3, 4, 5, 7, 1, 2, 0, 3, 6, 8}; System.out.printf("排序前：" + Arrays.toString(arr) + "n"); shellSort(arr); System.out.printf("排序后：" + Arrays.toString(arr)); } public static void shellSort(int[] arr) { //step:步长 for (int step = arr.length / 2; step > 0; step /= 2) { System.out.printf("step：" + step + "n"); //对一个步长区间进行比较 [step,arr.length) for (int i = step; i < arr.length; i++) { int value = arr[i]; int j; //对步长区间中具体的元素进行比较 for (j = i - step; j >= 0 && arr[j] > value; j -= step) { //j为左区间的取值，j+step为右区间与左区间的对应值 arr[j + step] = arr[j]; } //此时step为一个负数，[j + step]为左区间上的初始交换值 arr[j + step] = value; } } }}
5、简单选择排序（选择排序）
public class SelectSort { public static void main(String[] args) { int[] arr = new int[]{3, 4, 5, 7, 1, 2, 0, 3, 6, 8}; System.out.printf("排序前：" + Arrays.toString(arr) + "n"); selectsort(arr); System.out.printf("排序后：" + Arrays.toString(arr)); } public static void selectsort(int[] arr) { for (int i = 0; i < arr.length; i++) { int min = i; //最小元素的下标 for (int j = i + 1; j < arr.length; j++) { if (arr[min] > arr[j]) { min = j; //找最小值 } } //交换位置 if (i != min) { int temp = arr[i]; arr[i] = arr[min]; arr[min] = temp; } } }}
6、堆排序（选择排序）
public class HeapSort { public static void main(String[] args) { int[] arr = new int[]{3, 4, 5, 7, 1, 2, 0, 3, 6, 8}; System.out.printf("排序前：" + Arrays.toString(arr) + "n"); heapSort(arr); System.out.printf("排序后：" + Arrays.toString(arr)); } public static void maxHeap(int[] arr, int size, int index) { //左子结点 int leftNode = 2 * index + 1; //右子结点 int rightNode = 2 * index + 2; int max = index; //和两个子结点分别对比，找出最大的结点 if (leftNode < size && arr[leftNode] > arr[max]) { max = leftNode; } if (rightNode < size && arr[rightNode] > arr[max]) { max = rightNode; } //交换位置 if (max != index) { int temp = arr[index]; arr[index] = arr[max]; arr[max] = temp; //因为交换位置后有可能使子树不满足大顶堆条件，所以要对子树进行调整 maxHeap(arr, size, max); } } public static void heapSort(int[] arr) { //开始位置是最后一个非叶子结点，即最后一个结点的父结点 int start = (arr.length - 1) / 2; //调整为大顶堆 for (int i = start; i >= 0; i--) { HeapSort.maxHeap(arr, arr.length, i); } //先把数组中第 0 个位置的数和堆中最后一个数交换位置，再把前面的处理为大顶堆 for (int i = arr.length - 1; i > 0; i--) { int temp = arr[0]; arr[0] = arr[i]; arr[i] = temp; maxHeap(arr, i, 0); } }}
7、归并排序
public class MergeSort { public static void main(String[] args) { int[] arr = new int[]{3, 4, 5, 7, 1, 2, 0, 3, 6, 8}; System.out.printf("排序前：" + Arrays.toString(arr) + "n"); mergeSort(arr, 0, arr.length - 1); System.out.printf("排序后：" + Arrays.toString(arr)); } public static void merge(int[] arr, int low, int middle, int high) { // 用于存储归并后的临时数组 int[] temp = new int[high - low + 1]; // 记录第一个数组中需要遍历的下标 int i = low; // 记录第二个数组中需要遍历的下标 int j = middle + 1; // 记录在临时数组中存放的下标 int index = 0; // 遍历两个数组，取出小的数字，放入临时数组中 while (i <= middle && j <= high) { // 第一个数组的数据更小 if (arr[i] <= arr[j]) { // 把更小的数据放入临时数组中 temp[index] = arr[i]; // 下标向后移动一位 i++; } else { temp[index] = arr[j]; j++; } index++; } // 处理剩余未比较的数据 while (i <= middle) { temp[index] = arr[i]; i++; index++; } while (j <= high) { temp[index] = arr[j]; j++; index++; } // 把临时数组中的数据重新放入原数组 for (int k = 0; k < temp.length; k++) { arr[k + low] = temp[k]; } } public static void mergeSort(int[] arr, int low, int high) { int middle = (high + low) / 2; if (low < high) { // 处理左边数组 mergeSort(arr, low, middle); // 处理右边数组 mergeSort(arr, middle + 1, high); // 归并 merge(arr, low, middle, high); } }}
8、基数排序
public class RadixSort { public static void main(String[] args) { int[] arr = new int[]{3, 4, 5, 7, 1, 2, 0, 3, 6, 8}; System.out.printf("排序前：" + Arrays.toString(arr) + "n"); radixSort(arr); System.out.printf("排序后：" + Arrays.toString(arr)); } public static void radixSort(int[] arr) { // 存放数组中的最大数字 int max = Integer.MIN_VALUE; for (int value : arr) { if (value > max) { max = value; } } // 计算最大数字是几位数 int maxLength = (max + "").length(); // 用于临时存储数据 int[][] temp = new int[10][arr.length]; // 用于记录在 temp 中相应的下标存放数字的数量 int[] counts = new int[10]; // 根据最大长度的数决定比较次数 for (int i = 0, n = 1; i < maxLength; i++, n *= 10) { // 每一个数字分别计算余数 for (int j = 0; j < arr.length; j++) { // 计算余数 int remainder = arr[j] / n % 10; // 把当前遍历的数据放到指定的数组中 temp[remainder][counts[remainder]] = arr[j]; // 记录数量 counts[remainder]++; } // 记录取的元素需要放的位置 int index = 0; // 把数字取出来 for (int k = 0; k < counts.length; k++) { // 记录数量的数组中当前余数记录的数量不为 0 if (counts[k] != 0) { // 循环取出元素 for (int l = 0; l < counts[k]; l++) { arr[index] = temp[k][l]; // 记录下一个位置 index++; } // 把数量置空 counts[k] = 0; } } } }}
相关代码都在Learn-Java，请阅。
https://gitee.com/weimenghua/Learn-Java.git
三、历史文章指路
关注【嘎嘎软件测试】
搞测试，不迷路
呱呱大王本呱带你飞！
嘎嘎软件测试
本账号将分享个人成长、团队管理、软件测试技能知识等内容，更新频率一周两篇，做到有思想、有观点、有深度，欢迎订阅。