本文主要是对冒泡排序、选择排序、插入排序的学习与总结。
冒泡排序： 是一种直观的排序算法，它重复的走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来，遍历数列的工作是重复的进行直到没有在需要交换，也就是排序完成。
冒泡排序的步骤： 1、比较相邻的元素，如果第一个比第二个大，就交换它们两个。 2、对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。这步做完，最后的元素会是最大的数。 3、针对所有的重复元素重复以上的步骤，除了最后一个。 4、持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
代码如下
public class BubbleSort { public static int[] sort(int[] array) { //表示总共需要比较多少轮 for (int i = 0; i < array.length-1; i++) { //定义一个标记，若为true，表示此次循环没有进行交换 boolean flag=true; //表示每轮排序多少次 for (int j = 0; j < array.length-i-1; j++) { //把最小的值放前面 if(array[j]>array[j+1]) { int temp=array[j]; array[j]=array[j+1]; array[j+1]=temp; flag=false; } } if(flag) { break; } //第i轮的排序结果 System.out.println("第"+i+"轮排序后的结果为："); display(array); } return array; } //遍历显示数组 public static void display(int[] array) { for (int i = 0; i < array.length; i++) { System.out.print(array[i]+" "); } System.out.println(); } public static void main(String[] args) { // TODO Auto-generated method stub int[] array= {12,34,45,67,3,4,6,7,8,45,14,25}; //未排序数组顺序为 System.out.print(array); System.out.println("------------------"); array=sort(array); System.out.println("------------------"); System.out.println("排序后的数组顺序为"); display(array); } }结果如下：
第0轮排序后的结果为： 12 34 45 3 4 6 7 8 45 14 25 67 第1轮排序后的结果为： 12 34 3 4 6 7 8 45 14 25 45 67 第2轮排序后的结果为： 12 3 4 6 7 8 34 14 25 45 45 67 第3轮排序后的结果为： 3 4 6 7 8 12 14 25 34 45 45 67 ------------------ 排序后的数组顺序为 3 4 6 7 8 12 14 25 34 45 45 67冒泡排序解释：
冒泡排序是由两个for循环构成，第一个for循环的变量 i 表示总共需要多少轮比较，第二个for循环的变量 j 表示每轮参与比较的元素下标【0,1，…，length-i】，因为每轮比较都会出现一个最大值放在最右边，所以每轮比较后的元素个数都会少一个，这也是为什么 j 的范围是逐渐减小的。相信大家理解之后快速写出一个冒泡排序并不难。
冒泡排序性能分析：
假设参与比较的数组元素个数为 N，则第一轮排序有 N-1 次比较，第二轮有 N-2 次，如此类推，这种序列的求和公式为：
（N-1）+（N-2）+…+1 = N*（N-1）/2
当 N 的值很大时，算法比较次数约为 N2/2次比较，忽略减1。
假设数据是随机的，那么每次比较可能要交换位置，可能不会交换，假设概率为50%，那么交换次数为 N2/4。不过如果是最坏的情况，初始数据是逆序的，那么每次比较都要交换位置。
交换和比较次数都和N2 成正比。由于常数不算大 O 表示法中，忽略 2 和 4，那么冒泡排序运行都需要 O(N2) 时间级别。
其实无论何时，只要看见一个循环嵌套在另一个循环中，我们都可以怀疑这个算法的运行时间为 O(N2)级，外层循环执行 N 次，内层循环对每一次外层循环都执行N次（或者几分之N次）。这就意味着大约需要执行N2次某个基本操作。
选择排序： 这是一种简单直观的排序算法，每次从待排序的数据元素中选出最小的一个元素，存放在序列的起始位置，直到数据元素排完。并且无论什么数据进去都是O(n²)的时间复杂度，所以用到它的时候，数据规模越小越好，好处是不占用额外的内存空间。
选择排序的步骤： 1、首先在未排序序列中找到最小（或最大）元素，存放到序列的起始位置。 2、再从剩余未排序的元素中继续寻找最小（大）元素，放到已排序序列的末尾。 3、重复第二步，直到所有元素排序完毕。
代码如下：
public class ChoiceSort { //从大到小 public static int[] toSmall(int[] arr) { //遍历数组里最后一个的其他所有数，因为最后的对象没有与之可以相比较的数 for (int i = 0; i < arr.length; i++) { //遍历数组里没有排序的所有数，并与上一个数进行比较 //k=i+1因为自身一定等于自身，所以比较没有意义 //前面已经排好序的数，比较也没有意义 for (int k = i+1; k < arr.length-1; k++) { if(arr[k]<arr[i]) { int num=arr[i]; arr[i]=arr[k]; arr[k]=num; } } //第i轮的排序结果 System.out.println("第"+i+"轮排序后的结果为："); display(arr); } return arr; } //从小到大 public static int[] toBig(int[] arr) { for (int i = 0; i < arr.length; i++) { for (int k = i+1; k < arr.length-1; k++) { if(arr[k]>arr[i]) { int num=arr[i]; arr[i]=arr[k]; arr[k]=num; } } //第i轮的排序结果 System.out.println("第"+i+"轮排序后的结果为："); display(arr); } return arr; } //遍历显示数组 public static void display(int[] array) { for (int i = 0; i < array.length; i++) { System.out.print(array[i]+" "); } System.out.println(); } public static void main(String[] args) { int[] arr= {3,4,1,5,9,8,7,6,12,45,15,26,28}; System.out.println("----从小到大输出----"); arr=toBig(arr); System.out.println("结果为"); display(arr); System.out.println("----从大到小输出----"); arr=toSmall(arr); System.out.println("结果为"); display(arr); } }结果如下：
----从小到大输出---- 第0轮排序后的结果为： 45 3 1 4 5 8 7 6 9 12 15 26 28 第1轮排序后的结果为： 45 26 1 3 4 5 7 6 8 9 12 15 28 第2轮排序后的结果为： 45 26 15 1 3 4 5 6 7 8 9 12 28 第3轮排序后的结果为： 45 26 15 12 1 3 4 5 6 7 8 9 28 第4轮排序后的结果为： 45 26 15 12 9 1 3 4 5 6 7 8 28 第5轮排序后的结果为： 45 26 15 12 9 8 1 3 4 5 6 7 28 第6轮排序后的结果为： 45 26 15 12 9 8 7 1 3 4 5 6 28 第7轮排序后的结果为： 45 26 15 12 9 8 7 6 1 3 4 5 28 第8轮排序后的结果为： 45 26 15 12 9 8 7 6 5 1 3 4 28 第9轮排序后的结果为： 45 26 15 12 9 8 7 6 5 4 1 3 28 第10轮排序后的结果为： 45 26 15 12 9 8 7 6 5 4 3 1 28 第11轮排序后的结果为： 45 26 15 12 9 8 7 6 5 4 3 1 28 第12轮排序后的结果为： 45 26 15 12 9 8 7 6 5 4 3 1 28 结果为 45 26 15 12 9 8 7 6 5 4 3 1 28 ----从大到小输出---- 第0轮排序后的结果为： 1 45 26 15 12 9 8 7 6 5 4 3 28 第1轮排序后的结果为： 1 3 45 26 15 12 9 8 7 6 5 4 28 第2轮排序后的结果为： 1 3 4 45 26 15 12 9 8 7 6 5 28 第3轮排序后的结果为： 1 3 4 5 45 26 15 12 9 8 7 6 28 第4轮排序后的结果为： 1 3 4 5 6 45 26 15 12 9 8 7 28 第5轮排序后的结果为： 1 3 4 5 6 7 45 26 15 12 9 8 28 第6轮排序后的结果为： 1 3 4 5 6 7 8 45 26 15 12 9 28 第7轮排序后的结果为： 1 3 4 5 6 7 8 9 45 26 15 12 28 第8轮排序后的结果为： 1 3 4 5 6 7 8 9 12 45 26 15 28 第9轮排序后的结果为： 1 3 4 5 6 7 8 9 12 15 45 26 28 第10轮排序后的结果为： 1 3 4 5 6 7 8 9 12 15 26 45 28 第11轮排序后的结果为： 1 3 4 5 6 7 8 9 12 15 26 45 28 第12轮排序后的结果为： 1 3 4 5 6 7 8 9 12 15 26 45 28 结果为 1 3 4 5 6 7 8 9 12 15 26 45 28选择排序性能分析： 选择排序和冒泡排序执行了相同次数的比较：N*（N-1）/2，但是至多只进行了N次交换。 当 N 值很大时，比较次数是主要的，所以和冒泡排序一样，用大O表示是O(N2) 时间级别。但是由于选择排序交换的次数少，所以选择排序无疑是比冒泡排序快的。当 N 值较小时，如果交换时间比选择时间大的多，那么选择排序是相当快的。
插入排序： 直接插入排序基本思想是每一步将一个待排序的记录，插入到前面已经排好序的有序数列中去，直到插完所有元素为止。 插入排序还分为直接插入排序、二分插入排序、链表插入排序，希尔排序等等，这里只讲解直接插入排序。
插入排序步骤： 1、将第一待排序序列第一个元素看作一个有序序列，把第二个元素到最后一个元素当成未排序序列。 2、从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置（如果插入的元素与有序数列的元素相等，则将带插入的元素放到相等元素的后面）。 代码如下：
public class InsertSort { public static int[] sort(int[] array) { int j; //从下标为1的元素开始选择合适的位置插入，因为下标为0的元素只有一个，默认是有序的 for (int i = 1; i < array.length; i++) { int tmp=array[i];//记录要插入的数据 j=i; while(j>0&&tmp<array[j-1]) { array[j]=array[j-1];//向后移动 j--; } array[j]=tmp; } return array; } //遍历显示数组 public static void display(int[] array) { for (int i = 0; i < array.length; i++) { System.out.print(array[i]+" "); } System.out.println(); } public static void main(String[] args) { int[] arr= {5,7,3,2,8,9,0,4,1,6}; System.out.println("未排序数组顺序为："); display(arr); System.out.println("---------------------"); arr=sort(arr); System.out.println("---------------------"); System.out.println("排序后的结果为："); display(arr); } }结果如下：
未排序数组顺序为： 5 7 3 2 8 9 0 4 1 6 --------------------- --------------------- 排序后的结果为： 0 1 2 3 4 5 6 7 8 9插入排序性能分析： 在第一轮排序中，它最多比较一次，第二轮最多比较两次，一次类推，第N轮，最多比较N-1次。因此有 1+2+3+…+N-1 = N*（N-1）/2。 假设在每一轮排序发现插入点时，平均只有全体数据项的一半真的进行了比较，我们除以2得到：N*（N-1）/4。用大O表示法大致需要需要 O(N2) 时间级别。 复制的次数大致等于比较的次数，但是一次复制与一次交换的时间耗时不同，所以相对于随机数据，插入排序比冒泡快一倍，比选择排序略快。 这里需要注意的是，如果要进行逆序排列，那么每次比较和移动都会进行，这时候并不会比冒泡排序快。
上面讲的三种排序，冒泡、选择、插入用大 O 表示法都需要 O(N2) 时间级别。一般不会选择冒泡排序，虽然冒泡排序书写是最简单的，但是平均性能是没有选择排序和插入排序好的。
选择排序把交换次数降低到最低，但是比较次数还是挺大的。当数据量小，并且交换数据相对于比较数据更加耗时的情况下，可以应用选择排序。
在大多数情况下，假设数据量比较小或基本有序时，插入排序是三种算法中最好的选择。
地址： https://www.cnblogs.com/ysocean/p/7896269.html
