七种基于比较的排序，基于Java实现，收藏一下（）

亦余心之所善兮，虽九死其犹未悔。这篇文章主要讲述七种基于比较的排序，基于Java实现，收藏一下？相关的知识，希望能为你提供帮助。
一.总览

文章图片

二.基于比较的排序算法 1.简单插入排序（重点）注意：区间较小时，最快原理：一组数据array[]，认为以下标i为分界，[0，i+1)认为有序，[i+1,array.length)无序，从无序数据中每次取出一个数据，插入有序数据中

文章图片

代码实现：

public static void insertSort(long []array) //数据一共有array.length个 //所以，子操作需要执行array.length次 //减不减一都可以，减一认为第一个数已经有序 for (int i = 0; i < array.length-1 ; i++) //有序[0,i+1)例如刚开始[0,1)有序 //无序[i+1,array.length) //抓取出来的数是[i+1]long key=array[i+1]; int j=0; //依次在有序区间进行比较 for ( j = i; j> =0 ; j--) //[j]就是需要和key比较的数 /** * key< array[j]把array[j]往后移继续往前比较 * key==array[j]把key放入array[j]的后边 * key> array[j]把key放入array[j]的后边 */ if(key< array[j]) array[j+1]=array[j]; else break; array[j+1]=key;

性能分析：

文章图片

2.冒泡排序（重点）原理：
在无序区间，通过相邻数的比较，将最大的数冒泡到无序区间的最后，持续这个过程，直到数组整体有序
无序区间：[0,array,length-i)
有序区间：[array.length-i,array.length)
从下标j开始，将其与下标j+1依次比较，如果大于，交换。

文章图片

代码实现：

public static void bubblingSort(long []array) //外层循环，需要多少次冒泡的过程 for (int i = 0; i < array.length ; i++) //无序区间：[0,array,length-i) //有序区间[array.length-i,array.length)//假设数组已经有序 boolean isSorted=true; //冒泡过程 //只在无序区间中进行 //循环到无序区间的倒数第二个数，然后倒数第二会和倒数第一再比较 for (int j= 0; j< array.length-i-1 ; j ++) if(array[j]> array[j+1]) swap(array, j, j+1); //交换过，说明数组无序 isSorted=false; //如果数组有序，退出循环 if(isSorted) break; public static void swap(long []array,int i,int j) long t=array[i]; array[i]=array[j]; array[j]=t;

性能分析：

文章图片

3.简单选择排序**原理：
每一次从无序区间选出最大（或最小）的一个元素，存放在无序区间的最后（或最前），直到全部待排序的数据元素排完。
以选取最大为例：
无序区间[0,array.length-i)
有序区间[array.length-i,array.length)
动态图为选取最小为例：

文章图片

代码实现：

//选择排序/** *选择大的数 * 前面为有序区间，后面为无序区间 * 再无序区间中遍历，找到最大的数，和无序区间的最后一个数进行交换 */ public static void selectSort(long[]array) //一共多少次选择的过程 for (int i = 0; i < array.length ; i++) //无序区间：[0,array.length-i) //有序区间：[array.length-i,array.length) //记录无序区间最后一个值的下标和值 int maxindex=array.length-i-1; long key=array[array.length-i-1]; for (int j = 0; j < array.length-i ; j++) if(array[j]> key) maxindex=j; key=array[j]; //期望maxIndex指向无序区间的最大值的下标 //交换最大数所在下标和无序区间最后一个数的下标 swap(array, maxindex, array.length-i-1); public static void swap(long[]array,int i,int j) long t=array[i]; array[i]=array[j]; array[j]=t;

性能分析：

文章图片

4.堆排序原理：基本原理也是选择排序，只是不在使用遍历的方式查找无序区间的最大的数，而是通过堆来选择无序区间的最大的数。
注意：排升序要建大堆，排降序要建小堆，否则不行

文章图片

代码实现：

