Java排序算法
2021/8/2 20:38:58
本文主要是介绍Java排序算法，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！
Java排序算法
- 1.冒泡排序
- 1.1冒牌排序的思想
- 1.2算法描述
- 1.3代码实现
- 1.4算法分析
- 2.选择排序
- 2.1选择排序的思想
- 2.2算法描述
- 2.3代码实现
- 2.4算法分析
- 3.插入排序
- 3.1 插入排序思想
- 3.2算法描述
- 3.3代码实现
- 3.4算法分析
- 4.堆排序
- 4.1堆排序的思想
- 4.2算法描述
- 4.3代码实现
- 4.4算法分析
- 5.希尔排序
- 5.1希尔排序的思想
- 5.2算法描述
- 5.3代码实现
- 5.4算法分析
- 6.归并排序
- 6.1归并排序的思想
- 6.2算法描述
- 6.3代码实现
- 6.4算法分析
- 7.快速排序
- 7.1快速排序的思想
- 7.2算法描述
- 7.3代码实现
- 7.4算法分析
1.冒泡排序
1.1冒牌排序的思想
冒泡排序是一种简单的排序算法。它重复的访问要排序的数列，一次进行两个元素的比较操作，如果他们的顺序与预期想法不同则进行元素之间的交换过程。重复进行元素之间的比较操作直到元素不再需要交换，继而该排序过程已经完成。
1.2算法描述
- 比较相邻元素，如果前者元素大于后者就交换元素。
- 每次比较都比较的是每一对相邻的元素，一轮过后，最大的元素会出现在最后。
- 重复上述步骤，直至排序完成。
1.3代码实现
public static void bubbleSort(int[] array){
if(array==null||array.length==0){
return;
}
for(int i =0;i<array.length-1;i++){
for(int j =0;j<array.length-1-i;j++){
if(array[j]>array[j+1]){
int tmp=array[j];
array[j]=array[j+1];
array[j+1]=tmp;
}
}
}
}
上述代码存在重复比较的情况，尤其是若后序排列均为正常排列时，还是会重复比较，所以为了减少这一情况对上述代码进行优化。
public static void optimizedBubbleSort(int[] array){
if(array==null||array.length==0){
return;
}
//设置标记，如果后续排列均为正常正常排列，则无需继续进行冒泡
boolean nextSort=true;
for(int i=0;i<array.length-1&&nextSort;i++){
nextSort=false;
for (int j =0;j<array.length-1-i;j++){
if(array[j]>array[j+1]){
int tmp=array[j];
array[j]=array[j+1];
array[j+1]=tmp;
nextSort=true;
}
}
}
}
1.4算法分析
- 时间复杂度分析：
最优时间复杂度：O(n) 最差情况 O(n^2) 平均时间复杂度：O(n^2) - 空间复杂度分析： 平均空间复杂度：O(1)
- 稳定性： 稳定
2.选择排序
2.1选择排序的思想
选择排序的特点：选择排序是不稳定的排序算法，因为无论对什么数据进行排序都是 O(n^2)的时间复杂度，因为选择排序的时间复杂度比较大，所以当使用选择排序的时候，数据规模越小越好。
2.2算法描述
- 在待排序序列中找到最小（或最大）元素，存放排序序列在起始位置。
- 在剩余待排序序列中继续寻找最小（或最大）元素排在排序序列的末端。
- 重复第二步骤，直至序列排序完成。
2.3代码实现
public static void selectSort(int []array){
if(array==null||array.length==0){
return;
}
for(int i=0;i<array.length;i++){
int minIndex=i;
for(int j=i+1;j<array.length;j++){
if(array[j]<array[minIndex]){
minIndex=j;
}
}
//minIndex是元素最小的下标
if(minIndex!=i){
int tmp=array[i];
array[i]=array[minIndex];
array[minIndex]=tmp;
}
}
}
优化：在每一次寻找元素的过程中，直接寻找两个元素，即待排序序列中的最大元素和最小元素。
public static void optimizedSelectSort(int[]array){
if(array==null||array.length==0){
return;
}
for(int i=0;i<array.length/2;i++){
int minIndex=i;
int maxIndex=i;
for(int j=i+1;j<array.length-1-i;j++){
if(array[j]<array[minIndex]){
minIndex=j;
continue;
}
if(array[j]>array[maxIndex]){
maxIndex=j;
}
}
int tmp=array[i];
array[i]=array[minIndex];
array[minIndex]=tmp;
//判断maxIndex的值是否就是i
if(maxIndex==i){
maxIndex=minIndex;
}
tmp=array[maxIndex];
array[maxIndex]=array[array.length-1-i];
array[array.length-1-i]=tmp;
}
}
2.4算法分析
- 时间复杂度分析：
最优时间复杂度 O(n^2) 平均时间复杂度 O(n^2) 最坏时间复杂度 O(n^2) - 空间复杂度分析： 平均空间复杂度：O(1)
- 稳定性： 不稳定
3.插入排序
3.1 插入排序思想
插入排序的算法是通过构建有序序列，对于未排序的数据，在已排序的序列中从后向前进行查找操作，找到满足条件的元 素之后进行位置插入操作。
3.2算法描述
- 从第一个元素开始，该元素可以认为已经是排序好的元素；
- 取出下一个元素，在已经排序好了的元素中从后向前进行查找；
- 如果已经排序好的元素大于新元素，将该元素移动到下一个位置；
- 重复步骤3，直到找到找到已排序好的元素小于或等于新元素，进行元素的插入动作。
3.3代码实现
public static void insertSort(int []array){
if(array==null||array.length==0){
return;
}
for(int i=0;i<array.length;i++){
int tmp=array[i];//拿到的元素
int j=i;
while(j>0&&tmp<array[j-1]){
array[j]=array[j-1];
j--;
}
array[j]=tmp;
}
}
3.4算法分析
- 时间复杂度分析：
- 最优时间复杂度：O(n) 平均时间复杂度：O(n^2) 最差时间复杂度：O(n^2)
- -空间复杂度分析： 平均空间复杂度：O(1)
- 稳定性分析： 稳定
4.堆排序
4.1堆排序的思想
堆是一棵顺序存储的完全二叉树。完全二叉树中所有非终端节点的值均不大于（或不小于）其左、右孩子节点的值。其中 每个节点的值小于等于其左、右孩子的值，这样的堆称为小根堆；其中每个节点的值大于等于其左、右孩子的值，这样的堆称 为大根堆；
堆排序是指利用堆这种数据结构进行设计的一种排序算法。堆排序利用了大根堆(或小根堆)堆顶记录的关键字最大(或最小) 这一特征，使得在当前无序区中选取最大(或最小)关键字的记录变得简单。
4.2算法描述
用大根堆排序的基本思想：
- 先将初始数组建成一个大根堆，此堆为初始的无序
- 再将关键字最大的记录 R[ 1 ] (即堆顶)和无序区的最后一个记录 R[n]交换，由此得到新的无序区 R[1…n-1]和有 序区 R[n]。由于交换后新的根 R[1]可能违反堆性质，故应将当前无序区 R[1…n-1]调整为堆。然后再次将 R[1…n-1]中关键字最大的记录 R[1]和该区间的最后一个记录 R[n-1]交换，由此得到新的无序区 R[1…n-2]和有 序区 R[n-1…n]，同样要将 R[1…n-2]调整为堆。
- …… 直到无序区只有一个元素为止。
堆排序堆排序首先是根据元素构建堆。然后将堆的根节点取出(一般是与最后一个节点进行交换)，将前面 len-1 个节点 继续进行堆调整的过程，然后再将根节点取出，这样一直到所有节点都取出。
4.3代码实现
private static <T>void swap(T[] arr,int index1,int index2){
T temp = arr[index1];
arr[index1] = arr[index2];
arr[index2] = temp;
}
private static <T extends Comparable<T>>void adjust(T[] arr,int start,int end){
T temp=arr[start];
for(int i=2*start+1;i<=end;i=2*i+1){
if(i+1<=end && arr[i].compareTo(arr[i+1]) < 0){
i++;//i 保存左右孩子较大值的下标
}
if(temp.compareTo(arr[i]) < 0){
arr[start]=arr[i];
start=i;
}
else{
break;
}
}
arr[start]=temp;
}
public static <T extends Comparable<T>>void heapSort(T[] arr){
int i=0;
for(i=(arr.length-1-1)/2;i>=0;i--){//i 代表要调整根节点的下标
adjust(arr, i, arr.length-1);//最大堆建立好了
}
for(i=0;i<arr.length;i++){
//0 下标 根保存最大值
// arr[0]和堆中相对的"最后"元素进行交换
swap(arr,0,arr.length-1-i);
adjust(arr, 0, arr.length-1-i-1);
}
}
4.4算法分析
- 时间复杂度分析：
- 最优时间复杂度：O(nlog2n) 平均时间复杂度：O(nlog2n) 最坏时间复杂度：O(nlog2n)
- 空间复杂度分析： O(1)
- 稳定性分析： 不稳定
5.希尔排序
5.1希尔排序的思想
希尔排序也是一种插入排序，它是简单插入排序的一种算法改进方式。也成为见效增量排序，希尔排序的时间复杂度相比 直接插入排序的时间复杂度要小。他与直接插入排序的不同在于它会优先比较距离较远的元素。希尔排序是按照一定的增量进 行分组排序，对每一组进行直接插入排序，随着分组个数的减少，每组中的元素就会越来越多，当增量减少为 1 时，排序结束。
5.2算法描述
选择增量 gap=length/2;缩小增量继续以 gap=gap/2 的方式进行分组。{n/2,(n/2)/2,(n/2)/4,…,1}增量序列。
- 选择一个增量序列，按照增量序列个数 m，进行 m 趟排序。
- 每趟排序根据对应的增量次数分别进行元素的分组操作，对组内进行直接插入排序操作。
- 继续下一个增量，分别进行分组直接插入操作。
- 重复第三个步骤，直到增量变成 1，所有元素在一个分组内，希尔排序结束。
5.3代码实现
public static <T extends Comparable<T>>void shellSort(T[] arr,int gap){
int i=0,j=0;
for(i=gap;i<arr.length;i++){
T temp = arr[i];
for(j=i-gap;j>=0;j-=gap){
if(temp.compareTo(arr[j]) < 0){
arr[j+gap]=arr[j];
}
else{
break;
}
}
arr[j+gap]=temp;
}
}
public static <T extends Comparable<T>>void shell(T[] arr){
int[] partition={5,3,1};
for(int i=0;i<partition.length;i++){
shellSort(arr,partition[i]);
}
}
5.4算法分析
- 时间复杂度分析： 平均时间复杂度：O(n1.3~n1.5)
- 空间复杂度分析： O(1)
- 稳定性分析： 不稳定
6.归并排序
6.1归并排序的思想
归并排序建立在归并的有效操作上进行排序，主要采用分治法将已有序的子序列合并，得到完全有序的序列。即先让每一 小段有序，再让小段之间变得有序。若将两个有序合成一个有序段，这又称为二路归并。
6.2算法描述
- 开始以间隔为 1 的进行归并，也就是说，第一个元素跟第二个进行归并。第三个与第四个进行归并；
- 然后，再以间隔为 2 的进行归并，1-4 进行归并，5-8 进行归并；
- 再以 2 * 2 的间隔，同理，直到 2*k 超过数组长度为止。
- 当不够两组进行归并时，如果超过 k 个元素，仍然进行归并；如果剩余元素不超过 k 个元素，那么直接复制给中间数组。
6.3代码实现
public static <T extends Comparable<T>>void merge(T[] arr,int len,int gap){
int low1=0;//第一个归并段的起始下标
int high1=low1+gap-1;//第一个归并段的结束下标
int low2=high1+1;//第二个归并段起始下标
int high2=low2+gap-1 > len-1?len-1:low2+gap-1;
T[] brr=(T[])new Comparable[arr.length];
int i=0;
while(low2 < len){//保证有两个归并段
while(low1<=high1 && low2<=high2){//两个归并段都有数据时继续判断
if(arr[low1].compareTo(arr[low2]) <= 0){
brr[i++]=arr[low1++];
}
else{
brr[i++]=arr[low2++];
}
}
while(low1<=high1){//第一个归并段还有数据
brr[i++]=arr[low1++];
}
while(low2<=high2){
brr[i++]=arr[low2++];
}
low1=high2+1;
high1=low1+gap-1;
low2=high1+1;
high2 = low2+gap-1 > len-1?len-1:low2+gap-1;
}
//没有两个归并段：单的直接拷贝下来
while(low1<=len-1){
brr[i++]=arr[low1++];
}
for(i=0;i<arr.length;i++){
arr[i]=brr[i];
}
brr=null;
}
public static <T extends Comparable<T>>void mergeSort(T[] arr){
for(int i=1;i<arr.length;i*=2){//2 个 2 个有序，4 个 4 个有序...
merge(arr,arr.length,i);
}
}
6.4算法分析
- 时间复杂度分析： 平均时间复杂度：O(nlog2n) 最坏时间复杂度：O(nlog2n)
- 空间复杂度分析： O(n)
- 稳定性分析： 稳定
7.快速排序
7.1快速排序的思想
快排主要是通过选择一个关键值作为基准值。比基准值小的都在左边序列（一般是无序的），比基准值大的都在右边（一 般是无序的）。依此递归，达到总体待排序序列都有序。
7.2算法描述
- 选择基准：在待排序列中，按照某种方式挑出一个元素，作为 “基准”（pivot）
- 分割操作：以该基准在序列中的实际位置，把序列分成两个子序列。此时，在基准左边的元素都比该基准小，在基准右边 的元素都比基准大
- 递归地对两个序列进行快速排序，直到序列为空或者只有一个元素。
7.3代码实现
三位数取中
//随机
//中位数三位取中
public static int RandParition(int []arr,int left,int right){
Random random=new Random();
int index=random.nextInt((right-left)+1)+left;
int tmp=arr[left];
arr[left]=arr[index];
arr[index]=tmp;
return Parition(arr,left,right);
}
public static void QuickSort(int []arr){
QuickPass(arr,0,arr.length-1);
}
public static int Parition(int []arr,int left,int right){
int i=left,j=right;
int tmp=arr[i];
while (i<j){
while (i<j&&arr[j]>tmp)--j;
if(i<j)arr[i]=arr[j];
while (i<j&&arr[i]<=tmp)++i;
if(i<j)arr[j]=arr[i];
}
arr[i]=tmp;
return i;
}
非递归
public static void QuickPass(int []arr,int left,int right) {
Queue<Integer> queue = new LinkedList<>();
if (left >= right) return;
queue.offer(left);
queue.offer(right);
while (!queue.isEmpty()) {
left = queue.poll();
right = queue.poll();
int pos = OWParition2(arr, left, right);
if (left < pos - 1) {
queue.offer(left);
queue.offer((pos - 1));
}
if (pos + 1 < right) {
queue.offer(pos + 1);
queue.offer(right);
}
}
}
public static int OWParition2(int []arr,int left,int right){
int i=left,j=left+1;
int tmp=arr[i];
while (j<=right){
if(arr[j]<=tmp){
i+=1;
Swap(arr,i,j);
}
j++;
}
Swap(arr,left,i);
return i;
}
public static void Swap(int[]arr,int i,int j){
int tmp=arr[i];
arr[i]=arr[j];
arr[j]=tmp;
}
递归
public static void QuickSort(int []arr){
QuickPass(arr,0,arr.length-1);
}
// 利用递归
public static void QuickPass(int []arr,int left,int right){
if(left<right){
int pos=Parition(arr,left,right);
QuickPass(arr,left,pos-1);
QuickPass(arr,pos+1,right);
}
}
public static int Parition(int []arr,int left,int right){
int i=left,j=right;
int tmp=arr[i];
while (i<j){
while (i<j&&arr[j]>tmp)--j;
if(i<j)arr[i]=arr[j];
while (i<j&&arr[i]<=tmp)++i;
if(i<j)arr[j]=arr[i];
}
arr[i]=tmp;
return i;
}
7.4算法分析
- 时间复杂度分析：
最优时间复杂度：O(nlog2n) 平均时间复杂度：O(nlog2n) 最坏时间复杂度：O(nlog2n) - 空间复杂度分析： Olog2n)
- 稳定性分析： 不稳定
这篇关于Java排序算法的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
- 2024-12-22项目：远程温湿度检测系统
- 2024-12-21《鸿蒙HarmonyOS应用开发从入门到精通（第2版）》简介
- 2024-12-21后台管理系统开发教程：新手入门全指南
- 2024-12-21后台开发教程：新手入门及实战指南
- 2024-12-21后台综合解决方案教程：新手入门指南
- 2024-12-21接口模块封装教程：新手必备指南
- 2024-12-21请求动作封装教程：新手必看指南
- 2024-12-21RBAC的权限教程：从入门到实践
- 2024-12-21登录鉴权实战：新手入门教程
- 2024-12-21动态权限实战入门指南
