排序也叫排序算法，排序是将一组数据，依指定的顺序进行排列的过程。
排序的分类：
1）内部排序：指将需要处理的所有数据都加载到内部存储器中进行排序。
2）外部排序：数据量过大，无法全部加载到内存中，需要借助外部存储进行排序。
3）常见的排序算法分类：
内部排序：
（1）插入排序：直接插入排序、希尔排序
（2）选择排序：简单选择排序、堆排序
（3）交换排序：冒泡排序、快速排序
（4）归并排序、基数排序
我们先回顾知识点：时间复杂度
时间频度：一个算法花费的时间与算法中语句的执行次数成正比例，那个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。
，其中的常数项、低次项、系数都可以忽略。
时间复杂度：
1）一般情况下，算法中的基本操作语句的重复执行次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n)，使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于0的长树，则称f(n)时T(n)的同数量级函数。记作T(n)=O(f(n))，称O(f(n))为算法的渐进时间复杂度，简称时间复杂度。
2）T(n)不同，但时间复杂度可能相同。如T(n)=n^2+7n+6与T(n)=3n^2+2n+2，它们的T(n)不同，但时间复杂度相同，都为O(n^2)
3）计算时间复杂度的方法：用常数1代替运行时间中的所有加法常数；修改后的运行次数函数中，只保留最高阶项；去除最高阶项的系数。
常见的时间复杂度：
1）常数阶：O(1)
2）对数阶：O(log2 n)此处2为底数
3）线性阶：O(n)
4）线性对数阶：O(n log2 n)
5）平方阶：O(n^2)
6）立方阶：O(n^3)
7）k次方阶：O(n^k)
8）指数阶：O(2^n)
说明：常见的算法时间复杂度由小到大依次为：O(1)<O(log2 n)<O(n)<O(n log2 n)<O(n^2)<O(n^3)<O(n^k)<O(2^n)，随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。应该尽量避免使用指数阶的算法。
平均时间复杂度和最坏时间复杂度
1）平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下，该算法的运行时间。
2）最坏情况下的时间复杂度称最欢时间复杂度。一般讨论的时间复杂度均是最坏情况下的时间复杂度。这样做的原因是： 最坏情况下的时间复杂度是算法在任何输入实例上运行时间的界限，这就保证了算法的运行时间不会比最坏情况更长。
3）平均时间复杂度和最坏时间复杂度是否一致，和算法有关，如图：
算法空间复杂度定义为该算法所耗费的存储空间，它也是问题规模n的函数。
1.冒泡排序
思想：通过对待排序序列从前向后，依次比较相邻元素的值，若发现逆序则交换，使值较大的元素逐渐移向后面，就像水底的气泡一样逐渐向上冒。每次都会确定后面位置的元素。
因为排序的过程中，各元素不断接近自己的位置，如果一趟比较下来没有进行过交换，就说明序列有序，因此要在排序过程中设置一个标志flag判断元素是否进行过交换。从而减少不必要的比较。
排序的稳定性是如果序列中有两个数据值是一样的，排序后这两个元素的相对位置改变了，那就是不稳定的，如果没改变，就是稳定的。
冒泡排序一趟下来，两两比较，只交换逆序的，不交换相等的，故是稳定的。
每一趟，都是从头比较，所以时间复杂度是O(n^2)。
// 需要排序的无序数组int[] nums = {2,4,3,2,34,24,56,88,433,56,788,345};boolean flag = false; // 是否需要停止遍历的条件int temp = 0;// 第一趟排序是需要for (int i = 0; i < nums.length - 1; i++) { // 趟数for (int j = 0; j < nums.length - 1 - i; j++) {// 此处可以多加注意，因为每趟排序下来，一定有一个元素确定在自己的最终位置// 所以不用循环到它所在的位置了。if(nums[j] > nums[j + 1]){ // 如果前面的数比后面的数大，交换temp = nums[j];nums[j] = nums[j + 1];nums[j + 1] = temp;flag = true;}}if(flag == false) break; // 如果一趟下来，都没有交换，那么就是有序else flag = false; // 如果不是，就要重新置false，不然下一轮就算没有交换，也是true}for(int i : nums)System.out.printf("% d",i); // 2 2 3 4 24 34 56 56 88 345 433 788}
2.选择排序
选择排序也属于内部排序法，是从要排序的序列中，按指定的规则选出某一元素，再依规定交换位置后达到排序的目的。
思想：选择排序也是一种简单的排序方法，它的基本思想是：第一次从arr[0]~arr[n-1]中选取最小值，与arr[0]交换，第二次从arr[1]到arr[n-1]选取最小值与arr[1]交换，...，第n-1次从arr[n-2]~arr[n-1]中选取最小值，与arr[n-2]交换，总共通过n-1次，得到一个按排序码从小到大排序的有序序列。
int[] nums = {2,4,3,2,34,24,56,88,433,56,788,345};int temp = 0;for (int i = 0; i < nums.length - 1; i++) { // 遍历n-1次int min = nums[i]; // 记录最小值int index = i;for (int j = i + 1; j < nums.length; j++) { // 每轮找到最小的数和下标if(nums[j] < min){min = nums[j];index = j;}}// 交换数temp = nums[i];nums[i] = min;nums[index] = temp;}for(int i : nums)System.out.printf("% d",i);
选择排序两层for循环，时间复杂度是O(n^2)，交换过程中会改变相同数值元素的相对位置，所以是不稳定的。
3.插入排序
插入排序属于内部排序法，是对要排序的元素以插入的方式找寻该元素的实当位置，以达到排序的目的。
思想：把n个待排序的元素看成是一个有序表和无序表，开始时有序表中只包含一个元素（第一个元素），无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之称为新的有序表。
int[] nums = {2,4,3,2,34,24,56,88,433,56,788,345};int j,insertNum;for (int i = 1; i < nums.length; i++) {insertNum = nums[i];j = i - 1;while (j >= 0 && nums[j] > insertNum) {nums[j + 1] = nums [j];j--;}nums[j + 1] = insertNum; // 不要直接用nums[i]来换，已经变动了}for(int i : nums)System.out.printf("% d",i);
两层循环，时间复杂度为O(n^2)，但移动的时候，只移动比它大的，没有影响相同数值元素的相对位置，故稳定。
简单插入排序可能存在的问题：当需要插入的数是较小的数时，后移的次数明显增多，对效率有影响。
4.希尔排序
希尔排序是希尔于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也成为缩小增量排序。
思想：希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序，随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
希尔排序是通过对分组元素进行分组直接插入排序（即移动法）来优化插入排序的，注意不是用交换来写，交换本质不是插入。
int[] arr = {2,4,3,2,34,24,56,88,433,56,788,345}; // 12int j,insertVal;int gap = arr.length / 2;// 第一轮排序，将12个数据分成了6组while(gap >= 1) { // 等于1时就是最后一趟插入排序了// 类似于插入排序，从后往前插入// i初始化是分组后，第一组的第二个元素// 逐个往后遍历for (int i = gap; i < arr.length; i++) {j = i - gap; // j初始化是第一组的第一个元素，视作独立的有序序列insertVal = arr[i]; // 保留当前要往有序序列里插入的元素while (j >= 0 && insertVal < arr[j]) {// 和有序序列里的元素逐个比较大小，如果比它小，让它往后移arr[j + gap] = arr[j];j -= gap; // 按步进取一组里的每一个元素}// 将要插入的元素放在合适的位置arr[j + gap] = insertVal;}gap /= 2; // 步长更新}for(int i : arr)System.out.printf("% d",i);
希尔排序分组后，可能会让相同值的元素相对位置改变，故不稳定，平均时间复杂度为O(nlogn)，最坏时间复杂度为O(n^2)。
5.快速排序
快速排序是对冒泡排序（交换法）的一种改进。
基本思想：通过一趟排序将要排序的数据从基准位置分割成独立的两部分，其中一部分的所有数据都比基准小，另外一部分的所有数据都比基准大，这样一趟下来，基准元素就在最终位置了。然后再按此方法对两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
快排采用的是分治策略。
public static void main(String[] args) {int[] arr = {4,3,4,4,6,2,4,4,2,2,11,9};quickSort(arr,0,arr.length - 1);for(int i : arr)System.out.printf("% d",i);}private static void quickSort(int[] arr, int left, int right) {if(left >= right) return; // 递归停止条件，此时已排序完成int i = left,j = right; // 比对指针int bench = arr[left]; // 取最左边的数为基准int temp; // 交换时的暂存值while(i < j){while(arr[j] >= bench && i < j) j--;while(arr[i] <= bench && i < j) i++;if(i < j){ // 交换temp = arr[i];arr[i] = arr[j];arr[j] = temp;}}// 基准数归位，即将最左位和此时的基准最终位交换// 此时一定是i == jarr[left] = arr[i];arr[i] = bench;// 递归两边，递归放在while循环外面quickSort(arr,left,i-1);quickSort(arr,i+1,right);}
快速排序不稳定，时间复杂度平均为O(n logn)，最坏为O(n^2)
6.归并排序
归并排序是利用归并的思想实现的排序方法，该算法采用经典的分治策略（分治法将问题分成一些小的问题然后递归求解，而治的阶段则将分的阶段得到的各答案“修补”在一起，即分而治之）。
说明：可以看到这种结构很像一棵完全二叉树，本文的归并排序我们采用递归去实现（也可采用迭代的方式去实现）。
分阶段可以理解为就是递归拆分子序列的过程，递归深度为logn。
再来看看治阶段，我们需要将两个已经有序的子序列合并成一个有序序列，比如上图中的最后一次合并，要将[4,5,7,8]和[1,2,3,6]两个已经有序的子序列，合并为最终序列[1, 2, 3, 4, 5, 6, 7, 8]，来看下实现步骤。
public static void main(String[] args) {int[] arr = {2,3,4,2,6,2,8,7,2,5,11,9};int[] temp = new int[arr.length];mergeSort(arr,0,arr.length - 1,temp);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; // 左边有序序列的初始索引int j = mid + 1; // 右边有序序列的初始索引int t = 0; // 指向temp数组待放元素的下标// 第一步，先把左右两边（有序）的数据按照规则填充到temp里去// 直到左右两边的有序序列，有一边处理完毕为止while(i <= mid && j <= right){if(arr[i] <= arr[j]){temp[t++] = arr[i++]; // 这样就稳定了}else{temp[t++] = arr[j++];}}// 把有剩余数据的一边数据依次填充到tempwhile(i <= mid) temp[t++] = arr[i++];while(j <= right) temp[t++] = arr[j++];// 将temp数组的元素拷贝到arr// 注意，并不是每次都拷贝所有t = 0;int tempLeft = left;// 第一次合并时，left = 0,right = 1;// 第二次合并时。left = 2,right = 3;// 第三次合并时，left = 0;right = 3;// 最后一次合并时，left = 0,right = 7;while(tempLeft <= right){arr[tempLeft++] = temp[t++];}}
归并排序稳定，时间复杂度平均和最坏都是O(n logn)
7.基数排序
基数排序radix sort属于“分配式排序”，又称“桶子法”bucket sort或bin sort，顾名思义，它是通过键值的各个位的值，将要排序的元素分配至某些桶中，达到排序的作用。
基数排序是桶排序的扩展。
思想来源：将整数按位数切割成不同的数字，然后按每个位数分别比较。
排序思想：将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列。
图片解释：
可以看出基数排序是用空间换时间的经典算法。
public static void main(String[] args) {int[] arr = {53,3,542,748,14,214};redixSort(arr);System.out.println(Arrays.toString(arr));}private static void redixSort(int[] arr){// 第一一个二维数组，表示十个桶// 每个桶就是一个一维数组int[][] bucket = new int[10][arr.length];int[] index = new int[10]; // 每个桶的索引，new出来的在栈里，故有初始化值0// 得到数组中最大的数的位数int max = arr[0];for (int i = 1; i < arr.length; i++) {if(arr[i] > max) max = arr[i];}// 得到最大数的位数int maxLength = (max + "").length(); // 将其转为字符串，直接得出长度for (int i = 0,n = 1; i < maxLength; i++,n *= 10) {for (int j = 0; j < arr.length; j++) {// 从个位开始取出每一位/*个位：arr[j] % 10;十位：arr[j] /10 %10;百位：arr[j] /100 % 10;...*/int digit = arr[j] / n % 10;bucket[digit][index[digit]++] = arr[j]; // 第几个桶，桶里的第几个位置，放入后，位置++}int renew = 0;// 按照这个桶的顺序，一维数组的下标一次取出数据，放入原来数组for (int k = 0; k < bucket.length; k++) {// 如果桶中有数据，才放入原数组if (index[k] != 0) { // 桶里有数据for (int h = 0; h < index[k]; h++) {// 取出元素放入到arr中arr[renew++] = bucket[k][h];}}// 第一轮处理后，需要将每个桶的索引清零index[k] = 0;}}}
基数排序是稳定算法，时间复杂度平均和最坏都是的为O(log R B)，R为0-9，B为最高位数。
注意事项：有负数的数组，不用基数排序来进行排序。
9.常用排序算法对比
常用术语解释：
内排序：所有排序操作都在内存中完成；
外排序：由于数据台打，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行。
基数排序：平均、最好、最坏时间复杂度都为O(n * k)，空间复杂度也是O(n * k)。