public class HeapSort public static void heapSort(long[]array,int size) //1.建大堆 bulidHeap(array,size); //2.进行选择的过程，一共需要array.length-1组 for (int i = 0; i < array.length-1 ; i++) //无序区间：[0,array.length-i) //有序区间：[array.length-i,array.length) swap(array,0,array.length-i-1); //此时无序区间：[0,array.length-i-1) //无序区间的个数为array.length-i-1 adjustDown(array,array.length-i-1,0); //交换 public static void swap(long[]array,int i,int j) long t=array[i]; array[i]=array[j]; array[j]=t; //建大堆 public static void bulidHeap(long []array,int size) int lastNodeIndex=size-1; int lastParentIndex=(lastNodeIndex-1)/2; for (int i = lastParentIndex; i > =0 ; i--) adjustDown(array,size,i); //向下调整 public static void adjustDown(long[]array,int size,int index) while (true) //堆是完全二叉树，一定有左孩子 int leftIndex=index*2+1; //如果没有左孩子，则为叶子结点,直接return //等于size也超出了数组下标范围 if(leftIndex> =size) return; //找最大的孩子 int maxIndex=leftIndex; int rightIndex=leftIndex+1; //如果右孩子存在且右孩子的值大于左孩子，则将最大值的下标改为右孩子 if(rightIndex< size& & array[rightIndex]> array[leftIndex]) maxIndex=rightIndex; //比较maxIndex和index位置的值，如果maxIndex大，则交换，否则retrun if(array[maxIndex]< =array[index]) return; swap(array, maxIndex, index); index=maxIndex;

性能分析：

文章图片

5.希尔排序原理：
分组插入排序
希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成个组，所有
距离为的记录分在同一组内，并对每一组内的记录进行插入排序。然后，取，重复上述分组和排序的工作。当到达=1时，所有记录在统一组内排好序。
【七种基于比较的排序，基于Java实现，收藏一下（）】步骤：
1.分为gap组，认为gap之前的都是有序的（每组一个数）
2.对分好的每一个组，在组内进行插入排序

文章图片

代码实现：

//希尔排序(带间隔的插入排序） public class ShellSort public static void shellSort(long[]array) int gap=array.length/2; while (true) insertSortWithGap(array, gap); if(gap==1) break; gap=gap/2; public static void insertSortWithGap(long[]array,int gap) //分为gap组，认为gap之前的都是有序的（每组一个数） for (int i =gap; i < array.length ; i++) //记录需要比较的值 long key=array[i]; int j=0; //对每组的值进行插入排序，每组间隔为gap个 for (j =i-gap; j > =0 ; j=j-gap) if(key< =array[j]) array[j+gap]=array[j]; else break; array[j+gap]=key;

性能分析：

文章图片

6.快速排序（重点）原理：快速排序原理：

文章图片

partition分割原理：Hover法

文章图片

文章图片

步骤： 1.选择一个数key（一般选最左边）
2.做partition分隔（小的放左边，大的放右边）
3.分别做左右两个小区间按相同的方式处理（递归）
4.知道（小区间有序：区间数的个数size< =1)
代码实现：

