排序算法总结
2021/6/12 20:21:55
本文主要是介绍排序算法总结,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
排序算法总结
一.交换排序
1.冒泡排序
原理: 比较相邻的元素,如果前者比后者大,就交换他们两个,对从前往后对每一对相邻元素作同样的工作,这样一趟冒泡后,最后的元素就是最大的数。这样每一趟冒泡确定一个元素的位置,n趟后数组即有序。同样也可以从后往前冒泡,依次确定最小值。
原始版的冒泡(如果出现全部数已经排序好,但循环还没结束会出现不必要的时间浪费)
public static void bubble(int []a) { if(a.length==0) return ; int t=a.length; for(int i=0;i<t-1;i++) //在每一趟中确定最大的数,每一趟(如果有数的位置发生改变)都能最终确定一个数的位置 { for(int j=0;j<t-i-1;j++) //逐一遍历整个数组,除了已经确定好位置的数 { if(a[j]>a[j+1]) //石沉法,前面的数大于后面的数就交换两个数的位置 { int temp=a[j]; a[j]=a[j+1]; a[j+1]=temp; } } } }
改进版的冒泡法:(标志法)
public static void bubble(int []a) { if(a.length==0) return ; int t=a.length; boolean flag; for(int i=0;i<t-1;i++) //在每一趟中确定最大的数,每一趟(如果有数的位置发生改变)都能最终确定一个数的位置 { flag=false; for(int j=0;j<t-i-1;j++) //逐一遍历整个数组,除了已经确定好位置的数 { if(a[j]>a[j+1]) //石沉法,前面的数大于后面的数就交换两个数的位置 { flag=true; int temp=a[j]; a[j]=a[j+1]; a[j+1]=temp; } } if(!flag) break; //这一趟中的数没有发生位置交换说明所有的数已经排序成功了. } }
特征分析:
1、空间复杂度O(1),最好时间复杂度O(n),最坏时间复杂度O(n2),平均时间复杂度O(n2)。
2、冒泡排序是稳定的(因为交换的数都是相邻的):同一类型的数相对位置不会改变.
应用:
1.利用冒泡的每一趟排序都能确定一个数的最终位置,可以适合在规模巨大的数据中找到前n大(小)的数,即进行n次外循环即可.
2.利用冒泡的稳定性,可以在对一组数据进行操作时不改变同一类型数据的相对位置. 比如在一个数组中把所有奇数放在偶数前且不改变相对位置关系.
2.快速排序
原理: 快速排序原理是首先要找到一个中枢,把小于中枢的值放到他前面,大于中枢的值放到他的右边,然后再以此方法对这两部分数据分别进行快速排序,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
基本思路:
快排算法是基于分治策略的排序算法,其基本思想是,对于输入的数组 a[low, high],按以下三个步骤进行排序。
(1)分解:以 a[p] 为基准将 a[low: high] 划分为三段 a[low: p-1],a[p] 和 a[p+1: high],使得 a[low: p-1] 中任何一个元素小于等于 a[p], 而 a[p+1: high] 中任何一个元素大于等于 a[p]。
(2)递归求解:通过递归调用快速排序算法分别对 a[low: p-1] 和 a[p+1: high] 进行排序。
(3)合并:由于对 a[low: p-1] 和 a[p+1: high] 的排序是就地进行的,所以在 a[low: p-1] 和 a[p+1: high] 都已排好序后,不需要执行任何计算,a[low: high] 就已经排好序了。
public static void quicksort(int []a,int left,int right) //固定基准,以中间数为例 { if(a.length==0||left>=right) return ; int mid=a[(left+right)/2]; int i=left; int j=right; while(i<=j) { while(i<=j&&a[i]<mid) i++; while(i<=j&&a[j]>mid) j--; if(i<=j) { int temp=a[i]; a[i]=a[j]; a[j]=temp; i++; j--; } } //跳出循环后,i的左边是小于mid的数,j的右边是大于mid的数 quicksort(a,left,j); quicksort(a,i,right); }
public static int partion(int []a,int left,int right) //挖坑法 { if(a.length==0||left>=right) return -1; int i=left; int j=right; int pet=a[left]; while(i<j) { while(i<j&&a[j]>pet) j--; if(j<=i) break; a[i]=a[j]; while(i<j&&a[i]<=pet) i++; //跳出循环的时候,i的左边的数都<=pet if(j<=i) break; //越界,所有的数都搜索完 a[j]=a[i]; } //当i==j的时候,就是基数的位置 a[i]=pet; return i; } public static void quicksort_(int []a,int left,int right) //挖坑法 { if(a.length==0||left>=right) return ; int pos= partion(a,left,right); quicksort_(a,left,pos-1); quicksort_(a,pos+1,right); }
这个做法有点类似双指针思想,每一趟都划分出两个不同范围,再进行进一步的排序,体现了分治的思想
应用: 获取第k小的数
public static int partion(int []a,int left,int right) //挖坑法,进行一轮划分,每一轮确定一个数的最终位置 { if(a.length==0||left>=right) return -1; int i=left; int j=right; int pet=a[left]; //选定最左边的数为基数 while(i<j) { while(i<j&&a[j]>pet) j--; //跳出循环的时候,j的右边都是大于基数的数 if(j<=i) break; a[i]=a[j]; while(i<j&&a[i]<=pet) i++; //跳出循环的时候,i的左边的数都<=pet if(j<=i) break; //越界,所有的数都搜索完 a[j]=a[i]; } //当i==j的时候,就是基数的位置 a[i]=pet; return i; } public static int quicksort_(int []a,int left,int right,int k) //挖坑法,获取第k小的数 { if(left==right&&k==1) return a[left];//递归结束条件:数组只有一个数了,k=1的情况 int pos= partion(a,left,right); int tem=pos-left+1;//小于或等于每一趟选定的基数的数的数量 if(k<=tem) return quicksort_(a,left,pos,k); else return quicksort_(a,pos+1,right,k-tem); }
特征分析:
(1) 时间复杂度最好为O(nlog2n),最差为n^2(退化成单支树,根本上是因为基数的选择问题) 空间复杂度为O(log2n)
(2)该排序算法不稳定,不能保证排序后同一类型的数相对位置不会改变.
(3) 该算法在数据规模巨大,完全无序的情况下的效率最高.在处理小规模数据时的表现不好.这个时候可以改用插入排序。
(4) 快速排序采用了一种分治的策略,通常称其为分治法,现在各种语言中自带的排序库很多使用的都是快速排序。这种分治可以应用于各种不同情景,比如获取第k小的数.
改进方法:(针对枢轴的选择)
1、选取随机数作为枢轴。
2、使用左端,右端和中心的中值做为枢轴元。
3、每次选取数据集中的中位数做枢轴。
插入排序
1.直接插入排序
基本思想:每步将一个待排序的纪录,按其关键字的大小插入到已经排好序的有序数据中,直到全部插入完为止。
public static void insertsort(int []a) { if(a.length==0) return ; for(int i=0;i<a.length;i++) //每趟将a[i]插入到前面的排序子序列中 { int temp=a[i]; int j=i-1; while(j>=0&&temp<a[j]) //如果前面的数比a[i]大则交换位置 { a[j+1]=a[j]; j--; } a[j+1]=temp; } }
2.折半插入排序
在直接插入排序的基础上,如果数据量比较大,为了减少关键码的比较次数,可以使用折半插入来寻找要插入的位置。但是仍然不改变此算法的时间复杂度O(n^2),空间复杂度为O(1). 该算法具有稳定性
public static int Binary(int []a,int index,int x) //在数组中找到大于x的第一个数,即插入的位置 { int left=0; int right=index; while(left<=right) { int mid=(left+right)/2; if(a[mid]>x) { right=mid-1; } else left=mid+1; } return left; } public static void insertsort(int []a) { if(a.length==0) return ; for(int i=0;i<a.length;i++) { int temp=a[i]; int j=i-1; if(j>=0) { int ans=Binary(a,j,temp); //System.out.println(ans); for(int k=j;k>=ans;k--) //把ans以及后面的数全都挪后一位 { a[k+1]=a[k]; } a[ans]=temp; //填数 } } }
插入排序适用于已有部分数据有序的情况,有序部分越大越好。
选择排序
简单选择排序
它的工作原理是每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完。
public static void simpleSelectSort(int []a) { if(a.length==0) return ; int min; for(int i=0;i<a.length-1;i++) { min=i; for(int j=i+1;j<a.length;j++) { if(a[j]<a[min]) { min=j;//记录最小值的下标 } } if(min!=i) //在后面的数找到最小值,就交换 { int temp=a[i]; a[i]=a[min]; a[min]=temp; } } }
特征分析:
1、空间复杂度O(1),最好/最坏/平均时间复杂度都是O(n2),比较次数O(n2),移动次数O(n)。
2、选择排序是不稳定的排序方法
归并排序
归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。
public static void Mergesort(int []a,int []b,int start,int end) { if(a.length==0) return ; if(start==end) { b[start]=a[start]; return ; } int mid=(start+end)/2; //取中间点 Mergesort(a,b,start,mid); //将数组左部分排好序 Mergesort(a,b,mid+1,end);//将数组右部分排好序 int i=start; int j=mid+1; //双指针 int t=start; while(i<=mid&&j<=end) { if(i<=mid&&a[i]<=a[j]) { b[t++]=a[i++]; } if(j<=end&&a[j]<=a[i]) { b[t++]=a[j++]; } } while(i<=mid) b[t++]=a[i++]; while(j<=end) b[t++]=a[j++]; for(int k=start;k<=end;k++) { a[k]=b[k]; } }
特征分析:
1.归并排序的最好、最坏和平均的时间复杂度都为O ( n l o g n ) ,空间复杂度为O(n)
2. 因为它需要进行元素的两两比较所以不存在跳跃,所以归并排序是稳定的排序算法,但递归实现的归并排序需要的额外空间比较大,而迭代实现则相对较小,运行时间开销也较小,因此应尽量使用迭代方法。
3.该算法体现了分治思想,但和快速排序有所不同.该算法可以类比树的后序遍历.
应用场景:
求一个数组中逆序对的个数.
为什么逆序对要用归并排序呢?
该算法是从底向上计算的,每次归并的前提是两组数组都是有序的,在合并前就计算好两个数组分别初始的逆序对,再进行合并.在两部分有序的数组里找逆序对其实有点贪心思维在里面.本质上也是分治(大问题分解成一个个小问题)
static int ans=0; public static void Mergesort(int []a,int []b,int start,int end) { if(a.length==0) return ; if(start==end) { b[start]=a[start]; return ; } int mid=(start+end)/2; //取中间点 Mergesort(a,b,start,mid); //将数组左部分排好序 Mergesort(a,b,mid+1,end);//将数组右部分排好序 int i=start; int j=mid+1; //双指针 int t=start; while(i<=mid&&j<=end) //左右指针各自移动一次算一趟 { if(a[i]<=a[j])//左指针的移动,'='是因为两个相同的数不算逆序 { b[t++]=a[i++]; } else if(a[j]<a[i]) //右指针的移动,当右指针移动时才需要记录逆序对的个数 { b[t++]=a[j++]; ans+=(mid-i+1); //数组左部分大于a[j]的数的个数,每一个右指针的移动都要计算 } } while(i<=mid) b[t++]=a[i++]; while(j<=end) b[t++]=a[j++]; for(int k=start;k<=end;k++) { a[k]=b[k]; }
堆排序
堆的结构可以分为大根堆和小根堆,是一个完全二叉树,而堆排序是根据堆的这种数据结构设计的一种排序
堆的定义性质:
大根堆:arr(i)>arr(2i+1) && arr(i)>arr(2i+2)
小根堆:arr(i)<arr(2i+1) && arr(i)<arr(2i+2)
基本思想:
1.首先将待排序的数组构造成一个大根堆,此时,整个数组的最大值就是堆结构的顶端
2.将顶端的数与末尾的数交换,此时,末尾的数为最大值,剩余待排序数组个数为n-1
3.将剩余的n-1个数再构造成大根堆,再将顶端数与n-1位置的数交换,每一趟都能确定一个数(在n-1中最大的)的位置,如此反复执行,便能得到有序数组
public static void headsort(int []a) { if(a.length==0) return ; for(int t=a.length/2-1;t>=0;t--) //从第一个非叶子节点开始调整 { adjust(a,t,a.length); } for(int t=a.length-1;t>0;t--) //每一趟都确定最大的数,放在数组的末尾 { swap(a,0,t); adjust(a,0,t); } } public static void adjust(int []a,int i,int length)//在[i,length)内调整为大根堆 { int t=length; int ans=a[i]; int j=i; //j表示a[i]应该插入的位置 for(int k=2*i+1;k<t;k=2*k+1) //遍历左孩子 { if(k+1<t&&a[k]<a[k+1]) //确定左右孩子最大的点 { k++; } if(a[k]>ans) { a[j]=a[k]; j=k; } else break; //找到最终a[i]应该插入的位置 } a[j]=ans; } public static void swap(int []a,int i,int j) { int temp=a[i]; a[i]=a[j]; a[j]=temp; }
特征分析:
1、空间复杂度O(1),平均时间复杂度O(n log n),依次堆调整O(log n)——即堆的高度。由于建初始堆所需的比较次数较多,所以堆排序不适宜于记录数量较少的情况。
2、堆排序时不稳定的。
这篇关于排序算法总结的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-06小米11i印度快充版ROM合集:极致体验,超越期待
- 2024-10-06【ROM下载】小米11i 5G 印度版系统, 疾速跃迁,定义新速度
- 2024-10-06【ROM下载】小米 11 青春活力版,青春无极限,活力全开
- 2024-10-05小米13T Pro系统合集:性能与摄影的极致融合,值得你升级的系统ROM
- 2024-10-01基于Python+Vue开发的医院门诊预约挂号系统
- 2024-10-01基于Python+Vue开发的旅游景区管理系统
- 2024-10-01RestfulAPI入门指南:打造简单易懂的API接口
- 2024-10-01初学者指南:了解和使用Server Action
- 2024-10-01Server Component入门指南:搭建与配置详解
- 2024-10-01React 中使用 useRequest 实现数据请求