栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

合并排序与快速排序

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

合并排序与快速排序

合并排序与快速排序

文章目录
  • 合并排序与快速排序
  • 一、合并排序
    • 1.基本思想
    • 2.代码
    • 3.时间复杂度
  • 二、快速排序
    • 1.基本思想
    • 2.步骤
    • 3.时间复杂度
  • 总结


一、合并排序

合并排序算法又叫归并排序,是用分治策略实现对n个元素进行排序的算法

1.基本思想

将待排序元素分成大小大致相同的两个子集合,分别对两个子集合进行排序,最终将排好序的子集合合并成所要求的排好序的集合。
合并方法是循环的将两个有序子序列当前的首元素进行比较,较小的元素取出,置入合并序列的左边空置位,直至其中一个子序列的最后一个元素置入合并序列中。最后将另一个子序列的剩余元素按顺序逐个置入合并序列尾部即可完成排序。(二分法)
由于排序问题的计算下界为Ω(nlog n),所以合并排序是一个渐进最优算法

2.代码

代码

#include
#include
#define maxx 105
int a[maxx];
int merge[maxx];
//合并两个有序子序列
void Merge(int merge[],int a[],int left,int right,int middle){
	int i=left,j=middle+1;
	int k=left;
	while(i<=middle&&j<=right){
		if(a[i]<=a[j]){
			merge[k++]=a[i++];
		}else{
			merge[k++]=a[j++];
		}
	}
	while(i<=middle)merge[k++]=a[i++];
	while(j<=right)merge[k++]=a[j++];
	i=0;
	for(i=left;i<=right;i++)a[i]=merge[i];
}
//合并排序算法
void Mergesort(int a[],int left,int right){
	if(left
		int middle=(left+right)>>1;
		Mergesort(a,left,middle);
		Mergesort(a,middle+1,right);
		Merge(merge,a,left,right,middle);
    }
}
int main(){
	int n;
	while(scanf("%d",&n)!=EOF){
		int i;
		for(i=0;i
			scanf("%d",&a[i]);
		}
		Mergesort(a,0,n-1);
		i=0;
		for(i=0;i
			printf("%d ",a[i]);
		}
	}
	return 0;
}


3.时间复杂度

1)最好时间复杂度:O(log n)
2)最坏时间复杂度:O(n*log n)
最坏情况T(n)=O(1) ,n<=1
T(n)=2T(n/2)+O(n),n>1
3)空间复杂度O(n)

二、快速排序

基于分治策略的另一种排序,是性能最好的排序方式

1.基本思想

选择一个基准数,通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小。然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以达到全部数据变成有序。

2.步骤

(1) 从数列中挑出一个基准值。
(2) 将所有比基准值小的摆放在基准前面,所有比基准值大的摆在基准的后面(相同的数可以到任一边),在这个分区退出之后,该基准就处于数列的中间位置。
(3) 递归地把基准值前面的子数列和基准值后面的子数列进行排序。

代码如下(示例):

public class QuickSort {
 
    public static void main(String[] args) {
        int[] arr = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
        quickSort(arr, 0, arr.length - 1);
        System.out.println("排序结果:" + Arrays.toString(arr));
    }
    
    
    public static void quickSort(int[] arr, int left, int right) {
        if (left < right) {
            // 获取枢纽值,并将其放在当前待处理序列末尾
            dealPivot(arr, left, right);
            // 枢纽值被放在序列末尾
            int pivot = right - 1;
            int i = left; // 左指针
            int j = right - 1; // 右指针
            while (true) {
                while (arr[++i] < arr[pivot]) {
                }
                while (j > left && arr[--j] > arr[pivot]) {
                }
                if (i < j) {
                    swap(arr, i, j);
                } else {
                    break;
                }
            }
            if (i < right) {
                swap(arr, i, right - 1);
            }
            quickSort(arr, left, i - 1);
            quickSort(arr, i + 1, right);
        }
    }
 
    
    public static void dealPivot(int[] arr, int left, int right) {
        int mid = (left + right) / 2;
        if (arr[left] > arr[mid]) {
            swap(arr, left, mid);
        }
        if (arr[left] > arr[right]) {
            swap(arr, left, right);
        }
        if (arr[right] < arr[mid]) {
            swap(arr, right, mid);
        }
        swap(arr, right - 1, mid);
    }
 
    
    private static void swap(int[] arr, int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
}
3.时间复杂度

以减少排序过程中的比较次数,
1)它的最好情况为O(nlogn),
每一次划分都正好将数组分成长度相等的两半
T(n)=2T(n/2)+O(n)
=2(2T(n/4)+O(n/2))+O(n)=4T(n/4)+2O(n/2)+O(n)
=8T(n/8)+4O(n/4)+2O(n/2)+O(n)
….
=nT(n/n)+….+2O(n/2)+O(n)
=nT(1)+….+2O(n/2)+O(n)
=nT(1)+lognO(n)
=O(n+nlogn)=O(nlogn)
其空间复杂度也就为O(logn)

2)最坏情况为O(n2),
即每一次划分都将数组分成了0和n-1两部分
T(n)=T(n-1)+O(n)
=T(n-2)+O(n-1)+O(n)
=T(n-3)+O(n-2)+O(n-1)+O(n)
…
=O(n)+O(n-1)+…+O(n-2)+O(n-1)+O(n)
=O(n(n-1)/2)=O(n2)
n‐1次递归调用
其空间复杂度为O(n),
3)平均时间复杂度为O(nlogn)。
在平均情况下,即轴枢在第K位置,

平均情况,空间复杂度也为O(logn)

总结

快速排序不稳定,性能好坏取决于划分的对称性

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/966925.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号