public class QuickSort public static void quickSort(long[]array) //排序的区间为lowIndex到highIndex quickSortInteral(array,0,array.length-1); private static void quickSortInteral(long[]array,int lowIndex,int highIndex) //记录区间内数的个数 //区间是[lowIndex,highIndex] int size=highIndex-lowIndex+1; //当区间内个数小于等于一时，区间有序 if(size< =1) return; //1.选择其中一个数出来（最左边）-> array[lowIndex] //2.执行partition（分隔），小的数放左，大的数放右//keyIndex是经过partition后，选出来的数的最终下标 int keyIndex=partitionHover(array,lowIndex,highIndex); //keyIndex左边：左边的lowIndex=lowIndex，highIndex=keyIndex-1 //keyIndex右边：右边的lowIndex=keyIndex+1，highIndex=highIndex//分别左左右区间相同处理-> 递归 quickSortInteral(array, lowIndex, keyIndex-1); quickSortInteral(array, keyIndex+1, highIndex); //区间为array[lowIndex,highIndex] //1.选择array[lowIndex]作为特殊的数 //2.需要遍历整个区间（不能遗漏任何数），与选择出来的数进行比较 //3.保证小于等于的在最左边，大于等于的数在最右边（但没有顺序要求） private static int partitionHover(long []array,int lowIndex,int highIndex) int leftIndex=lowIndex; int rightIndex=highIndex; //选择的数是最左边的 //注意：选择最左边的数key，要让rightIndex先动起来，不然右边全小于key的情况不好考虑 long key=array[lowIndex]; while (leftIndex< rightIndex) while (leftIndex< rightIndex& & array[rightIndex]> =key) //当右边的值大于key，rightIndex继续往左走 rightIndex--; while (leftIndex< rightIndex& & array[leftIndex]< =key) //当左边的值小于key，leftIndex继续往右走 leftIndex++; //当leftIndex和rightIndex都停下来时，交换 swap(array, leftIndex, rightIndex); //当leftIndex和rightIndex相遇时，循环结束//交换开始选中的值leftIndex和上述停止相遇的值lowIndex swap(array, leftIndex, lowIndex); //返回选中的key值当前的位置 return leftIndex; private static void swap(long[]array,int i,int j) long t=array[i]; array[i]=array[j]; array[j]=t;

性能分析：

文章图片

时间复杂度：每次partition的时间为O（n），然后乘以二叉树的高度
7.归并排序（二路归并）（重点）原理：归并思想：

文章图片

数组合并思想：
创建一个新数组，数组大小个原数组大小相等
遍历将左边和右边两个有序区间，并比较。如同打擂台，小的数放入新数组
最后将新创建的数组复制到原数组即可
整体思想：

文章图片

文章图片

代码实现：

//归并排序 public class MergeSort public static void mergeSort(long[]array) mergeSortInternal(array,0,array.length); //区间范围是左闭右开 //array[lowIndex,highIndex) private static void mergeSortInternal(long[] array, int lowIndex, int highIndex) int size=highIndex-lowIndex; if(size< =1) return; int middleIndex=(highIndex+lowIndex)/2; //区间被分成左右两份 //左区间：[lowIndex,middleIndex) //右区间: [middleIndex,highIndex)//递归 mergeSortInternal(array, lowIndex, middleIndex); mergeSortInternal(array, middleIndex, highIndex); //左右两个区间都有序 mergeLeftAndRight(array,lowIndex,middleIndex,highIndex); //合并两个有序区间 private static void mergeLeftAndRight(long[] array, int lowIndex, int middleIndex, int highIndex) //两个区间数的总数 int size=highIndex-lowIndex; long[]extraArray=new long[size]; //遍历（三个下标，一个数组一个） int leftIndex=lowIndex; int rightIndex=middleIndex; int extraIndex=0; //两个队伍都有人 while (leftIndex< middleIndex& & rightIndex< highIndex) //加等于保证稳定性 if(array[leftIndex]< =array[rightIndex]) extraArray[extraIndex]=array[leftIndex]; leftIndex++; else extraArray[extraIndex]=array[rightIndex]; rightIndex++; extraIndex++; //直到有个队伍没有人 if(leftIndex< middleIndex) //左边队伍有人 while (leftIndex< middleIndex) extraArray[extraIndex++]=array[leftIndex++]; else //右边队伍有人 while (rightIndex< highIndex) extraArray[extraIndex++]=array[rightIndex++]; //最后把数据从extraArray新数组搬回去 //新数组extraArray[0,size) //搬回去的下标范围[lowIndex,highIndex) for (int i = 0; i < size; i++) array[i+lowIndex]=extraArray[i];

性能分析：