开始学习第二课，排序相关的知识，以前只接触过冒泡排序，今天重新学习了其他的排序方法，记录一下。主要学习了选择排序、冒泡排序、插入排序，希尔排序和快速排序。
主要排序方法的解释，其中部分借鉴了度娘的解释，主要为子龙老师的讲解内容，感谢度娘和子龙老师。另外代码中对for循环代码进行优化，以及元素交换做出了新的思路讲解，表示很不错。这里先逐一记录各种排序方法的解释，以及代码实现。在学习排序的过程中，插入排序费了很大力气才理解老师的意思，由于水平有限全程没看到插入的过程，理解后希尔排序就相对轻松一点，最后的快速排序比较难理解，花费的时间最多，看完代码发现子龙老师的代码高度浓缩，学习了。
它的工作原理是每一次从待排序的数据中选出最小（或最大）的一个元素，存放在序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后接着放到已排序序列的后面。以此类推，直到全部待排序的数据元素排完。 选择排序是一种不稳定的排序方法，下面自己简单的写了一段代码来记录选择排序。
1 import java.util.Scanner; 2 3 public class SelectSort { 4 /** 5 * 选择排序，就是每次循环比较都得到一个最值，将其放到指定的位置，然后再循环比较剩余的序列，再次得到最值，放到新的指定位置 6 * 最后比较完成，完成排序，这就是选择排序。 7 */ 8 9 public static void main(String[] args) { 10 //获取数组 11 Scanner scan = new Scanner(System.in); 12 System.out.println("输入数组长度"); 13 int n = scan.nextInt(); 14 int[] data = new int[n]; 15 System.out.println("开始输入数组具体内容"); 16 for (int i = 0; i < n; i++) { 17 data[i] = scan.nextInt(); 18 } 19 20 //排序前 21 System.out.println("排序前"); 22 for (int i = 0; i < data.length; i++) { 23 System.out.print(data[i] + " "); 24 } 25 System.out.println(); 26 27 //选择排序 28 for (int i = 0; i < data.length-1; i++) { 29 //外层循环定义下标需要比较的范围，为0到data.length-2 30 for(int j=i+1;j<data.length;j++){ 31 //内层排序，就是拿当前位置的后面元素，一一和它进行比较，如果比它小就进行数组交换，直到比较到数组末尾 32 //升序排列 33 if(data[i]>data[j]){ 34 int temp=data[i]; 35 data[i]=data[j]; 36 data[j]=temp; 37 } 38 } 39 } 40 41 System.out.println("选择排序后"); 42 //重新打印 43 for (int i = 0; i < data.length; i++) { 44 System.out.print(data[i] + " "); 45 } 46 47 } 48 }
控制台输出结果，可以看出能正常的进行升序排列，选择排序的时间复杂度为O(n^2)。
冒泡排序是任何学习编程的人都会接触的，其排序过程是相邻元素两两进行交换，将最大的元素慢慢移动到最后或者最前面，类似冒泡的过程，因此形象的叫做冒泡排序，直接上代码。
1 import java.util.Scanner; 2 3 public class BubbleSort { 4 5 public static void main(String[] args) { 6 /** 7 * 冒泡排序，主要就是两两比较，这个是最熟悉的算法，没有之一 8 */ 9 10 //获取数组 11 Scanner scan = new Scanner(System.in); 12 System.out.println("输入数组长度"); 13 int n = scan.nextInt(); 14 int[] data = new int[n]; 15 System.out.println("开始输入数组具体内容"); 16 for (int i = 0; i < n; i++) { 17 data[i] = scan.nextInt(); 18 } 19 20 //排序前 21 System.out.println("排序前"); 22 for (int i = 0; i < data.length; i++) { 23 System.out.print(data[i] + " "); 24 } 25 System.out.println(); 26 27 //冒泡排序开始 28 for (int i = 0,len=data.length; i < len-1; i++) { 29 //外层循环为控制内层循环比较的范围，逐一压缩比较范围 30 for (int j = 0; j < len-1-i; j++) { 31 //第一次冒泡从data[0]-data[1]比较到data[len-2]-data[len-1] 32 //第二次冒泡从data[0]-data[1]比较到data[len-3]-data[len-2] 33 //... 34 //最后一次冒泡比较data[0]-data[1] 35 if(data[j]>data[j+1]){ 36 data[j]=data[j]+data[j+1]; 37 data[j+1]=data[j]-data[j+1]; 38 data[j]=data[j]-data[j+1]; 39 } 40 } 41 } 42 43 System.out.println("冒泡排序后"); 44 //重新打印 45 for (int i = 0; i < data.length; i++) { 46 System.out.print(data[i] + " "); 47 } 48 } 49 }
控制台输出结果，可以看出能正常的进行升序排列，冒泡排序的时间复杂度为O(n^2)。
插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，是一种稳定的排序方法，直接上代码。
1 import java.util.Scanner; 2 3 public class InsertSort { 4 5 public static void main(String[] args) { 6 /** 7 * 插入排序 8 * 下面例子插入排序，就在原来数组的基础上进行，先从下标1的开始，因此下标为0的直接不用排，放到新数组的第一位即可 9 * 如 4 6 1 2 3 升排序 10 * 1 先取出第一位放到新数组第一位，变成4 11 * 2 再取出第二位6，跟4进行比较，变成4 6 12 * 3 再取出第三位1，跟6比较，发现比它小，交换位置，变成4 1 6，然后1再与4比较，比4小再交换位置，变成1 4 6 13 * 4 再取出第四位2，与前面类似，它会逐渐跟6 4 比较，变成 1 2 4 6 ，然后2比1大不再变换位置 14 * 5 再取出最后一位3，与前面类似，他会逐一跟4 6进行比较，变成1 2 3 4 6 15 * 16 */ 17 18 //获取数组 19 Scanner scan = new Scanner(System.in); 20 System.out.println("输入数组长度"); 21 int n = scan.nextInt(); 22 int[] data = new int[n]; 23 System.out.println("开始输入数组具体内容"); 24 for (int i = 0; i < n; i++) { 25 data[i] = scan.nextInt(); 26 } 27 28 //排序前 29 System.out.println("排序前"); 30 for (int i = 0; i < data.length; i++) { 31 System.out.print(data[i] + " "); 32 } 33 System.out.println(); 34 35 //插入排序，其实下面初略看好像不是插入排序，其实是比较浓缩的写法感觉是 36 for (int i = 1; i < n; i++) {//从索引1的位置开始逐一取出数准备进行插入比较 37 for (int j = i; j > 0; j--) {//拿出的这个数，逐一和它前面的数字进行比较 38 if (data[j] < data[j - 1]) { 39 //交换位置，使用另一种交换方法 40 data[j] = data[j] + data[j - 1]; 41 data[j - 1] = data[j] - data[j - 1]; 42 data[j] = data[j] - data[j - 1]; 43 } else { 44 //不用交换直接跳出内层循环，后面的不需要比了 45 break; 46 } 47 } 48 } 49 System.out.println("插入排序后"); 50 //重新打印 51 for (int i = 0; i < data.length; i++) { 52 System.out.print(data[i] + " "); 53 } 54 55 } 56 }
控制台输出结果，可以看出能正常的进行升序排列，插入排序的时间复杂度为O(n^2)。
希尔排序实际上是对上面插入排序的一种优化，其引入了步长的概念，插入排序是一个一个的进行对比，希尔排序是按照步长间隔，先初步对分组的数据进行排序，然后再组合起来，虽然看上去不是排序好的，但是实际上它更加的贴近有序，参考下面代码。
import java.util.Scanner; public class ShellSort { public static void main(String[] args) { /** * 希尔排序，是在插入排序的基础上进行了优化，引入了步长的概念，以前是一个一个的插入比较，现在是按照步长来先一一比较， * 意味着比较的两个元素不一定相邻，有可能索引相隔好几个数字，希尔排序每排完一次，步长会更新为新的步长，然后按照新的步长， * 继续比较排序，最后步长变成1，完成一次完整的插入排序，这样整个希尔排序完成。 */ //获取数组 Scanner scan = new Scanner(System.in); System.out.println("输入数组的长度"); int n = scan.nextInt(); int[] data = new int[n]; System.out.println("开始输入数组的具体内容"); for (int i = 0; i < n; i++) { data[i] = scan.nextInt(); } //排序前 System.out.println("希尔排序前"); for (int i = 0; i < data.length; i++) { System.out.print(data[i] + " "); } System.out.println(); //希尔排序，引入了步长的概念 int step = n; while (step >= 1) { step = step / 2; for (int i = step; i < n; i++) {//刚开始比较以数组长度/2作为步长，从步长的索引位置开始，往后开始比较 for (int j = i; j - step >=0; j -= step) { if (data[j] < data[j - step]) { //交换位置，使用另一种交换方法 data[j] = data[j] + data[j - step]; data[j - step] = data[j] - data[j - step]; data[j] = data[j] - data[j - step]; } else { //不用交换直接跳出内层循环，后面的不需要比了 break; } } } } System.out.println("希尔排序后"); //重新打印 for (int i = 0; i < data.length; i++) { System.out.print(data[i] + " "); } } }
控制台输出结果，可以看出能正常的进行升序排列，希尔排序的时间复杂度为O(n^2)。
快速排序引入了基准数的概念，即比较的过程中都和基准数进行比较，如果基准数不是最小数，比较完后比基准数小的在左边，比基准数大的在右边，完成一次快速排序，然后再针对基准数左边的序列和右边的序列再次执行快速排序，最后完成整个排序过程。
1 public class QuickSort { 2 /** 3 * 快速排序，引入了基准数的概念，即根据基准数分成了2组，一组比基准数小，一组比基准数大。 4 * 然后再次对两个分组使用快速排序，最后完成排序过程。 5 * 排序需要遵守的规则： 6 * （1）从右边开始，逐一和基准数进行比较，如果找到比基准数小的就进行更换 7 * （2）从左边开始，逐一和基准数进行比较，如果找到比基准树大的就进行更换 8 * 举例数组 45 28 80 90 50 16 100 10 9 * 第一次排序 基准数为45 10 * 规则1执行后：10 28 80 90 50 16 100 45 11 * 规则2执行后：10 28 45 90 50 16 100 80 12 * 第二次排序，基准数还是45 13 * 规则1执行后：10 28 16 90 50 45 100 80 14 * 规则2执行后：10 28 16 45 50 90 100 80 15 * 第三次排序，基准数还是45 16 * 规则1执行后：没变，基准数右边找不到比它更小的 17 * 规则2执行后：没变，基准数左边找不到比它更大的 18 * 结束第一次快速排序，数组变成{10 28 16} 45 {50 90 100 80} 19 * 然后开始对左边和右边进行快速排序，继续执行上面的逻辑判断，很显然快速排序用到了递归的思想，因此需要写一个通用的排序方法可以反复调用 20 */ 21 22 public static void main(String[] args) { 23 int[] data=new int[]{45,28,80,90,50,16,100,10}; 24 //快速排序 25 quickSort(data,0,data.length-1); 26 for (int i = 0; i < data.length; i++) { 27 System.out.print(data[i]+" "); 28 } 29 } 30 31 /** 32 * 快速排序通用方法，参考子龙老师的代码学习 33 * @param data 需要进行快排的数组 34 * @param left 排序的范围：左边起始位置 35 * @param right 排序的范围：右边的起始位置 36 */ 37 public static void quickSort(int[] data,int left,int right){ 38 //在排序的过程中左边起始位置和右边起始位置会更新，因此需要定义变量先初始化 39 int ll=left; 40 int rr=right; 41 int base=data[left];//比较的基准数为第一个数字 42 43 //在比较的过程中，ll和rr会更新，最后当ll==rr时会停止比较 44 while(ll<rr){ 45 //从右边开始跟基准数相比，如果比它小就进行数值更换 46 while(ll<rr&&data[rr]>=base){ 47 rr--;//如果从右边开始没找到比基准数小的，查找范围继续往数组左边移动 48 } 49 //最后有两种情况，一种是找到了，一种是没找到，如果是没找到，则最终ll==rr，找到了就是ll<rr 50 if(ll<rr){ 51 //将ll和rr位置对应的数字进行更换，其中data[ll]是基准数，替换完后data[rr]就是基准数 52 int temp=data[ll]; 53 data[ll]=data[rr]; 54 data[rr]=temp; 55 //左侧已经替换完一个小的数，从被替换位置开始往后移动一位，因为下次从左侧寻找比基准数大的数，这个数已经是小的所以不需要再找 56 ll++; 57 } 58 //接着马上从左边开始跟基准数进行比较，如果比基准数大就进行更换 59 while(ll<rr&&data[ll]<=base){ 60 ll++; 61 } 62 if(ll<rr){ 63 //同上，进行更换，此时data[rr]就是基准数，与它进行更换，更换完成后data[ll]又变成了基准数 64 int temp=data[ll]; 65 data[ll]=data[rr]; 66 data[rr]=temp; 67 //跟上面类似，右侧替换完一个比基准数大的数，下次从右侧找比基准数小的数就不需要从这个位置找了，直接左边移动一位开始找 68 rr--; 69 } 70 71 } 72 73 System.out.println("比较的基准数为："+base); 74 printArray(data); 75 76 //上面循环完成后完成第一次快速排序，接下来对基准数左边和右边继续进行快速排序 77 //左边快速排序 78 if(left<ll){ 79 quickSort(data,left,ll-1); 80 } 81 //右边快速排序 82 if(right>rr){ 83 quickSort(data,ll+1,right); 84 } 85 86 } 87 88 /** 89 * 为了方法，写一个输出数组的方法 90 * @param data 91 */ 92 public static void printArray(int[] data){ 93 for (int i = 0; i < data.length; i++) { 94 System.out.print(data[i]+" "); 95 } 96 System.out.println(); 97 } 98 }
控制台输出结果，可以看出能正常的进行升序排列，快速排序的时间复杂度糟糕情况下为O(n^2)。
以上为常见的5种排序算法，有些理解还不是很透，需要再学习理解，后续的几种排序算法以后补充添加。
参考博客：
（1）https://www.cnblogs.com/shen-hua/p/5424059.html
原文：https://www.cnblogs.com/youngchaolin/p/11097567.html