数据小白必看：七大排序算法超详细讲解（下）
个人主页：♡喜欢做梦
欢迎 👍点赞 ➕关注 ❤️收藏 💬评论
目录
交换排序
冒泡排序
基本思想
快速排序
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[j+1]){ swap(array,j,j+1); flg=true; } } if(flg==false){ break; } } }}- 时间复杂度：没有讨论优化的情况下：O（N^2），优化后：O（N）;
- 空间复杂度：O（1）；
- 稳定性：稳定；
快速排序
基本思想
基本思想：任取待排序元素序列中的某元素作为基准值，通过一趟排序将待排序集合分割成两个子序列，左子序列中的所有元素均小于基准值，右子序列中的所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素在相应的位置上。
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=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,那么将会造成死循环。
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=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[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]){ //比较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 =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 stack=new ArrayDeque(); //划分区域 int pivot=partition(array,left,right); //将两边的左右区间放入栈中 if(pivot-1>left){ stack.push(left); stack.push(pivot-1); } if(pivot+1left){ 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=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*logN）；
- 空间复杂度：O（N）；
排序算法总结
