排序也称排序算法，排序是将一组数据，依指定的顺序进行排列的过程。
时间频度：一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，他花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。 记为T(n)。
举例说明-基本案例 比如计算1-100所有数字之和，设计以下两种算法： // 第一种算法:T(n) = n+1; int total = 0; int end = 100; for(int i = 1; i <= end; i++){ total += i; } // 第二种算法：T(n) = 1; total = (1+end)*end/2; 举例说明-忽略常数项 结论： 2n+20 和 2n 随着n变大，执行曲线无限接近，20可以忽略；3n+10 和 3n 随着n变大，执行曲线无限接近，10可以忽略； 举例说明-忽略低次项 结论： 2n^2+3n+10 和 2n^2 随着n变大，执行曲线无限接近，可以忽略 3n+10；n^2+5n+20 和 n^2 随着n变大，执行曲线无限接近，可以忽略 5n+20； 举例说明-忽略系数 结论： 随着 n 值变大，5n^2+7n 和 3n^2+2n，执行曲线重合，说明 这种情况下，5和3可以忽略；而n^3+5n 和 6n^3+4n，执行曲线分离，说明，多少次方是关键；常见的时间复杂度对应的曲线图 说明：
常见的算法时间复杂度由小到大依次为：O(1)<O(log2n)<O(n)<O(nlog2n)<O(n^2)<O(n^3)<O(n^k)<O(2^n)，随着问题规模n的不断增大，上述时间复杂度不断增大，算法执行效率越低；从图中可见，我们应该尽可能避免使用指数阶的算法；1. 常数阶O(1) 无论代码执行了多少行，只要是没有循环等复杂结构，那这个代码的时间复杂度就都是O(1)。
int i = 1; int j = 2; ++i; j++; int m = i + j;上述代码在执行的时候，它消耗的时候并不随着某个变量的增长而增长，那么无论这类代码有多长，即使有几万几十万行，都可以用O(1)来表示它的时间复杂度。
2. 对数阶O(log2n)
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)。
3. 线性阶O(n)
for(int i =1; i <=n; ++i) { j = i; j++; }说明：这段代码，for循环里面的代码会执行n遍，因此它消耗的时间是随着n的变化而变化的，因此这类代码都可以用O(n)来表示它的时间复杂度。
4. 线性对数阶O(nlogN)
for (m = 1; m < n; m++) { i = 1; while(i < n){ i = i * 2; } }说明：将时间复杂度为O(logn)的代码循环N遍的话，那么它的时间复杂度就是 n*O(logN)，也就是 O(nlogN)。
5. 平方阶 O(n^2)
for (x=1; i<=n; x++) { for(i=1;i<=n;i++){ j = i; j++; } }说明：平方阶 O(n^2)就更容易理解了，如果把O(n)的代码再嵌套循环一遍，它的时间复杂度就是O(n^2)，这段代码其实就是嵌套了2层n循环，它的时间复杂度就是 O(n*n)，即 O(n^2) 如果将其中一层循环的n改成m，那它的时间复杂度就变成了 O(m*n)。
6. 立方阶 O(n^3)、K次方阶 O(n^k) 说明：参照上面的 O(n^2)去理解就好了， O(n^3) 相当于三层n循环，其他的类似。
冒泡排序（Bubble Sorting）的基本思想是：通过对待排序序列从前向后（从下标较小的元素开始），依次比较相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从前移向后部，就像水底下的气泡一样逐渐向上冒。
优化 因为排序的过程中，各元素不断接近自己的位置，如果一趟比较下来没有进行过交换，就说明序列有序，因此要在排序过程中设置一个标志 flag 判断元素是否进行过交换，从而减少不必要的比较。（这里说的优化，可以在冒泡排序写好后，再进行） 说明：
一共进行 数组的大小-1 次大的循环；每一趟排序的次数在逐渐的减少；如果我们发现在某趟排序中，没有发生一次交换，可以提前结束冒泡排序。例子：将五个无序的数：3,9,-1,10,-2 使用冒泡排序法将其排成一个从小到大的有序数列。 代码实现
package com.lele.sort; import java.text.SimpleDateFormat; import java.util.Arrays; import java.util.Date; /** * author: hwl * date: 2020/10/8 21:10 * version: 1.0.0 * modified by: * description: 冒泡排序 */ public class BubbleSort { public static void main(String[] args) { // int arr[] = {3,9,-1,10,-2}; // bubbleSort(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 date1 = new Date(); SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss"); String date1Str = simpleDateFormat.format(date1); System.out.println("排序前的时间为：" + date1Str); bubbleSort(arr); Date date2 = new Date(); String date2Str = simpleDateFormat.format(date2); System.out.println("排序后的时间为：" + date2Str); } // 冒泡排序的时间复杂度：O(n^2) private static void bubbleSort(int[] arr) { 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; } } // System.out.println("第"+(i+1)+"趟排序后的数组："); // System.out.println(Arrays.toString(arr)); if (!flag) { // 在一趟排序中，一次交换都没有发生过 break; } else { flag = false; // 重置flag,进行下次判断 } } } }选择式排序也属于内部排序法，是从预排序的数据中，按指定的规则选出某一元素，再依规定交换位置后达到排序的目的。
选择排序（select sorting）的基本思想是：第一次从 arr[0]~arr[n-1]中选取最小值，与arr[0]交换；第二次从 arr[1]~arr[n-1] 中选取最小值，与 arr[1] 交换；第三次从 arr[2]~arr[n-1]中选取最小值，与 arr[2] 交换；…，第 i 次从 arr[i-1]~arr[n-1] 中选取最小值，与 arr[i-1] 交换，…，第 n-1 次从 arr[n-2]~arr[n-1] 中选取最小值，与 arr[n-2] 交换，总共通过 n-1 次，得到一个按排序码从小到大排列的有序序列。
插入式属于内部排序法，是对于欲排序的元素以插入的方式寻找该元素的适当位置，以达到排序的目的。
插入排序的基本思想是：把n个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表。
数组 arr={2,3,4,5,6,1} 这时需要插入的数1（最小），这样的过程是：
{2,3,4,5,6,6} {2,3,4,5,5,6} {2,3,4,4,5,6} {2,3,3,4,5,6} {2,2,3,4,5,6} {1,2,3,4,5,6}结论：当需要插入的数是较小的数时，后移的次数明显增多，对效率有影响。
希尔排序是希尔（Donald Shell）于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称缩小增量排序。
希尔排序把记录下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
有一群小牛，考试成绩分别是 {8,9,1,7,2,3,5,4,6,0} 请从小到大排序，请分别使用：
希尔排序时，对有序序列在插入时采用交换法，并测试排序速度；希尔排序时，对有序序列在插入时采用移动法，并测试排序速度；代码实现
package com.lele.sort; import java.text.SimpleDateFormat; import java.util.Arrays; import java.util.Date; /** * author: hwl * date: 2020/10/13 7:26 * version: 1.0.0 * modified by: * description: */ public class ShellSort { public static void main(String[] args) { // int[] arr = {8,9,1,7,2,3,5,4,6,0}; // 创建一个 有80000 个随机数的数组 int[] arr = new int[80000]; for (int i = 0; i < 80000; i++) { arr[i] = (int)(Math.random()*8000000); } Date date1 = new Date(); SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss"); String date1Str = simpleDateFormat.format(date1); System.out.println("排序前的时间是：" + date1Str); // shellSort(arr); shellSort2(arr); Date date2 = new Date(); String date2Str = simpleDateFormat.format(date2); System.out.println("排序后的时间是：" + date2Str); // System.out.println(Arrays.toString(arr)); } // 希尔排序时，对有序序列在插入时采用交换法， public static void shellSort(int[] arr) { int temp = 0; int count = 0; for (int gap = arr.length / 2; gap > 0; gap /= 2) { for (int i = gap; i < arr.length; i++) { // 遍历各组中所有的元素（共gap组，每组有个元素），步长gap for (int j = i - gap; j >= 0; j -= gap) { // 如果当前元素大于加上步长后的那个元素，则交换 if (arr[j] > arr[j + gap]) { temp = arr[j]; arr[j] = arr[j + gap]; arr[j + gap] = temp; } } } // System.out.println("希尔排序第"+(++count)+"轮 =" + Arrays.toString(arr)); } } // 对交换式的希尔排序进行优化=>移位法 public static void shellSort2(int[] arr) { //增量gap, 并逐步的缩小增量 for (int gap = arr.length / 2; gap > 0; gap /= 2) { // 从第gap个元素，逐个对其所在的组进行直接插入排序 for (int i = gap; i < arr.length; i++) { int j = i; int temp = arr[j]; if (arr[j] < arr[j-gap]) { while(j - gap >= 0 && temp < arr[j-gap]) { // 移动 arr[j] = arr[j-gap]; j -= gap; } // 当退出while后，就给temp找到插入的位置 arr[j] = temp; } } } } }快速排序是对冒泡排序的一种改进。基本思想是：通过一趟排序将要排序的数据分割成独立量部分，其中一部分的所有数据比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
对[-9,78,0,23,-567,70]进行从小到大的排序，使用快速排序。
如果取消左右递归，结果是 -9,-567,0,23,78,70如果取消右递归，结果是 -567,-9,0,23,78,70如果取消左递归，结果是 -9,-567,0,23,70,78代码实现
package com.lele.sort; import java.text.SimpleDateFormat; import java.util.Arrays; import java.util.Date; /** * author: hwl * date: 2020/10/15 21:24 * version: 1.0.0 * modified by: * description: */ public class QuickSort { public static void main(String[] args) { // int[] arr = {-9,78,0,23,-567,70,-1,900,4561}; // 创建一个 有80000 个随机数的数组 int[] arr = new int[80000]; for (int i = 0; i < 80000; i++) { arr[i] = (int)(Math.random()*8000000); } Date date1 = new Date(); SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss"); String date1Str = simpleDateFormat.format(date1); System.out.println("排序前的时间是：" + date1Str); quickSort(arr, 0, arr.length-1); Date date2 = new Date(); String date2Str = simpleDateFormat.format(date2); System.out.println("排序后的时间是：" + date2Str); // System.out.println(Arrays.toString(arr)); } public static void quickSort(int[] arr, int left, int right) { int l = left;// 左下标 int r = right;// 右下标 // pivot 中轴值 int pivot = arr[(left + right) / 2]; int temp = 0;// 临时变量，作为交换时使用 // while循环的目的是让比pivot值小的放到左边，比pivot值大的放到右边 while(l < r) { // 在pivot的左边一直找，找到大于等于pivot值，才退出 while(arr[l] < pivot) { l++; } // 在pivot的右边一直找，找到小于等于pivot值，才退出 while(arr[r] > pivot) { r--; } // 如果 l >= r 说明pivot的左右两边的值，已经按照左边全部是小于等于 pivot 值，右边全部是大于等于pivot值 if (l >= r) { break; } // 交换 temp = arr[l]; arr[l] = arr[r]; arr[r] = temp; // 如果交换完后，发现这个arr[l] == pivot 值 相等 r--，前移 if (arr[l] == pivot) { r--; } // 如果交换完后，发现这个arr[r] == pivot 值 相等 l++，后移 if (arr[r] == pivot) { l++; } } // 如果 l==r，必须l++,r--,否则出现栈溢出 if (l == r) { l++; r--; } // 向左递归 if (left < r) { quickSort(arr,left, r); } // 向右递归 if (right > l) { quickSort(arr, l, right); } } }归并排序是利用归并的思想实现的排序方法，该算法采用经典的分治策略（分治法将问题分成一些小的问题然后递归求解，而治的阶段则将分的阶段得到的各答案“修补”在一起，即分而治之）。
给你一个数组，{8,4,5,7,1,3,6,2},使用归并排序完成排序。 代码实现
package com.lele.sort; import java.text.SimpleDateFormat; import java.util.Arrays; import java.util.Date; /** * author: hwl * date: 2020/10/17 17:16 * version: 1.0.0 * modified by: * description: */ public class MergeSort { public static void main(String[] args) { // int arr[] = {8,4,5,7,1,3,6,2}; // 测试快排的执行速度 // 创建一个80000个随机数的数组 int[] arr = new int[80000]; for (int i = 0; i < 80000; i++) { arr[i] = (int)(Math.random() * 8000000); } Date date1 = new Date(); SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss"); String date1Str = simpleDateFormat.format(date1); System.out.println("排序前的时间是：" + date1Str); int temp[] = new int[arr.length]; //归并排序需要一个额外空间 mergeSort(arr, 0, arr.length - 1, temp); Date date2 = new Date(); String date2Str = simpleDateFormat.format(date2); System.out.println("排序后的时间：" + date2Str); // System.out.println("排序后=" + Arrays.toString(arr)); } public static void mergeSort(int[] arr, int left, int right, int[] temp) { if (left < right) { int mid = (left + right) / 2;//中间索引 // 向左递归进行分解 mergeSort(arr, left, mid, temp); // 向右递归进行分解 mergeSort(arr, mid+1,right,temp); // 合并 merge(arr, left, mid, right, temp); } } /** * 合并的方法 * @param arr 排序的原始数组 * @param left 左边有序序列的初始索引 * @param mid 中间索引 * @param right 右边索引 * @param temp 做中转的数组 */ public static void merge(int[] arr, int left, int mid, int right, int[] temp) { int i = left; // 初始化i，左边有序序列的初始索引 int j = mid + 1; // 初始化j，右边有序序列的初始索引 int t = 0; // 指向 temp 数组的当前索引 // 先把左右两边（有序）的数据按照规则填充到 temp 数组，直到左右两边的有序序列，有一边处理完毕为止 while(i <= mid && j <= right) { // 继续 // 如果左边的有序序列的当前元素，小于等于右边有序序列的当前元素，则将左边的当前元素，填充到 temp 数组，然后t++，i++ if (arr[i] <= arr[j]) { temp[t] = arr[i]; t++; i++; } else {// 反之将右边有序序列的当前元素，填充到 temp 数组 temp[t] = arr[j]; t++; j++; } } // 把剩余数据的一边的数据依次全部填充到 temp while( i <= mid) { //左边的有序序列还有剩余的元素，就全部填充到 temp temp[t] = arr[i]; t++; i++; } while(j <= right) { // 右边的有序序列还有剩余元素，就全部填充到 temp temp[t] = arr[j]; t++; j++; } // 将 temp 数组的元素拷贝到 arr // 注意，并不是每次都拷贝所有 t = 0; int tempLeft = left; // 第一次合并 tempLeft = 0, right = 1 // tempLeft = 2 right = 3 // tempLeft = 0, right = 3 // 最后一次 tempLeft = 0 right = 7 while(tempLeft <= right) { arr[tempLeft] = temp[t]; t++; tempLeft++; } } }将数组{53,3,542,748,14,214} 使用基数排序，进行升序排序。 代码实现
package com.lele.sort; import java.text.SimpleDateFormat; import java.util.Arrays; import java.util.Date; /** * author: hwl * date: 2020/10/20 7:03 * version: 1.0.0 * modified by: * description: */ public class RadixSort { public static void main(String[] args) { // int[] arr = {53,3,542,748,14,214}; // 创建一个80000个随机数的数组 int[] arr = new int[80000]; for (int i = 0; i < 80000; i++) { arr[i] = (int)(Math.random() * 8000000); } Date date1 = new Date(); SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss"); String date1Str = simpleDateFormat.format(date1); System.out.println("排序前的时间是：" + date1Str); radixSort(arr); Date date2 = new Date(); String date2Str = simpleDateFormat.format(date2); System.out.println("排序后的时间：" + date2Str); } // 基数排序方法 public static void radixSort(int[] arr) { // 获取数组中最大的数的位数 int max = arr[0];// 假设第一个数就是最大数 for (int i = 1; i < arr.length; i++) { if (arr[i] > max) { max = arr[i]; } } // 得到最大数是几位数 int maxLength = (max + "").length(); /** * 定义一个二维数组，表示10个桶，每个桶就是一个一维数组 * 说明 * 1. 二维数组包含10个一维数组 * 2.为了防止在放入数的时候，数据溢出，则每一个一维数组（桶），大小定为arr.length * 3.基数排序是使用空间换时间的经典算法 */ int[][] bucket = new int[10][arr.length]; /** * 为了记录每个桶中，实际放了多少个数据，我们定义一个一维数组来记录各个桶的每次放入的数据个数 * 比如：bucketElementCounts[0],记录的就是 bucket[0] 桶的放入数据个数 */ int[] bucketElementCounts = new int[10]; for (int i = 0, n = 1;i < maxLength; i++, n *= 10) { // 针对每个元素的对应位进行排序处理，第一次是个位，第二次是十位，第三次是百位 for (int j = 0; j < arr.length; j++) { // 取出每个元素的对应位的值 int digitOfElement = arr[j] / n % 10; // 放入到对应的桶中 bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j]; bucketElementCounts[digitOfElement]++; } // 按照这个桶的顺序（一维数组的下标依次取出数据，放入原数组） int index = 0; // 遍历每一个桶，并将桶中数据，放入原数组 for (int k = 0; k < bucketElementCounts.length; k++) { // 如果桶中，有数据，我们才放入原数组 if (bucketElementCounts[k] != 0) { // 循环该桶 即第k个桶，放入 for (int l = 0; l < bucketElementCounts[k]; l++) { // 取出元素放入到arr arr[index++] = bucket[k][l]; } } // 第 i+1 轮处理后，需要将每个 bucketElementCounts[k] = 0 bucketElementCounts[k] = 0; } // System.out.println("第"+(i+1)+"轮，排序后：arr = " + Arrays.toString(arr)); } } }注释
稳定：如果 a 原本在 b前面，而a = b，排序之后a仍然在b的前面；不稳定：如果 a 原本在 b前面，而a = b，排序之后a可能会出现在b的后面；内排序：所有排序操作都在内存中完成；外排序：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行；时间复杂度：算法执行所耗费的时间；空间复杂度：运行完一个程序所需要内存大小；n : 数据规模；k：“桶”的个数；In-space：不占用额外内存；Out-place：占用额外内存；