在上一篇的随笔中，我着重复习了数组，而数组是无序的，那么如何实现有序排列呢，这里我们需要引入排序算法
冒泡排序的基本规则：
话不多说，直接上代码
package discovery; /** * Author :zhanghong * Date :2019-02-16 20:03. */ //冒泡排序 public class BubbleSort { public static int[] sort(int[] arr){ //第一个for用来表示是第几轮冒泡 for(int i=1;i<arr.length;i++){ //定义一个标志，如果这一轮循环结束仍为true，则表示这一轮没有发生元素交换，已经是有序的 boolean flag = true; //第二个for表示每轮参与比较的元素下标 j的范围是一直在缩小的 for(int j=0;j<arr.length-1;j++){ if(arr[j]>arr[j+1]){ int temp=arr[j]; arr[j]=arr[j+1]; arr[j+1]=temp; flag=false; } } if(flag){ break; } System.out.print("第"+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(); } }
package discovery; import static discovery.BubbleSort.display; import static discovery.BubbleSort.sort; /** * Author :zhanghong * Date :2018-08-13 15:00. */ public class Run { public static void main(String[] args) { // MyThread t1 = new MyThread(); // MyThread t2 = new MyThread(); // MyThread t3 = new MyThread(); // t1.start(); // t2.start(); // t3.start(); //region 数组 // MyArray myArray=new MyArray(4); // myArray.add(1); // myArray.add(2); // myArray.add(3); // myArray.add(4); // myArray.display(); // int i=myArray.getelement(0); // System.out.println(i); // myArray.delete(4); // myArray.display(); // myArray.update(3,33); // myArray.display(); //endregion //region 冒泡 int[] array = {4,2,8,9,5,7,6,1,3}; //未排序数组顺序为 System.out.println("未排序数组顺序为："); display(array); System.out.println("-----------------------"); array = sort(array); System.out.println("-----------------------"); System.out.println("经过冒泡排序后的数组顺序为："); display(array); //endregion } }
最终结果为：
本来应该是 8 轮排序的，这里我们只进行了 7 轮排序，因为第 7 轮排序之后已经是有序数组了。
我们对冒泡排序做一个简单的性能分析：
假定有N个数据需要进行排序，第一轮需要N-1次比较，第二轮需要N-2次比较，以此类推...
最终需要 （N-1）+（N-2）+...+1 = N*（N-1）/2 次
当数据量足够大时，则为 N2/2 忽略-1，在数据随机的情况下，每次比较也许需要交换位置，也许不需要，概率如果为50%,那么则变为N2/4，那么冒泡排序运行（比较和交换）都需要 O(N2) 时间级别
其实无论何时，只要看见一个循环嵌套在另一个循环中，我们都可以怀疑这个算法的运行时间为 O(N2)级，外层循环执行 N 次，内层循环对每一次外层循环都执行N次（或者几分之N次）。这就意味着大约需要执行N2次某个基本操作。
选择排序的基本规则
package discovery; /** * Author :zhanghong * Date :2019-02-16 20:46. */ public class ChoiceSort { public static int[] sort(int[] array){ for(int i=0;i<array.length-1;i++){ int min=i; for(int j=i+1;j<array.length;j++){ if(array[min]>array[j]){ min=j; } } if(i!=min){ int temp=array[i]; array[i]=array[min]; array[min]=temp; } System.out.print("第"+(i+1)+"轮排序后的结果为:"); 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(); } }
package discovery; import static discovery.ChoiceSort.display; import static discovery.ChoiceSort.sort; /** * Author :zhanghong * Date :2018-08-13 15:00. */ public class Run { public static void main(String[] args) { // MyThread t1 = new MyThread(); // MyThread t2 = new MyThread(); // MyThread t3 = new MyThread(); // t1.start(); // t2.start(); // t3.start(); //region 数组 // MyArray myArray=new MyArray(4); // myArray.add(1); // myArray.add(2); // myArray.add(3); // myArray.add(4); // myArray.display(); // int i=myArray.getelement(0); // System.out.println(i); // myArray.delete(4); // myArray.display(); // myArray.update(3,33); // myArray.display(); //endregion //region 冒泡 // int[] array = {4,2,8,9,5,7,6,1,3}; // //未排序数组顺序为 // System.out.println("未排序数组顺序为："); // display(array); // System.out.println("-----------------------"); // array = sort(array); // System.out.println("-----------------------"); // System.out.println("经过冒泡排序后的数组顺序为："); // display(array); //endregion //region 选择排序 int[] array = {4,2,8,9,5,7,6,1,3}; //未排序数组顺序为 System.out.println("未排序数组顺序为："); display(array); System.out.println("-----------------------"); array = sort(array); System.out.println("-----------------------"); System.out.println("经过选择排序后的数组顺序为："); display(array); //endregion } }
运行结果：
未排序数组顺序为：
4 2 8 9 5 7 6 1 3
-----------------------
第1轮排序后的结果为:1 2 8 9 5 7 6 4 3
第2轮排序后的结果为:1 2 8 9 5 7 6 4 3
第3轮排序后的结果为:1 2 3 9 5 7 6 4 8
第4轮排序后的结果为:1 2 3 4 5 7 6 9 8
第5轮排序后的结果为:1 2 3 4 5 7 6 9 8
第6轮排序后的结果为:1 2 3 4 5 6 7 9 8
第7轮排序后的结果为:1 2 3 4 5 6 7 9 8
第8轮排序后的结果为:1 2 3 4 5 6 7 8 9
-----------------------
经过选择排序后的数组顺序为：
1 2 3 4 5 6 7 8 9
选择排序的性能分析
选择排序和冒泡排序执行了相同次数的比较：N*（N-1）/2，但是至多只进行了N次交换。
当 N 值很大时，比较次数是主要的，所以和冒泡排序一样，用大O表示是O(N2) 时间级别。但是由于选择排序交换的次数少，所以选择排序无疑是比冒泡排序快的。当 N 值较小时，如果交换时间比选择时间大的多，那么选择排序是相当快的。
插入排序分为直接插入排序、二分插入排序、链表插入排序、希尔排序等等，这里我们只是以直接插入排序讲解，后面讲高级排序的时候会将其他的。
直接插入排序的基本思路是：将一个待排序元素放入到前面已经排好序的序列中，直到插完所有元素为止
原文：https://www.cnblogs.com/zhhouse/p/10389460.html