目录
概念
插入排序
直接插入排序
希尔排序
选择排序
直接选择排序
双向选择排序
堆排序
交换排序
冒泡排序
快速排序
Hoare法
挖坑法
前后指针法
快排的优化
三数取中法
非递归快排
归并排序
分治算法+二路归并
非递归归并
应用
排序总结
其他排序
计数排序
简单版本
复杂版本（稳定版本）
基数排序
桶排序
概念
排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。
内部排序：数据元素全部放在内存中的排序
外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。 （比如要放在磁盘，硬盘等来进行排序）
分类：
插入排序
直接插入排序
动图演示如下：
我们可以设置两个指针i和j，i放在第二个元素的位置，j放在第一个元素的位置
每次把i位置的元素提取出来放到tmp中，和j位置的元素进行比较，如果tmp的元素较小，就与j位置元素进行交换
交换完之后j--，看看前面还有没有元素比交换后靠前的元素大，如果有就重复上述步骤，没有就把j和i挪到下一个元素
public static void insertSort(int[] array) {for (int i = 1; i < array.length; i++) {int tmp = array[i];int j = i - 1;for (; j >= 0; j--) {if (array[j] > tmp) {array[j + 1] = array[j];} else {break;}}array[j + 1] = tmp;}}时间复杂度？
最坏情况：
假设有n个数据，遍历第2个元素并进行交换，j要回退2-1 = 1次
遍历第3个元素并进行交换，j要回退3-1 = 2次
遍历第n个元素并进行交换，j还需要进行回退n-1次，那么需要n-1次操作，
总共就需要
1+2+3+...+n-1 ≈ n^2 -->O(n^2)
最好情况:
交换之后j不需要进行回退，那么直直遍历下去 --> O(n)
所以直插适用于：待排序序列基本趋于有序了
稳定性？
直接插入排序是稳定的，数据交换判断需要array[i] > tmp才有进行交换，如果原本序列有两个相同的数字，那直插是不会改变这两个数字的顺序的，所以是稳定的
⚠一个稳定的排序可以通过修改条件变成不稳定的排序，但是不稳定的排序一定不能变成稳定的排序
希尔排序
缩小增量排序，比如下面的排序
初始数据我们可以分成5组，此时的增量就是5，接着第1个元素与第6个元素，第2个元素与第7个元素等两两交换
接着降低增量（gap / 2），增加每组的数据，继续进行排序
其实前面的增量分组相当于一个预排序，真正的排序是最后一组
//希尔排序public static void shellSort(int[] array){int gap = array.length;while(gap>1){gap /= 2;shell(array,gap);}}/*** 对每组进行排序* 这段代码其实跟插入排序差不多，就是i其实位置在gap上，j每次递减递增gap个单位* @param array* @param gap*/public static void shell(int[] array, int gap){for (int i = gap; i < array.length; i++) {int tmp = array[i];int j = i -gap;for (; j >= 0 ; j-=gap) {if (array[j] > tmp){array[j+gap] = array[j];}else{break;}}array[j+gap] = tmp;}}时间复杂度？
稳定性？不稳定，因为分组交换之后会打乱相同的数字原本的前后顺序
编写个代码来测试一下两者的运行时间
import java.util.Arrays;public class Test {public static void testInsert(int[] array){int[] tmpArray = Arrays.copyOf(array, array.length);long startTime = System.currentTimeMillis();Sort.insertSort(tmpArray);long endTime = System.currentTimeMillis();System.out.println("直接插入排序时间："+(endTime-startTime));}public static void testShell(int[] array){int[] tmpArray = Arrays.copyOf(array, array.length);long startTime = System.currentTimeMillis();Sort.shellSort(tmpArray);long endTime = System.currentTimeMillis();System.out.println("希尔排序时间："+(endTime-startTime));}public static void initArray(int[] array){for (int i = 0; i < array.length; i++) {array[i] = array.length-i;}}public static void main(String[] args) {int[] array = new int[10_0000];initArray(array);testInsert(array);testShell(array);}
}
选择排序
直接选择排序
动图如下：
设置i和j，遍历当前i下标后面的元素（j++），找到一个最小的值与i下标的元素进行替换
然后i++，进行下一个元素的交换
/*** 选择排序* 时间复杂度O(n^2)* 空间复杂度O(1)* 稳定性：不稳定* @param array* @param i* @param j*/public static void swap(int[] array,int i,int j){int tmp = array[i];array[i] = array[j];array[j] = tmp;}public static void selectSort(int[] array){for (int i = 0; i < array.length; i++) {int minIndex = i;//j往后遍历，每次找到比minIndex下标元素小的就进行下标替换for (int j = i+1; j < array.length; j++) {if(array[j] < array[minIndex]){minIndex = j;}}swap(array,i,minIndex);}}双向选择排序
设置最左边下标l和最右边下标r，设置i = l+1，往后遍历，找到最小值的下标和最大值的下标
接着把minIndex的元素与l交换，maxIndex的元素与r交换
接着再i++，l++，r--，重复上面的步骤
注意：如果l的位置就是最大值，经过与最小值交换之后不一定有序
所以我们要把minIndex和maxIndex换过来
public static void selectSort2(int[] array){int left = 0;int right = array.length-1;while(left<right){int minIndex = left;int maxIndex = right;//找到最大值和最小值下标for (int i = left+1; i <= right; i++) {if(array[i] < array[minIndex]){minIndex = i;}if(array[i] > array[maxIndex]){maxIndex = i;}}swap(array,minIndex,left);if(maxIndex == left){maxIndex = minIndex;}swap(array,maxIndex,right);left++;right--;}}堆排序
可以看着我这篇博客的思路数据结构：优先级队列（堆）-CSDN博客
代码如下：
private static void createHeap(int[] array) {for (int parent = (array.length-1-1)/2; parent >= 0 ; parent--) {siftDown(array,parent,array.length);//alt+enter}}private static void siftDown(int[] array,int parent, int length) {int child = 2*parent + 1;while (child < length) {if(child+1 < length && array[child] < array[child+1]) {child++;}if(array[child] > array[parent]) {swap(array,child,parent);parent = child;child = 2*parent+1;}else {break;}}}/*** 时间复杂度：O(N*logN)* 空间复杂度：O(1)* 稳定性：不稳定的排序* @param array*/public static void heapSort(int[] array) {createHeap(array);int end = array.length-1;while (end > 0) {swap(array,0,end);siftDown(array,0,end);end--;}}
交换排序
冒泡排序
动图如下：
/*** 时间复杂度：O(n^2)* 空间复杂度：O(1)* 稳定性：稳定* @param array*/public static void bubbleSort(int[] array){//i代表趟数for (int i = 0; i < array.length-1; i++) {//每一趟都比较上一趟有没有交换boolean flg = false;//j来比较每个数据的大小for (int j = 0; j < array.length-1-i; j++) {if(array[j]>array[j+1]){swap(array,j,j+1);flg = true;}}if(flg==false){break;}}}快速排序
Hoare法
单趟动图如下：
第一轮交换之后，6在中间，6的左边都比6小，右边都比6大
第二轮和第一轮一样，接着不停地递归下去
这些数组可以拆分并组成一棵二叉树如下图，二叉树就是左边和右边分别递归
public static void quickSort(int[] array){quick(array,0,array.length-1);}private static void quick(int[] array, int start, int end){if(start >= end){return;}//找到中间的值int pivot = partitionHoare(array,start,end);//左右分别进行递归quick(array,start,pivot-1);quick(array,pivot+1,end);}接下来我们要来搞定partition的方法，也就是要找到整个序列中间值
先确定第一个元素是pivot元素
right指针负责找到比array[right]小的数字，left指针负责找到比array[left]大的数字
找到了就进行交换，直到左右指针相遇
private static int partitionHoare(int[] array, int left, int right){int tmp = array[left];int i = left;//整个的循环，要求left和right相遇之后能交换数字while(left<right){//单独的循环，因为如果right--一直找不到比tmp大的数，而right不能一直减到最左边的边界//所以需要再规定依次left<rightwhile(left<right && array[right] >= tmp){right--;}while (left<right && array[left] <= tmp){left++;}swap(array,left,right);}swap(array,i,left);return left;}思考：
1.为什么这里要有一个等于号
如果不用=号可能会进入死循环
如果没有等于号，第一个循环因为6不大于6，right没办法--，同理left没办法++，走到后面right和left进行交换，只是相当于6和6这两个元素的下标进行交换而已，整个数组也没有进行排序
2.为什么从右边开始而不是从左边开始？
如果先走左边，有可能会出现相遇的时大的数据，最后把大的数据放在最前面
而先走右边的话可以先遇到小的，可以把小的放到前面
时间复杂度？
最好情况：
根据上方代码的递归分治思想，找到中间值，递归左边递归右边再出中间值，每次出一个中间值都是把一部分一分为二进行寻找（logn）
每次循环都有n个元素要进行遍历
最后总的时间复杂度O(n*logn)
最坏情况：
比如：1 2 3 4 5
递归时right每次找到比1小的值都要遍历n个元素，在循环中每次都要遍历n个元素检查是否进行交换
所以总的时间复杂度就是O(n^2)
⚠快排使用时，数据一般不是逆序或者有序的
⚠快排使用时，往往会有栈的溢出
这个错误跟我们递归的层次有关系，递归越多在栈上开辟的空间就越多，而IDEA默认给出的空间是256KB，这么小的空间容纳不了我们10万个数据进行栈空间的开辟
我们要对IDEA进行一个调整
挖坑法
单趟动图如下：
private static int partitionHole(int[] array, int left, int right){int tmp = array[left];//整个的循环，要求left和right相遇之后能交换数字while(left<right){//单独的循环，因为如果right--一直找不到比tmp大的数，而right不能一直减到最左边的边界//所以需要再规定依次left<rightwhile(left<right && array[right] >= tmp){right--;}array[left] = array[right];while (left<right && array[left] <= tmp){left++;}array[right] = array[left];swap(array,left,right);}array[left] = tmp;return left;}前后指针法
思路：
1、选出一个key，一般是最左边或是最右边的。
2、起始时，prev指针指向序列开头，cur指针指向prev+1。
3、若cur指向的内容小于key，则prev先向后移动一位，然后交换prev和cur指针指向的内容，然后cur指针++；若cur指向的内容大于key，则cur指针直接++。如此进行下去，直到cur到达end位置，此时将key和++prev指针指向的内容交换即可。
/*** 前后指针法：* 总结：* 1. Hoare 优先级: 2* 2. 挖坑法 优先级：1* 3. 前后指针法 优先级：3* 这3种方式 每次划分之后的前后顺序 有可能是不一样的* @param array* @param left* @param right* @return*/private static int partition(int[] array, int left, int right) {int prev = left;int cur = left + 1;while (cur <= right) {if (array[cur] < array[left] && array[++prev] != array[cur]) {swap(array, cur, prev);}cur++;}swap(array, prev, left);return prev;}选择题：
这道题不要太死板地做，题目问我们第8个记录45，那么说明45之前的数字一定是有序的
那45就需要比较到比它小的数就行，很简单选C
快排的优化
上面我们提到了，快排一旦递归较多的时候容易出现栈溢出的情况
所以我们优化方向：1.减少递归次数；2.让每一次都能均匀地分割数组
三数取中法
上面提到当快排的hoare和挖坑法遇到有序数列时，l和r都跑到第一个元素去，右边有一大坨数字，无法实现取到中间数的效果
我们采用三数取中法
1.先找到数列中间下标（m）的数字
int mid = (left+right)/2;
定义大前提
2.找出l，m，r下标的三个数字排在最中间的那个数
array[left]<array[right]
array[left]>array[right]
if(array[left] < array[right]){if(array[mid]<array[left]){return left;}else if(array[mid] > array[right]){return right;}else{return mid;}}else{//array[left] > array[right]if(array[mid]>array[left]){return left;}else if(array[mid] < array[right]){return right;}else{return mid;}}3.把m坐标元素与l坐标元素交换
4.然后以4为基准，利用r--找到比4小的元素，把这个元素与4交换
这样就不会出现找不到左数或者右数的情况
5.接着左右子树进行遍历就行了
if(start>=end){return;}//1 2 3 4 5 6 7int index = middleNum(array,start,end);swap(array,index,start);//4 2 3 1 5 6 7int pivot = partition(array,start,end);quick2(array,start,pivot-1);quick2(array,pivot+1,end);6.排序的最终步骤一般集中在数组二叉树的最后两层，而当排序到这个地方的时候，整个数组已经偏向有序的状态了，所以我们没必要再让二叉树继续递归下去，我们可以采用插入排序，在一个很小的序列中进行排序。这样可以降低树的高度，减少递归的次数
整个的代码
private static int middleNum(int[] array, int left,int right){int mid = (left+right)/2;//求中位数的下标if(array[left] < array[right]){if(array[mid]<array[left]){return left;}else if(array[mid] > array[right]){return right;}else{return mid;}}else{//array[left] > array[right]if(array[mid]>array[left]){return left;}else if(array[mid] < array[right]){return right;}else{return mid;}}}public static void insertSort(int[] array, int left,int right) {for (int i = left+1; i <= right; i++) {int tmp = array[i];int j = i - 1;for (; j >= left; j--) {if (array[j] > tmp) {array[j + 1] = array[j];} else {break;}}array[j + 1] = tmp;}}private static void quick2(int[] array, int start, int end){if(start>=end){return;}if(end-start+1<=15){insertSort(array,start,end);return;}//1 2 3 4 5 6 7int index = middleNum(array,start,end);swap(array,index,start);//4 2 3 1 5 6 7int pivot = partition(array,start,end);quick2(array,start,pivot-1);quick2(array,pivot+1,end);}非递归快排
先利用挖坑法排好序
创建一个栈，把6左边第一个和最后一个元素(pivot-1)的位置放入栈中，右边同理
弹出一个9给r，弹出6给l
再重复一次挖坑法partition方法
9右边的元素不需要递归，所以直接当成pivot
把9左边的第一个元素下标(6)和最后一个元素(7)放入栈中
怎么判断pivot左边和右边有多少个元素呢？
当pivot+1 = e的时候，右边只有1个元素；当pivot+1<e的时候，右边有两个或两个以上的元素
相反当pivot-1>s，左边有两个或两个以上元素
总结步骤：
1.调用partition方法找出整个数组的中间数位置pivot
2.左边有没有两个元素，下标放到栈
3.右边一样
4.判断栈空不空-->不空的话就pop两个元素出来分别交给r和l（注意最先出来的给r，慢一点的给l）
整个代码：
public static void quickSortNor(int[] array){int start = 0;int end = array.length-1;Stack<Integer> stack = new Stack<>();int pivot = partitionHoare(array,start,end);if(pivot>start+1){stack.push(start);stack.push(pivot-1);}if(pivot+1<end){stack.push(pivot+1);stack.push(end);}while(!stack.isEmpty()){end = stack.pop();start=stack.pop();pivot = partitionHoare(array,start,end);if(pivot>start+1){stack.push(start);stack.push(pivot-1);}if(pivot+1<end){stack.push(pivot+1);stack.push(end);}}}归并排序
分治算法+二路归并
分解：
public static void mergeSort(int[] array){mergeSortFun(array,0, array.length-1);}private static void mergeSortFun(int[] array,int start,int end){if(start>=end){return;}//分解int mid = (start+end)/2;mergeSortFun(array,start,mid);mergeSortFun(array,mid+1,end);//合并merge(array,start,mid,end);}归并方法
创建一个tmpArr数组记录排序好的数字
先进行s1和s2两个元素的比较，s2的元素比较小先扔到tmpArr里面，s2++
接着再比较s2和s1，发现s1更小，扔到tmpArr里面，s1++
后面的步骤差不多，比较s1和s2两个元素，谁小谁放进数组
private static void merge(int[] array, int left, int mid,int right) {int s1 = left;int e1 = mid;int s2 = mid+1;int e2 = right;int[] tmpArr = new int[right-left+1];int k = 0;//tmpArr的下标//同时满足两个归并段都有数据while(s1 <= e1 && s2 <= e2){if(array[s1] <= array[s2]){tmpArr[k++] = array[s1++];}else{tmpArr[k++] = array[s2++];}}while(s1 <= e1){tmpArr[k++] = array[s1++];}while(s2 <= e2){tmpArr[k++] = array[s2++];}//把排好的数据拷贝回原来的数组array中for (int i = 0; i < tmpArr.length; i++) {array[i+left] = tmpArr[i];}}时间复杂度
每次都要遍历n个元素，而分解过程分治算法和二路归并的复杂度logn
总的复杂度O(N*logN)
稳定性：稳定
非递归归并
先让每组的两个数据进行排序，接着再让两个组的四个数据进行排序
每组一个数据进行排序
两组的数据排序
int gap = 1;while(gap<array.length){for (int i = 0; i < array.length; i = i+gap*2) {int left = i;int mid = left+gap-1;int right = mid+gap;merge(array,left,mid,right);}gap*=2;}mid和right的定义方式可能会有越界的风险
所以我们需要进行风险修正
if(mid >= array.length){mid = array.length-1;}if(right>=array.length){right = array.length-1;}整个代码：
public static void mergeSortNor(int[] array){int gap = 1;while(gap<array.length){for (int i = 0; i < array.length; i = i+gap*2) {int left = i;int mid = left+gap-1;int right = mid+gap;if(mid >= array.length){mid = array.length-1;}if(right>=array.length){right = array.length-1;}merge(array,left,mid,right);}gap*=2;}}应用
1.先把文件切割成200份，每个512M
2.分别对512M排序，任意排序都行，因为内存放的下
3.进行2路归并，同时对200份有序文件做归并过程，最终结果就是有序了
排序总结
其他排序
计数排序
简单版本
有这么一组数字，要求你进行排序，注意这组数组在0~9之间
1.先申请一个计数数组count，设置一个i，定义co把每个数字出现的次数记录下来。i遍历上面的数字，每次遍历到重复的数字就co++(count[array[i] - minVal]++)
⚠计数数组上面的数字代表数组里面出现的数字，不是下标
如果不一定是以0为最小值的呢？
那我们就需要定义数组最小值minVal和最大值maxVal了
int minVal = array[0];int maxVal = array[0];for (int i = 0; i < array.length; i++) {if(array[i]<minVal){minVal = array[i];}if(array[i]>maxVal){maxVal=array[i];}}数组长度？
//确定计数数组的长度int len = maxVal-minVal+1;int[] count = new int[len]; //遍历array数组 把数据出现的次数存储到计数数组中for (int i = 0; i < array.length; i++) {count[array[i]-minVal]++;}2.设置一个i遍历这个计数数组，把每个数字重复（如果有）记录下来并写回原来的数组
//遍历计数数组，把实际的数组写回array数组int index = 0;for (int i = 0; i < count.length; i++) {while(count[i]>0){//这里需要写回array,得从array的0位置开始写array[index] = i+minVal;index++;//每次写进array一个元素，计数数组的对应元素数量就得减少count[i]--;}}整个代码：
public static void countSort(int[] array){//求数组最大值和最小值 O(N)int minVal = array[0];int maxVal = array[0];for (int i = 0; i < array.length; i++) {if(array[i]<minVal){minVal = array[i];}if(array[i]>maxVal){maxVal=array[i];}}//确定计数数组的长度int len = maxVal-minVal+1;int[] count = new int[len];//遍历array数组 把数据出现的次数存储到计数数组中 O(N)for (int i = 0; i < array.length; i++) {count[array[i]-minVal]++;}//遍历计数数组，把实际的数组写回array数组 //跟最大值和最小值有关系，所以是O(范围)int index = 0;for (int i = 0; i < count.length; i++) {while(count[i]>0){//这里需要写回array,得从array的0位置开始写array[index] = i+minVal;index++;//每次写进array一个元素，计数数组的对应元素数量就得减少count[i]--;}}}时间复杂度：O(MAX(N, 范围))
空间复杂度：O(范围)
稳定性：不稳定
复杂版本（稳定版本）
这里字数太多（主要是我懒~），大家可以去看这篇博客计数排序 - 知乎 (zhihu.com)
基数排序
基数排序动图演示
从低位到高位数字，让每位数字依次有序
代码见下：
1.10 基数排序 | 菜鸟教程 (runoob.com)
桶排序
【排序】图解桶排序_桶排序图解-CSDN博客
