常见的排序算
视图总览：
一，插入排序
1，介绍及实现思路
整个区间被分为
有序区间
无序区间
每次选择无序区间的第一个元素，在有序区间内选择合适的位置插
语言 方法
5689 Q3ltT62b20
ke557石川恋
7152 /04/11 23:40:52
2，代码
//默认为升序排序public static void insertSort(int[] array){ //通过bound划分出两个区间 //[0，bound)表示已排序区间 //[bound，size )为待排序区间 for (int bound = 1; bound < array.length ; bound++) {//默认0号位置已将是排序得了，从1开始 int v = array[bound];//取出bound位置元素往前插 int cur = bound-1; //从bound-1的位置开始找位置, for(;cur >= 0; cur--){ if(array[cur] > v){ //注意如果这个条件写成>=依旧可以完成排序，但是不为稳定排序了 array[cur+1] = array[cur]; }else { break;//找到了合适的位置 } } //此时的cur+1位置即要插入的位置 array[cur+1] = v; }} 3，性能分析
稳定性：
稳定排序
插入排序，初始数据越接近有序，时间效率越高
二，希尔排序
1，介绍及实现思路
希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成个组，所 有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工作。当到达=1 时，所有记录在统一组内排好序。
希尔排序是对直接插入排序的优化。
当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很 快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。
2，代码
public static void shellSort(int[] array){ int gap = array.length/2; while(gap > 1){ //需要循环进行分组插排 shellSortGap(array,gap); gap/=2; } shellSortGap(array,1); //当gap为1时再进行一次插排}public static void shellSortGap(int[] array,int gap){ //通过bound划分出两个区间 //[0，bound)表示已排序区间 //[bound，size )为待排序区间 for (int bound = gap; bound < array.length ; bound++) {//默认0号位置已将是排序得了，从1开始 int v = array[bound];//取出bound位置元素往前插 int cur = bound-gap; //从bound-1的位置开始找位置, //找到同组中的上一个元素 for(;cur >= 0; cur -= gap){ if(array[cur] > v){ //注意如果这个条件写成>=依旧可以完成排序，但是不为稳定排序了 array[cur+gap] = array[cur]; }else { break;//找到了合适的位置 } } //此时的cur+1位置即要插入的位置 array[cur+gap] = v; }} 3，性能分析
稳定性：
不稳定性排序
三，选择排序
1，介绍及实现思路
每一次从无序区间选出最大（或最小）的一个元素，存放在无序区间的最后（或最前），直到全部待排序的数据元
素排完 。
2，代码
public static void selectSort(int[] array){ for (int bound = 0; bound < array.length-1 ; bound++) { //[0,bound)为已排序区间bound位置元素为擂主，循环取出待排序区间元素与擂主比较 //如果小就交换（即打擂成功） for(int cur = bound+1;cur < array.length;cur++){ if(array[bound] > array[cur]){ //打擂成功 int temp = array[bound]; array[bound] = array[cur]; array[cur] = temp; } } }} 3，性能分析
稳定性：
不稳定排序
四，堆排序
1，介绍及实现思路
基本原理也是选择排序，只是不在使用遍历的方式查找无序区间的最大的数，而是通过堆来选择无序区间的最大的
数。
注意：排升序要建大堆；排降序要建小堆。
此处以升序为例：
2，代码
public static void heapSort(int[] array){ //先建大堆 CreatHeap(array); //循环把堆顶元素交换到最后，并调整堆 for (int i = 0; i < array.length-1; i++) { //当堆中只剩一个元素，也不需要进行调整，本来就是有序的 swap(array,0,array.length-1-i); //堆中元素个数为length-i,所以最后一个元素下标为length-i-1 //交换完之后把最后一个元素删掉 //堆的长度又进一步缩水了 //数组中 //[0,array.length-i-1)为待排序区间 //[array.length-i-1,array.length)为已排序区间 shiftDown(array,array.length-i-1,0); }} public static void CreatHeap(int[] array) { //从最后一个非叶子节点出发向前循环，依次进行向下调整 for(int i = (array.length-1-1)/2;i >=0;i--){ shiftDown(array,array.length,i); } } public static void shiftDown(int[] array, int heapLength, int index) { int parent = index; int child = index*2 +1; while(child <heapLength){ if(child+1 < heapLength && array[child+1] > array[child]){ child = child +1; } //条件结束，child已经指向左右子树中较大的数 if(array[child] > array[parent]){ swap(array,child,parent); } parent = child; child = parent*2+1; } } public static void swap(int[] array,int i, int j){ int temp = array[i]; array[i] = array[j]; array[j] = temp;} 3，性能分析
稳定性：
不稳定性排序
五，冒泡排序
1，介绍及实现思路
在无序区间，通过相邻数的比较，将最大的数冒泡到无序区间的最后，持续这个过程，直到数组整体有序 。
2，代码
public static void bubbleSort(int[] array){ //从前往后找最小的方式进行排序 //[0,bound)为已排序区间 //[bound,size)为待排序区间 for(int bound = 0 ; bound < array.length;bound++){ for(int cur = array.length-1;cur > bound; cur--){ if(array[cur-1] > array[cur]){ swap(array,cur-1,cur); } } } } public static void swap(int[] array,int i, int j){ int temp = array[i]; array[i] = array[j]; array[j] = temp;} 3，性能分析
稳定性：
稳定排序
六，快速排序
1，介绍及实现思路
原理：
从待排序区间选择一个数，作为基准值(pivot)；
Partition: 遍历整个待排序区间，将比基准值小的（可以包含相等的）放到基准值的左边，将比基准值大的
（可以包含相等的）放到基准值的右边；
采用分治思想，对左右两个小区间按照同样的方式处理，直到小区间的长度 == 1 代表已经有序，或者小区间的长度 == 0，代表没有数据。
基准值的取法：
1.选择边上（左或者右）
2. 随机选择
3. 几数取中（例如三数取中）：array[left], array[mid], array[right] 大小是中间的为基准值
2，代码
递归实现：
public static void quickSort(int[] array){ //借助这个方法进行辅助递归 //此处为了简单，代码写成前闭后闭区间 quickSortHelper(array,0,array.length-1);}private static void quickSortHelper(int[] array, int left, int right) { if(left>=right){ return; //表示只有一个区间只有一个元素或者没有元素，直接返回 } //针对[left,right]区间进行整理 //index位置即为整理完毕后left和right重合的位置，知道了这个位置才能进一步进行递归 int index = partition(array,left,right); quickSortHelper(array,left,index-1); quickSortHelper(array,index+1,right);}private static int partition(int[] array, int left, int right) { int i = left; int j = right; int base = array[right];//取区间最后一位为基准值 while(i < j){ //从左往右找比基准值大的元素 while(i < j && array[i] <= base){ i++; } //当上面的循环结束之后，i要么和j重合，要么指向了一个比基准值base小大的元素 //从右往左找比基准值小的元素 while(i < j && array[j] >= base){ j--; } //当上面的循环结束之后，i要么和j重合，要么j指向了一个比基准值base小的元素 //交换i和j的值 swap(array,i,j); } //当i和j重合的时候，最后一步，把重合位置元素和基准值的交换 swap(array,i,right); return i;}public static void swap(int[] array,int i, int j){ int temp = array[i]; array[i] = array[j]; array[j] = temp;}
非递归实现：
public static void quickSortByLoop(int[] array) { //借助栈来模拟递归 //stack用来存放数组下标，通过数组下标来表示接下来要处理的区间是啥 Stack<Integer> stack = new Stack<>(); //初始情况下，把左右边界下标入栈，左右边界仍构成闭区间 stack.push(array.length-1); stack.push(0); while(!stack.isEmpty()){ //取出来的顺序和push的顺序刚好相反 int left = stack.pop(); int right = stack.pop(); if(left >= right){ //区间内只有一个或0个元素不需要调整 continue; } //通过partition把数据调整为以基准值为中心，左侧元素小于基准值，右侧元素大于基准值的序列 int index = partition(array,left,right); //准备处理下个区间 //[index+1,right]为基准值右侧范围 stack.push(right); stack.push(index + 1); //[left,index-1]为基准值左侧数据 stack.push(index - 1); stack.push(left); }}public static int partition(int[] array, int left, int right) { int i = left; int j = right; int base = array[right];//取区间最后一位为基准值 while(i < j){ //从左往右找比基准值大的元素 while(i < j && array[i] <= base){ i++; } //当上面的循环结束之后，i要么和j重合，要么指向了一个比基准值base小大的元素 //从右往左找比基准值小的元素 while(i < j && array[j] >= base){ j--; } //当上面的循环结束之后，i要么和j重合，要么j指向了一个比基准值base小的元素 //交换i和j的值 swap(array,i,j); } //当i和j重合的时候，最后一步，把重合位置元素和基准值的交换 swap(array,i,right); return i;}public static void swap(int[] array,int i, int j){ int temp = array[i]; array[i] = array[j]; array[j] = temp;} 3，性能分析
稳定性：
不稳定性排序
七，归并排序
1,介绍及实现思路
归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and
Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使
子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
2,代码
递归实现：
//[low,mid) 有序区间//[mid,high) 有序区间 //把这两个区间合并为一个有序区间 public static void merge(int[] array,int low,int mid,int high){ int[] output = new int[high-low]; //额外空间用来临时存放数据 int outputIndex = 0;//用来记录output中被放入了多少个元素 int cur1 = low; int cur2 = mid; while(cur1 < mid && cur2 < high ){ if(array[cur1] <= array[cur2]){ output[outputIndex] = array[cur1]; outputIndex++; cur1++; } else{ output[outputIndex] = array[cur2]; outputIndex++; cur2++; } } //循环结束肯定是cur1和cur2有一个先到达末尾 //把剩下的元素一股脑拷贝到output中 while(cur1 < mid){ output[outputIndex] = array[cur1]; outputIndex++; cur1++; } while(cur2 < high){ output[outputIndex] = array[cur2]; outputIndex++; cur2++; } //把output中的元素搬运回array中 for (int i = 0; i < high-low; i++) { array[low+i] = output[i]; } } public static void mergeSort(int[] array){ mergeSortHelper(array,0,array.length); }//[low,high)为左闭右开区间.两者差值小于等于1，区间中就只有一个或两个元素 private static void mergeSortHelper(int[] array, int low, int high) { if(high-low <= 1){ return; } int mid = (low + high)/2; //这个方法执行完就认为low mergeSortHelper(array,low,mid); mergeSortHelper(array,mid,high); //当左右区间归并排序完了，说明左右区间已经是有序区间了 //接下来就可以针对两个有序区间合并 merge(array,low,mid,high); }
非递归实现：
public static void mergeSortByLoop(int[] array){ //引入一个gap变量进行分组 //当gap为1的是时候[0） [1）进行合并，[2） [3）进行合并，[4） [5）进行合并，[6）[7）进行合并..... //当gap为2的时候[0,1）和[2,3）进行合并，[4,5）和[6,7）进行合并...... //当gap为4的时候[0,1,2,3）和[4，5，6，7）进行合并..... for (int gap = 1; gap < array.length;gap *= 2){ //接下来进行具体的分组合并 for(int i = 0; i < array.length;i += 2*gap){ //当前相邻组 //[begain,mid) //[mid,end) //begain =>i //mid => i+gap //end => i+2*gap int beg = i; int mid = i+ gap; int end = i + 2*gap; if(mid > array.length){ //防止越界 mid = array.length; } if(end > array.length){ end = array.length; } merge(array,beg,mid,end); } }}public static void merge(int[] array,int low,int mid,int high){ int[] output = new int[high-low]; //额外空间用来临时存放数据 int outputIndex = 0;//用来记录output中被放入了多少个元素 int cur1 = low; int cur2 = mid; while(cur1 < mid && cur2 < high ){ if(array[cur1] <= array[cur2]){ output[outputIndex] = array[cur1]; outputIndex++; cur1++; } else{ output[outputIndex] = array[cur2]; outputIndex++; cur2++; } } //循环结束肯定是cur1和cur2有一个先到达末尾 //把剩下的元素一股脑拷贝到output中 while(cur1 < mid){ output[outputIndex] = array[cur1]; outputIndex++; cur1++; } while(cur2 < high){ output[outputIndex] = array[cur2]; outputIndex++; cur2++; } //把output中的元素搬运回array中 for (int i = 0; i < high-low; i++) { array[low+i] = output[i]; }} 3,性能分析
稳定性：
稳定排序
如果觉得《java中七种常见的排序算法（面试常考！！！）》对你有帮助，请点赞、收藏，并留下你的观点哦！
