九 排序算法大总结（冒泡排序 选择排序 插入排序 希尔排序 快速排序 归并排序

一、排序算法介绍以及时间复杂度计算

1.排序的分类

排序也称排序算法(Sort Algorithm)，排序是将一组数据，依指定的顺序进行排列的过程。排序的分类：

内部排序(考察的比较多）:

指将需要处理的所有数据都加载到内部存储器中进行排序。外部排序法：

数据量过大，无法全部加载到内存中，需要借助外部存储进行排序。

2.算法的时间复杂度计算

2.1 时间频度

时间频度：一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度

2.2 时间复杂度（忽略常数项、低次项和系数）

2.2.1 时间复杂度O(1)

无论代码执行了多少行，只要是没有循环等复杂结构，那这个代码的时间复杂度就都是O(1)

int i = 1;int j = 2;++i;j++;int m = i + J;

上述代码在执行的时候，它消耗的时候并不随着某个变量的增长而增长，那么无论这类代码有多长，即使有几万几十万行，都可以用O(1)来表示它的时间复杂度。

2.2.2 时间复杂度 O(logn)(底数可以改变的）

int i = 1;while(i < n){i = i * 2;}

说明：在while循环里面，每次都将 i 乘以 2，乘完之后，i 距离 n 就越来越近了。假设循环x次之后，i 就大于 2 了，此时这个循环就退出了，也就是说 2 的 x 次方等于 n，那么 x = log2n也就是说当循环 log2n 次以后，这个代码就结束了。因此这个代码的时间复杂度为：O(log2n) 。 O(log2n) 的这个2 时间上是根据代码变化的，i = i * 3 ，则是 O(log3n)

2.2.3 时间复杂度 O(n)

for（int i = 1； i <= n ; ++i){i++;}

说明：这段代码，for循环里面的代码会执行n遍，因此它消耗的时间是随着n的变化而变化的，因此这类代码都可以用O(n)来表示它的时间复杂度

2.2.4 时间复杂度 O(nlogn)

for(int m =1; m < n; m++){i = 1;while(i < n){i = i * 2;}}

说明：线性对数阶O(nlogN) 其实非常容易理解，将时间复杂度为O(logn)的代码循环N遍的话，那么它的时间复杂度就是 n * O(logN)，也就是了O(nlogN)

2.2.5 时间复杂度 O(n^k)

int m = 1;for (int i = 1; i <= n; i++){for(int j =1; j <= n; j++){m++;}}

说明：平方阶O(n²) 就更容易理解了，如果把 O(n) 的代码再嵌套循环一遍，它的时间复杂度就是 O(n²)，这段代码其实就是嵌套了2层n循环，它的时间复杂度就是 O(nn)，即 O(n²)。 如果将其中一层循环的n改成m，那它的时间复杂度就变成了 O(mn)

2.2.6 平均时间复杂度和最坏时间复杂度

1.平均时间复杂度：指所有可能的输入实例均以等概率出现的情况下，该算法的运行时间。

2.最坏时间复杂度：最坏情况下的时间复杂度称最坏时间复杂度。一般讨论的时间复杂度均是最坏情况下的时间复杂度。 这样做的原因是：最坏情况下的时间复杂度是算法在任何输入实例上运行时间的界限，这就保证了算法的运行时间不会比最坏情况更长。

二、冒泡排序

1.冒泡排序原理

2.代码实现

package sort;import java.text.SimpleDateFormat;import java.util.Date;public class BubbleSort {public static void main(String[] args) {//int arr[] = {3, 9, -1, 10, 20};////System.out.println("排序前");//System.out.println(Arrays.toString(arr));//为了容量理解，我们把冒泡排序的演变过程，给大家展示//测试一下冒泡排序的速度O(n^2), 给80000个数据，测试//创建要给80000个的随机的数组int[] arr = new int[80000];for(int i =0; i < 80000;i++) {arr[i] = (int)(Math.random() * 8000000); //生成一个[0, 8000000) 数}Date data1 = new Date();SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");String date1Str = simpleDateFormat.format(data1);System.out.println("排序前的时间是=" + date1Str);//测试冒泡排序bubbleSort(arr);Date data2 = new Date();String date2Str = simpleDateFormat.format(data2);System.out.println("排序后的时间是=" + date2Str);}// 将前面的冒泡排序算法，封装成一个方法public static void bubbleSort(int[] arr) {// 冒泡排序 的时间复杂度 O(n^2), 自己写出int temp = 0; // 临时变量boolean flag = false; // 标识变量，表示是否进行过交换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]) {flag = true;temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}if (!flag) {// 在一趟排序中，一次交换都没有发生过break;} else {flag = false; // 重置flag!!!, 进行下次判断}}}}

3.测试结果

排序前的时间是=-09-27 09:52:04排序后的时间是=-09-27 09:52:16

三、选择排序

1.选择排序原理

2.代码实现

package sort;import java.text.SimpleDateFormat;import java.util.Arrays;import java.util.Date;//选择排序public class SelectSort {public static void main(String[] args) {//int [] arr = {101, 34, 119, 1, -1, 90, 123};//创建要给80000个的随机的数组int

九 排序算法大总结（冒泡排序 选择排序 插入排序 希尔排序 快速排序 归并排序 基数排序）