java进阶- 经典排序（插入排序、冒泡排序、快排（分划交换排序）、直接选择排序、堆排序、合并排序）
版权声明：本文为博主原创文章，未经博主允许不得转载。 https://blog.csdn.net/weixin_40254498/article/details/79205834 业余时间学习java，回顾回顾经典算法。 插入排序 代码 运行结果 冒泡排序 代码 运行结果 快速排序 代码 运行结果 插入排序 插入排序的基本思想是：每步将一个待排序的记录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。 —— [ 百度百科 ] 代码 /** * 插入排序 */ public void insertSort(int[] array) { System.out.println("-----Start 插入排序-----"); System.out.println(Arrays.toString(array)); for (int i = 0; i < array.length; i++) { int j = i - 1; int temp = array[i]; while (j > -1 && temp < array[j]) { array[j + 1] = array[j]; j--; } if (temp == array[i]) { continue; } array[j + 1] = temp; } System.out.println(Arrays.toString(array)); System.out.println("-----End 插入排序-----"); } 运行结果 -----Start 插入排序----- [14, 21, 12, 5, 7] [5, 7, 12, 14, 21] -----End 插入排序----- 冒泡排序 冒泡排序算法的运作如下：（从后往前） 比较相邻的元素。如果第一个比第二个大，就交换他们两个。 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。 针对所有的元素重复以上的步骤，除了最后一个。 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。 —— [ 百度百科 ] 代码 /** * 冒泡排序（Bubble Sort） */ public void bubbleSort(int[] array) { System.out.println("-----Start 冒泡排序-----"); System.out.println(Arrays.toString(array)); int temp = 0; for (int i = array.length - 1; i > 0; --i) { for (int j = 0; j < i; ++j) { if (array[j + 1] < array[j]) { temp = array[j]; array[j] = array[j + 1]; array[j + 1] = temp; } } } System.out.println(Arrays.toString(array)); System.out.println("-----End 冒泡排序-----"); } 运行结果 -----Start 冒泡排序----- [5, 7, 12, 14, 21] [5, 7, 12, 14, 21] -----End 冒泡排序----- 快速排序 快速排序由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。 —— [ 百度百科 ] 代码 private int count = 0; /** * 快速排序（Bubble Sort） * @param array * @param l * @param r */ public void quickSort(int[] array, int l, int r) { if (l < r) { int i = l, j = r, x = array[l]; while (i < j) { // 从右向左找第一个小于x的数 while(i < j && array[j] >= x) j--; if(i < j) array[i++] = array[j]; // 从左向右找第一个大于等于x的数 while(i < j && array[i] < x) i++; if(i < j) array[j--] = array[i]; } array[i] = x; count ++; System.out.println("-----第"+count+"次快速排序-----"); System.out.println(Arrays.toString(array)); // 递归调用 quickSort(array, l, i - 1); quickSort(array, i + 1, r); } } 运行结果 int[] outOrder = {14, 21, 12, 5, 7,9,55,77,33,12,65,6}; 运行结果： -----第1次快速排序----- [6, 12, 12, 5, 7, 9, 14, 77, 33, 55, 65, 21] -----第2次快速排序----- [5, 6, 12, 12, 7, 9, 14, 77, 33, 55, 65, 21] -----第3次快速排序----- [5, 6, 9, 7, 12, 12, 14, 77, 33, 55, 65, 21] -----第4次快速排序----- [5, 6, 7, 9, 12, 12, 14, 77, 33, 55, 65, 21] -----第5次快速排序----- [5, 6, 7, 9, 12, 12, 14, 21, 33, 55, 65, 77] -----第6次快速排序----- [5, 6, 7, 9, 12, 12, 14, 21, 33, 55, 65, 77] -----第7次快速排序----- [5, 6, 7, 9, 12, 12, 14, 21, 33, 55, 65, 77] -----第8次快速排序----- [5, 6, 7, 9, 12, 12, 14, 21, 33, 55, 65, 77] Process finished with exit code 0
