个人主页：♡喜欢做梦
欢迎 ?点赞 ➕关注 ❤️收藏 ?评论
目录
交换排序
冒泡排序
基本思想
快速排序
1.Hoare版
2.挖坑法
3.前后指针法
优化快速排序
快速排序非递归
归并排序
排序算法总结
交换排序
冒泡排序
基本思想
基本思想：将待排序的元素看做是“气泡”，比较相邻两个元素进行交换，每次遍历都会将当前最大（最小）的元素像“气泡”一样，浮到一端。
实现过程：
代码：
public static void bubbleSort(int[] array){ for (int i = 0; i < array.length-1; i++) { boolean flg=false; for (int j = i; j < array.length-i-1 ; j++) { if(array[j]>array[j+1]){ swap(array,j,j+1); flg=true; } } if(flg==false){ break; } } }}快速排序
基本思想
基本思想：任取待排序元素序列中的某元素作为基准值，通过一趟排序将待排序集合分割成两个子序列，左子序列中的所有元素均小于基准值，右子序列中的所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素在相应的位置上。
public static void quickSort(int[] array){ //快速排序入口 quick(array,0,array.length-1); } public static void quick(int[] array,int start,int end){ //递归结束条件 if (start>=end){ return; } //划分区间 int pivot=partition(array,start,end); quick(array,start,pivot-1); quick(array,pivot+1,end); }1.Hoare版
实现过程：
思路：
将最左边的数作为基准数；通过双指针从两端向中间移动，通过内层循环，直到right寻找比tmp大的元素，left寻找比right小的元素，将两下标元素进行交换，直到两指针相遇；将基准数与两指针相遇的位置进行交换，划分左右区间； //Hoare版分割 public static int partitionHoare(int[] array,int left,int right){ int tmp=array[left]; int tmpleft=left; //直到两指针相遇结束循环 while(left<right){ //right寻找比tmp小的元素 //所以只要大于等于tmp，那么right向左移动 while(left<right && array[right]>=tmp){ right--; } //left寻找比tmp大的元素 //所以只要小于等于tmp，那么left向右移动 while(left<right && array[left]<=tmp){ left++; } //将左右指针的元素进行交换 swap(array,left,right); } //将基准数与指针相遇的地方交换，划分左右区间 swap(array,left,tmpleft); return left; }可能有的疑惑：
可不可以后面往前面向后面找，为什么是从后面开始往前面找？答案是不可以的。
如上图所示，从前往后找可能会使left比right更先找到比基准值大的值，然后将他们进行交换，导致左边区间可能出现比基准值大的元素
2.在内层循环，双指针移动过程中为什么left还要写小于right，他进入内层循环的条件不就是left<right吗?
如果要排序的数组是[6,1,4,2],left下标只要没有比tmp下标的元素来的大，那么就要一直向右移动，甚至移到right的右边。right也同理。
3.为什么array[left]和array[right]循环条件为什么还要等于tmp？
如果数组中有相同的元素，而内层循环条件是array[left]<tmp，array[right]>tmp,那么将会造成死循环。
2.挖坑法
实现过程：
思路：
最左边的树作为基准数；通过双指针从两端向中间移动，通过内层循环，直到right寻找比tmp大的元素，将right的元素给left，left寻找比right小的元素，将left的元素给right，直到两指针相遇；将基准数给两指针相遇的位置，划分左右区间；代码：
public static int partition(int[] array,int left,int right){ int tmp=array[left]; while(left<right){ //右指针寻找比tmp小的值给左指针 while(left<right && array[right]>=tmp){ right--; } //将right下标元素给left下标元素 array[left]=array[right]; //左指针寻找比tmp大的值给右指针 while(left<right && array[left]<=tmp){ left++; } //将left下标元素给right下标元素 array[right]=array[left]; } //将基准数给left或者right下标 array[left]=tmp; return left; }3.前后指针法
实现过程：
思路：
初始化prev指向首位置，cur指向prev的下一个位置；如果cur的元素小于基准值，并且prev向后移动一位与cur不等，那么将cur与prev中的元素进行交换；cur遍历完后，交换基准值与left的元素，划分区间。 public static int partition2(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; }优化快速排序
1. 三数取中法选key
public static void quick(int[] array,int start,int end){ //递归结束条件 if (start>=end){ return; } //找到中间元素下标 int midIndex=getMid(array,start,end); //将中间元素与首元素进行比较 swap(array,midIndex,start); //划分区间 int pivot=partition2(array,start,end); quick(array,start,pivot-1); quick(array,pivot+1,end); }private static int getMid(int[] array, int left,int right){ int mid=(left+right)/2; //如果left下标小于right下标元素 if(array[left]<array[right]){ //比较left与mid if(array[left]>array[mid]){ return left; }else if(array[right]<array[mid]){ //比较right与mid return right; }else{ return mid; } //如果left下标大于right下标元素 }else{ //比较left与mid if(array[left]<array[mid]){ return left; }else if(array[right]>array[mid]){ //比较right与mid return right; }else{ return mid; } } }2.递归到小的子区间时，可以考虑使用插入排序
public static void quick(int[] array,int start,int end){ //递归结束条件 if (start>=end){ return; } if(end-start+1<=7){ insertSortRange(array,start,end); } int midIndex=getMid(array,start,end); swap(array,midIndex,start); //划分区间 int pivot=partition2(array,start,end); quick(array,start,pivot-1); quick(array,pivot+1,end); } private static void insertSortRange(int[] array,int start,int end){ //这里end取闭区间 for (int i = start+1; i <= end; i++) { //将下标i中的元素给tmp； int tmp=array[i]; int j = i-1; for (; j >=start; j--) { //将j中的元素与tmp中的元素进行比较 //如果j中的元素大于tmp中的元素，那么将j中的元素放到j+1的元素中 if(tmp<array[j]){ array[j+1]=array[j]; }else{ //否则说明j+1是适合tmp元素的位置，将其插入 array[j+1]=tmp; break; } } array[j+1]=tmp; } }快速排序非递归
实现过程：
思路：
先对整体数组做一次划分；将基准元素两边的左右边界进行入栈；先弹出右边界，在弹出左边界，在左右边界区间中再进行划分，循环此操作直到栈为空为止。代码：
public static void quickSort(int[] array){ //快速排序入口 quickNor(array,0,array.length-1); // quick(array,0,array.length-1); } public static void quickNor(int[] array,int left,int right){ Deque<Integer> stack=new ArrayDeque<>(); //划分区域 int pivot=partition(array,left,right); //将两边的左右区间放入栈中 if(pivot-1>left){ stack.push(left); stack.push(pivot-1); } if(pivot+1<right){ stack.push(pivot+1); stack.push(right); } //只要栈不为空，就代表还不是整体有序 while(!stack.isEmpty()){ //弹出右边界，在弹出左边界 right=stack.pop(); left=stack.pop(); //将左右边界区间在进行分割 pivot=partition(array,left,right); //如果满足条件，在进行入栈 if(pivot-1>left){ stack.push(left); stack.push(pivot-1); } if(pivot+1<right){ stack.push(pivot+1); stack.push(right); } } } //挖坑法 public static int partition(int[] array,int left,int right){ int tmp=array[left]; while(left<right){ //右指针寻找比tmp小的值给左指针 while(left<right && array[right]>=tmp){ right--; } //将right下标元素给left下标元素 array[left]=array[right]; //左指针寻找比tmp大的值给右指针 while(left<right && array[left]<=tmp){ left++; } //将left下标元素给right下标元素 array[right]=array[left]; } //将基准数给left或者right下标 array[left]=tmp; return left; }快速排序总结
快速排序整体的综合性能和使用场景都比较好，所以才敢叫快速排序；稳定性：不稳定；时间复杂度：最好情况：O（N*logN），最坏情况：O^2;空间复杂度：最好情况：O（logN）,最坏情况：O（N）；归并排序
基本思想：
归并排序是一种高效的基于分治策略的排序算法。
分治策略：将一个数组分成两个子数组，然后递归的对这两个子数组进行排序，最后将排好序的子树组合并成一个完整的排序数组。
实现过程：
思路：
分解：
如果子数组只有一个元素返回，也就是当left>=right的时候，停止分解；否则对数组进行左右递归分解；合并：
创建临时数组tmp；用两个指针来比较两个元素大小，将小的放入tmp；将剩余的元素放入tmp中；将数组放入原数组对应的位置。代码：
public static void mergeSort(int[] array){ mergeSortTmp(array,0,array.length-1); } //分解 public static void mergeSortTmp(int[] array,int left,int right){ if(left>=right){ return; } //分解： int mid=(left+right)/2; mergeSortTmp(array,left,mid); mergeSortTmp(array,mid+1,right); //合并 merge(array,left,mid,right); } //合并 public static void merge(int[] array,int left,int mid,int right){ int[] tmp=new int[right-left+1]; int k=0; int s1=left; int s2=mid+1; while(s1<=mid && s2<=right){ if(array[s1]<=array[s2]){ tmp[k++]=array[s1++]; }else{ tmp[k++]=array[s2++]; } } //放入剩余的元素 while(s1<=mid){ tmp[k++]=array[s1++]; } while(s2<=right){ tmp[k++]=array[s2++]; } //保证数组有序 for (int i = 0; i < k; i++) { array[i+left]=tmp[i]; } }排序算法总结
| 排序 | 最好 | 平均 | 最坏 | 空间复杂度 | 时间复杂度 |
| 冒泡排序 | O（n） | O（n^2） | O（n^2） | O（1） | 稳定 |
| 插入排序 | O（n） | O（n^2） | O（n^2） | O（1） | 稳定 |
| 希尔排序 | O（n） | O（n^1.3） | O（n^2） | O（1） | 不稳定 |
| 选择排序 | O（n^2） | O（n^2） | O（n^2） | O（1） | 不稳定 |
| 堆排序 | O（n*log（n）） | O（n*log（n）） | O（n*log（n）） | O（1） | 不稳定 |
| 快速排序 | O（n*log（n）） | O（n*log（n）） | O（n^2） | O（log（n））~O（n） | 不稳定 |
| 归并排序 | O（n*log（n）） | O（n*log（n）） | O（n*log（n）） | O（n） | 稳定 |
