Java 排序算法 Java中七种排序算法总结分析
dhdhdhdhg 人气:0前言：对文章出现的一些名词进行解释
排序： 使一串记录，按照其中的某个或某些关键字的大小，递增或者递减排列起来的操作。
稳定性： 假定在排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，a=b，且a在b之前，而在排序后的序列中，a仍然在b之前则这种排序算法是稳定的，否则就是不稳定的。
内部排序： 数据元素全部放在内存中的排序。
外部排序： 数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。
文中所有排序都是升序。
一、插入排序
直接插入排序是一种简单的插入排序法。
1.基本思想
把待排序的记录按照其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有记录全部插完为止，得到一个新的有序序列。这种思想在我们玩扑克牌的时候用到过，在我们码牌时，抽出一个牌，会从后往前依次比较牌面值，然后插入到一个比前面大且比后面小的位置中。
2.直接插入排序
步骤：
1.第一次排序先将第一个元素看成是已排序区间，将其内容保存起来
2.待排序区间是其后面的所有元素，从其后面第一个开始，依次和已排序区间里的元素比较（这里的比较是从后向前比较，也就是从其前一个元素比较到0号位置的元素）
3.如果小于已排序区间中的元素，则将该位置向后挪一位
4.直到找到第一个比其小的元素，此时其后面的所有元素都是比它大的，且都向后挪了一位，这时其后面的位置是空的，将该元素放进来即可。
5.之后取第二个，第三个…第i个依次这样比较即可，即循环起来。其中每次[0,i)是已排序区间，[i,size)是待排序区间。
动图演示：
代码实现：
public static void insertSort(int[] array){
int j=0;
//i位置与之前所有下标从后往前进行比较，该位置大于i则继续往前，小于则插入到后边
//[0,bound)已排序区间
//[bound,size)待排序区间
for(int bound=1;bound<array.length;bound++) {
int temp = array[bound];
//先取已排序区间的最后一个，依次往前进行比较
for (j = bound - 1; j >= 0; j--) {
//如果temp小于，则将元素往后移一位
if (array[j]>temp) {
array[j + 1] = array[j];
} else {
break;
}
}
//找到合适位置，填充
array[j + 1] = temp;
}
}
相关特性总结：
时间复杂度：O(N2)
空间复杂度：O(1)
稳定性：稳定（是从后往前依次比较的）
应用场景：元素越接近有序越好（因为越接近有序比较次数就会越少，算法的时间效率就会越高）
3.希尔排序(缩小增量排序)
基本思想：
把待排序区间中所有记录分成几个组，设置一个gap值，所有距离为gap的记录分在同一组内，并分别对每个组内的记录进行排序，然后让gap以一定的规律减小，然后重复上述分组和排序的工作，当gap达到1时，所有记录已经排好序。
步骤：
1.设置gap值（每个组内元素之间间隔）
2.在每个组内进行直接插入排序
3.缩小gap值（这里我按照2倍缩小）
4.gap为1时排序完毕
图象解释：
代码实现：
public static void shellSort(int[] array){
int gap= array.length/2;
while(gap>0){
int j=0;
//i位置与之前所有下标从后往前进行比较，该位置大于i则继续往前，小于则插入到后边
for(int bound=gap;bound<array.length;bound+=gap) {
int temp = array[bound];
for (j = bound - gap; j >= 0; j-=gap) {
if (array[j]>temp) {
array[j + gap] = array[j];
} else {
break;
}
}
array[j + gap] = temp;
}
gap=gap/2;
}
}
相关特性总结：
希尔排序是对直接插入排序的优化
当gap>1时都是预排序，目的是让数组更接近有序，当gap==1时，数组已经接近有序，这样就很会快，整体而言，可以达到优化的效果
时间复杂度不确定，因为gap取值方法有很多
空间复杂度：O(1)
稳定性：不稳定（元素之间是跳着交换的）
二、选择排序
1.基本思想
每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。
2.直接选择排序
步骤：
1.先记录下标为0元素为最小值
2.从下标为1开始往后遍历，遇到比最小值还小的就标记起来，遍历完成即找到最小值
3.将找到的最小值与下标为0的元素进行交换
4.此时[0,1）为已排序区间，即不再动，[1,size)是待排序区间
5.从下标为1继续上面的操作，即循环起来
6.循环到最后只剩一个元素结束，排序完成
动图演示：
代码实现：
public static void selectSort(int[] nums) {
//每次都和第一个元素相比，如果小于则和一个元素则交换
for(int bound=0;bound<nums.length-1;bound++){
//先记录最小值为第一个元素
int min=bound;
//从其后一个开始遍历，找出后面所有元素中的最小值
for(int i=bound+1;i<nums.length;i++){
if(nums[min]>nums[i]){
min=i;
}
}
//将最小值与待排序区间第一个进行交换
swap(nums,bound,min);
}
}
相关特性总结：
时间复杂度：O(N2)
空间复杂度：O(1)
稳定性：不稳定
效率不是很好，实际中很少使用
3.堆排序
堆排序是指利用堆这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。
注意：排升序要建大堆，排降序要建小堆
步骤：
1.创建一个大堆（升序）
从倒数第一个非叶子结点开始向下调整，直到根结点，创建一个大堆
2.将根结点与最后一个结点进行交换，此时最后一个元素一定是所有元素中最大的
3.将size–
4.将堆继续调整好形成一个大堆，继续上面的操作，即循环起来
5.最终排序完成
图像解释：
代码实现：
//写一个交换函数
private static void swap(int[] array,int parent,int child){
int temp=array[child];
array[child]=array[parent];
array[parent]=temp;
}
//排升序建大堆
//向下调整，上篇博客提到了
private static void shiftDown(int[] array,int parent,int size){
int child=parent*2+1;
while(child<size){
if(child+1<size&&array[child+1]>array[child]){
child+=1;
}
if(array[parent]<array[child]){
swap(array,parent,child);
parent=child;
child=parent*2+1;
}else{
return;
}
}
}
//堆排序
public static void heapSort(int[] array){
//创建一个堆
int size=array.length;
for(int root=(size-2)/2;root>=0;root--){
shiftDown(array,root,size);
}
while(size>1){
//将第一个和最后一个元素进行交换
swap(array,0,size-1);
//交换完成向下调整
size--;
shiftDown(array,0,size);
}
}
相关特性总结：
时间复杂度：O(NlogN)
空间复杂度：O(1)
稳定性：不稳定
使用堆来选数，效率高了很多
三、交换排序
1.基本思想
交换，就是根据序列中两个记录键值的比较结果来兑换这两个记录在序列中的位置，交换序列的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的头部移动
2.冒泡排序
步骤：
1.从0号位置开始，将元素和他后面的元素比较，如果大于则交换
2.当遍历完成，最大的元素肯定在数组的最后
3.之后再比较时，最后一个元素就是已排序区间，不再参与比较
4.重复上述步骤，即循环起来
动图演示：
代码实现：
public static void bubbleSort(int[] nums) {
//外层循环控制循环次数
for(int num=1;num<nums.length;num++){
//内层循环控制交换哪两个元素
for(int i=0;i<nums.length-num;i++){
if(nums[i+1]<nums[i]){
swap(nums,i+1,i);
}
}
}
}
相关特性总结：
时间复杂度：O(N2)
空间复杂度：O(1)
稳定性：稳定
冒泡排序在最开始就已经学到，很容易理解
3.快速排序（递归与非递归）
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该基准值将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后左右子序列重复该过程，直到所有元素都排列在相应的位置上为止。
主框架实现：
public static void quickSort(int[] array,int left,int right){
if((right-left)<=1){
return;
}
//按照基准值对array数组的[left,right)区间中的元素进行划分
int div=partition3(array,left,right);
//划分成功后以div为边界形成了左右两部分[left,div)和[div+1,right)
//递归排[left,div)
quickSort(array,left,div);
//递归排[div+1,right)
quickSort(array,div+1,right);
}
从上述程序可以看出，程序结构与二叉树前序遍历规则非常像。
接下来按照基准值划分就是快排的核心，常见方法有三种：
1.Hoare版
步骤：
1.这里我们取最右侧为基准值
2.设置begin和end用来标记，让begin从左往右走，end从右往左走
3.当begin小于end时，因为我们取得基准值为最右侧，所以应先让begin从左往右走，找到比基准值大的元素就停下来
4.这时让end从右往左走，找到比基准值小的元素就停下来，两者交换位置
5.循环起来
6.当循环结束时，两个最终走到了同一个位置，将其和基准值进行交换
动图演示：
代码实现：
private static int partition1(int[] array,int left,int right){
int temp=array[right-1];
//begin从左往右找
int begin=left;
//end从右往左找
int end=right-1;
while(begin<end){
//让begin从前往后找比temp大的元素，找到之后停下来
while(array[begin]<=temp&&begin<end){
begin++;
}
//让end从后往前找比temp小的元素，找到之后停下来
while(array[end]>=temp&&begin<end){
end--;
}
//当两个在同一个位置时，不需要交换，减少交换次数
if(begin!=end){
swap(array,begin,end);
}
}
if(begin!=right-1){
swap(array,begin,right-1);
}
return begin;
}
2.挖坑法
步骤：
1.先将基准值（这里是最右侧元素）放在临时变量temp中，这里就形成第一个坑位
2.设置begin和end用来标记，让begin从左往右走，end从右往左走
3.当begin小于end时，让begin从左往右走，找到比temp大的值，去填end的坑，同时begin这里形成一个坑位
4.然后让end从右往左走，找到比temp小的值，去填begin的坑，同时end这里形成了一个新的坑位
5.就这样一直循环，互相填坑，直到不满足循环条件
6.这时begin和end在同一个坑位，且是最后一个坑位，使用基准值填充
图象解释：
代码实现：
private static int partition2(int[] array,int left,int right){
int temp=array[right-1];
int begin=left;
int end=right-1;
while(begin<end){
//让begin从前往后找比基准值大的元素
while(array[begin]<=temp&&begin<end){
begin++;
}
if(begin!=end){
//begin位置找到了一个比temp大的元素，填end的坑
array[end]=array[begin];
//begin位置形成了一个新的坑位
}
//让end从后往前找比基准值小的元素
while(array[end]>=temp&&begin<end){
end--;
}
if(begin!=end){
//end位置找到了一个比temp小的元素，填begin的坑
array[begin]=array[end];
//end位置形成了一个新的坑位
}
}
//begin和end位置是最后的一个坑位
//这个坑位使用基准值填充
array[begin]=temp;
return begin;
}
3.前后标记法（难理解）
小编其实也是根据大佬的代码分析出来的，要问为什么这么做咱确实也是不太理解，另外如理解错误欢迎指正
这里真诚发问，大佬们的脑子是不是和我的脑子不太一样？
步骤：
1.采用cur和prev来标记，两者都是从左往右走，不一样的是，最开始cur在0号位置，prev在cur前一个位置上
2.当遇到比temp大的元素时，prev不动，cur向前走一步，当两者一前一后的状态时，cur也会往前走一步，而prev不动
3.这样两者逐渐拉开差距，此时遇到比基准值小的元素，cur中的元素就会与prev中的元素交换
4.走到最后prev的下一个元素与基准值位置交换
图象解释：
代码实现：
private static int partition3(int[] array,int left,int right){
int temp=array[right-1];
int cur=left;
int prev=cur-1;
//让cur从前往后找比基准值小的元素
while(cur<right){
if(array[cur]<temp&&++prev!=cur){
swap(array,cur,prev);
}
cur++;
}
//将基准值的位置放置好
if(++prev!=right-1){
swap(array,prev,right-1);
}
return prev;
}
但是会发现：
当我们选取的基准值越靠近整个数组的中间时，效率越好，这时可以看作是将数组逐渐分成了一个满二叉树，因此效率为O(NlogN)
最差时是取到其最大或者最小的元素，还是要划分n次，效率为O(N2)
一般时间复杂度都是看起最差情况，那为什么快速排序的时间复杂度是O(NlogN)呢？
其实是可以对取基准值进行优化的，详情请看下面：
4.快速排序优化
1.三数取中法选temp
之前我们只取一个基准值
优化后，我们在左边取一个，中间取一个，右边取一个
比较三个数的大小，谁在中间就取谁为基准值
private static int getIndexOfMid(int[] array,int left,int right){
int mid=left+((right-left)>>1);
if(array[left]<array[right-1]){
if(array[mid]<array[left]){
return left;
}else if(array[mid]>array[right-1]){
return right-1;
}else{
return mid;
}
}
在更改上面的划分方法中，只需要看看上面取出的基准值在不在最右侧，如果不在就与最右侧的值交换，这样代码改动就比较小。
int index=getIndexOfMid(array,left,right);
if(index!=right-1){
swap(array,index,right-1);
}
2.递归到小的子区间时，可以考虑使用插入排序
在Idea的内层方法中，用的是小于47使用直接插入排序
5.快速排序非递归
如果直接转为循环不好转，之前提到可以使用栈来实现，利用栈后进先出的特性
public static void quickSortNor(int[] array){
Stack<Integer> s=new Stack<>();
s.push(array.length);
s.push(0);
while(!s.empty()){
int left=s.pop();
int right=s.pop();
if((right-left)<47){
insertSortQuick(array,left,right);
}else{
int div=partition1(array,left,right);
//先压入基准值的右半侧
s.push(right);
s.push(div+1);
//再压入基准值的左半侧
s.push(div);
s.push(left);
}
}
}
6.相关特性总结
时间复杂度：O(NlogN)
空间复杂度：O(logN)(递归单次没有借助辅助空间，高度即是深度)
稳定性：不稳定
快速排序整体综合性能和使用场景都是比较好的，所以才叫快速排序
四、归并排序（递归与非递归）
归并排序是建立在归并操作上的一种有效的排序算法，该算法是采用分治法的一个非常典型的应用。将已有的子序列合并，得到完全有序的序列，即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
动图演示：
归并排序核心步骤：将两个有序数组合并成一个有序数组
private static void mergeData(int[] array,int left,int mid,int right,int[] temp){
int begin1=left,end1=mid;
int begin2=mid,end2=right;
int index=left;
while(begin1<end1&&begin2<end2){
//依次比较每一位上的元素，小的放入temp同时下标后移一位
if(array[begin1]>array[begin2]){
temp[index++]=array[begin2++];
}else {
temp[index++]=array[begin1++];
}
}
//看两个数组哪个还没有遍历完成，直接顺次放入temp数组的后面
while(begin1<end1){
temp[index++] = array[begin1++];
}
while(begin2<end2){
temp[index++]=array[begin2++];
}
}
主程序（递归）：
步骤：
1.先对待排序区间进行均分为两个
2.使用递归，直到均分为每个区间只剩下一个元素时，每两个使用二路归并
3.将两个有序数组合并为一个有序数组，将结果保存在temp中
4.最终temp保存的就是排序完成的数组，再拷贝回原数组中
private static void mergeSort(int[] array,int left,int right,int[] temp){
if((right-left>1)){
//先对[left,right)区间中的元素进行均分
int mid=left+((right-left)>>1);
//[left,mid)
mergeSort(array,left,mid,temp);
//[mid,right)
mergeSort(array,mid,right,temp);
//二路归并
mergeData(array,left,mid,right,temp);
//将temp中的元素拷贝回原数组中
System.arraycopy(temp,left,array,left,right-left);
}
}
主程序（非递归）：
直接采用gap对数组进行分割，每次分割完成对gap*2，一开始为2个采用二路归并，之后4个，8个，直到大于等于size结束。
非递归比递归思路更加简单。
public static void mergeSortNor(int[] array){
int size=array.length;
int gap=1;
while(gap<size){
for(int i=0;i<size;i+=2*gap){
//划分好要归并的区域，第一次每个区间只有一个元素
//[left,mid)
int left=i;
int mid=left+gap;
//[mid,right)
int right=mid+gap;
if(mid>size){
mid=size;
}
if(right>size){
right=size;
}
int[] temp=new int[size];
//二路归并
mergeData(array,left,mid,right,temp);
//将temp中的元素拷贝回原数组中
System.arraycopy(temp,left,array,left,right-left);
}
//gap值翻二倍，继续归并
gap<<=1;
}
}
相关特性总结：
时间复杂度：O(NlogN)
空间复杂度：O(N)
稳定性：稳定
缺点在于需要O(N)的空间复杂度，归并排序解决更多的是磁盘中的外排序问题
加载全部内容