精华内容
下载资源
问答
  • PAT 1029 Median(中位数+归并排序
    2017-06-16 22:41:00

    题目

    https://www.patest.cn/contests/pat-a-practise/1029

    题意:求两个排好序的数组合并后的中位数。

    解题思路

    担心直接sort会超时,所以拿归并排序的merge方法合并数组,即从每次都从两个数组剩余的元素中挑出最小的,若某个数组先挑完,则另一个数组原样抄回。

    然而,sort也能过……(摊手)

    顺便复习一下归并排序:

    归并排序利用了分治的思想,将数列a[l,h]分成两半a[l,mid]和a[mid+1,h],分别进行归并排序,然后再将这两半合(merge)并起来。

    利用归并排序可以求逆序对的数目。即在合并的过程中(设l<=i<=mid,mid+1<=j<=h),当a[i]<=a[j]时,并不产生逆序数;当a[i]>a[j]时,在前半部分中比a[i]大的数都比a[j]大,将a[j]放在a[i]前面时,逆序数要加上mid+1-i。因此,可以在归并排序中的合并过程中计算逆序数。

    AC代码

    #include <iostream>
    using namespace std;
    
    const int maxn = 1000005;
    long int a[maxn], b[maxn], res[maxn<<1];
    int lena, lenb, cnt;
    
    int main()
    {
        ios::sync_with_stdio(false);
        cin >> lena;
        for (int i = 0; i < lena; ++i)
            cin >> a[i];
        cin >> lenb;
        for (int i = 0; i < lenb; ++i)
            cin >> b[i];
        //归并排序的merge步骤
        int p1 = 0, p2 = 0, cnt = 0;
        while (p1 < lena && p2 < lenb)
        {
            if (a[p1] < b[p2]) 
            {
                res[cnt++] = a[p1];
                p1++;
            }
            else
            {
                res[cnt++] = b[p2];
                p2++;
            }
        }
        if (p1 < lena) //p1还有剩余
        {
            for (int i = p1; i < lena; ++i)
                res[cnt++] = a[i];
        }
        if (p2 < lenb) //p2还有剩余
        {
            for (int i = p2; i < lenb; ++i)
                res[cnt++] = b[i];
        }
        cout << res[(cnt-1)>>1] << endl; //输出中位数
        return 0;
    }
    
    更多相关内容
  • 例如,若序列S1=(11, 13, 15, 17, 19),则S1的中位数是15,两个序列的中位数是含它们所有元素的升序序列的中位数。例如,若S2= (2, 4,6,8, 20),则S1和S2的中位数是11。现在有两个等长升序序列A和B,试设计一个在...

    题目:一个长度为L (L>=1)的升序序列S,处在第[L/2]个位置的数称为S的中位数。例如,若序列S1=(11, 13, 15, 17, 19),则S1的中位数是15,两个序列的中位数是含它们所有元素的升序序列的中位数。例如,若S2= (2, 4,6,8, 20),则S1和S2的中位数是11。现在有两个等长升序序列A和B,试设计一个在时间和空间两方面都尽可能高效的算法,找出两个序列A和B的中位数。要求:

    1. 给出算法的基本设计思想。
    2. 根据设计思想,釆用C或C++或Java语言描述算法,关键之处给出注释。
    3. 说明你所设计算法的时间复杂度和空间复杂度。

    该题为2011年研究生考试计算机联考真题。

    第一种方法

    算法思想:1.先将两个升序序列归并排序成一个升序序列,找中位数(最先想到且简单)
    时间复杂度:O(n),空间复杂度:O(n)

    #include"head.h"
    bool findmid1(SeqList A, SeqList B, SeqList& C) {
    	if (A.length + B.length > C.Maxsize) {
    		//return false;//若两表长度之和大于新表最大长度,则返回。
    		//为了更有效的执行算法,此处我们不这样写,如果两表长度之和大于新表最大长度,则新表动态增加空间
    		IncreaseSize(C, 10);//C表自动增加10个长度
    	}
    	int i = 0, j = 0, k = 0;
    	while (i < A.length && j < B.length)
    	{
    		if (A.data[i] < B.data[j])
    		{
    			C.data[k++] = A.data[i++];
    		}
    		else
    		{
    			C.data[k++] = B.data[j++];
    		}
    	}
    	while (i < A.length)
    	{
    		C.data[k++] = A.data[i++];
    	}
    	while (j < B.length)
    	{
    		C.data[k++] = B.data[j++];
    	}
    	C.length = k;
    	int mid = C.length / 2;
    	printf("C表中位数为:%d\n", C.data[mid-1]);//中位数,数组长度一般下标-1
    	return true;
    }
    

    第二种方法

    算法思想:类比归并排序的思想但并不实现归并,仅按顺序进行访问
    时间复杂度:O(n),空间复杂度:O(1)

    int findmid2 ( int* a, int* b, int len ) {
    	int i = 0, j = 0, k = 0;
    
    	for ( ; k < len-1; k++ ) {
    		if ( a[i] < b[j] ) {
    			i++;
    		}
    		else {
    			j++;
    		}
    	}
    
    	return (a[i] < b[j])? a[i]: b[j];
    }
    //就是从头到尾一共数 len 个数,这个时候两个指针指向的数字较小者即为所求。
    

    第三种方法

    **王道考研参考书中给出的该题的最优方法

    时间复杂度:O(log2n),空间复杂度:O(1)

    分别求两个升序序列A、B的中位数,设为a和b, 求序列A、B的中位数过程如下:

    1. 若a = b,则a或b即为所求中位数,算法结束。

    2. 若a < b,则舍弃序列A中较小的一半,同时舍弃序列B中较大的一半,要求两次舍弃的长度相等。

    3. 若a > b,则舍弃序列A中较大的一半,同时舍弃序列B中较小的一半,要求两次舍弃的长度相等。**

    int findmid3(int A[], int B[], int n)
    {
    	int start1 = 0, end1 = n - 1, m1, start2 = 0, end2 = n - 1, m2;
    	//分别表示序列A和B的首位数、末位数和中位数
    
    	while (start1 != end1 || start2 != end2)
    	{
    		m1 = (start1 + end1) / 2;
    		m2 = (start2 + end2) / 2;
    		if (A[m1] == B[m2])
    			return A[m1];   //满足条件 1)
    
    		if (A[m1] < B[m2]) // 满足条件 2)
    		{
    			if ((start1 + end1) % 2 == 0)  //若元素个数为奇数
    			{
    				start1 = m1;  //舍弃A中间点以前的部分且保留中间点
    				end2 = m2;  //舍弃B中间点以后的部分且保留中间点
    			}
    			else				//元素个数为偶数
    			{
    				start1 = m1 + 1;  //舍弃A中间点及中间点以前部分
    				end2 = m2;  //舍弃B中间点以后部分且保留中间点
    			}
    		}
    		else
    		{  //满足条件3)
    			if ((start2 + end2) % 2 == 0)   //若元素个数为奇数
    			{
    				end1 = m1;    //舍弃A中间点以后的部分且保留中间点
    				start2 = m2;    //舍弃B中间点以前的部分且保留中间点
    			}
    			else     //元素个数为偶数
    			{
    				end1 = m1;    //舍弃A中间点以后部分且保留中间点
    				start2 = m2 + 1;    //舍弃B中间点及中间点以前部分
    			}
    		}
    	}
    	return  A[start1] < B[start2] ? A[start1] : B[start2];
    }
    

    总结

    1. 当在练习的时候可以对三种方法慢慢调试,仔细理解。

    2. 若无法理解第三种最优解的方法建议就不要再看了,考试时第三种方法为满分答案,第二种方法减1分,第一种方法减2分。

    3. 小编在写第一种和第二种方法时一共用了10分钟,第三种方法依然没有理解并成功运行,给诸位大佬程序员丢人了…

    展开全文
  • 数字逻辑与处理器大作业,通过汇编语言实现从文档读入并且归并排序,写入文档的操作
  • 多种排序算法求中位数

    千次阅读 2017-06-12 22:39:15
    File name:求中位数.cpp Author:杨柳 Date:2017/5/25 IDE:DEV-c++ 思想:把无序数组排好序,取出中间的元素 */ #include #include using namespace std; #define MAX 100 int array[MAX],arr[MAX]; int result=0;/...

    给一列无序数组,求出中位数并给出算法的时间复杂度。

    /*
    File name:求中位数.cpp
    Author:杨柳
    Date:2017/5/25
    IDE:DEV-c++ 
    思想:把无序数组排好序,取出中间的元素
    */
    
    #include<stdio.h>
    #include<iostream>
    using namespace std;
    #define MAX 100
    int array[MAX],arr[MAX];
    int result=0;//保存中位数 
    
    //简单选择排序 
    int selectsort(int array[],int n){
    	int temp,j,k;	//设置临时变量 
    	for(int i=0;i<n;i++){  //n-1趟 
    		j=i;	//记录最小元素的位置 
    		for(k=i+1;k<n;k++){
    			if(array[j]>array[k])
    				j=k;
    				temp=array[i];
    				array[i]=array[j];
    				array[j]=temp;
    		}
    	}
    	if(n%2==0){		//	若数组有奇数个元素,中位数是array[(n-1)/2]
    		result=((array[n/2-1]+array[n/2])/2);
    		return result;
    	}
    	else{			//若数组有偶数个元素,中位数为array[n/2-1]和array[n/2]两个数的平均值
    		result=array[(n-1)/2];
    		return result;
    	}
    }
    
    //直接插入排序
    int insertsort(int array[],int n){
    	for(int i=1;i<n;i++){
    			int temp;//设置临时变量存放待插入的记录
    		 	temp=array[i];		
    		 	for(int k=i-1;k>=0&&temp<array[k];k--){	//待插入一次与前面数据一次 
    		 		array[k+1]=array[k]; 
    				 array[k+1]=temp;
    			 } 
    		 	
    	}
    	if(n%2==0){		//	若数组有奇数个元素,中位数是array[(n-1)/2]
    		result=((array[n/2-1]+array[n/2])/2);
    		return result;
    	}
    	else{			//若数组有偶数个元素,中位数为array[n/2-1]和array[n/2]两个数的平均值
    		result=array[(n-1)/2];
    		return result;
    	}
    } 
    //希尔排序求中位数
    int  shellsort(int array[],int arr[],int n,int m) {
    	int h,k,j,v;
    	for(int i=0;i<m;i++){
    		h=arr[i];//选取增量
    		for(k=h;k<n;k++){
    			j=array[k];
    			for(v=k-h;v>=0&&j<array[v];v=v-h){
    				array[v+h]=array[v];
    				array[v+h]=j;
    			}
    		} 
    	}
    
    
    	if(n%2==0){		//	若数组有奇数个元素,中位数是array[(n-1)/2]
    		result=((array[n/2-1]+array[n/2])/2);
    		return result;
    	}
    	else{			//若数组有偶数个元素,中位数为array[n/2-1]和array[n/2]两个数的平均值
    		result=array[(n-1)/2];
    		return result;
    	}
    }
    
    //冒泡排序求中位数
    int bubblesort(int array[],int n){
    	int temp,change=true;  //设置标志以便进入循环 
    	for(int i=1;i<n&&change;i++){   //n-1趟 
    		change=false;//第i趟设置交换标志false,这时没有交换记录,已经有序,结束 
    		for(int j=0;j<n-i;j++){
    			if(array[j]>array[j+1]){  //若逆序交换 
    				temp=array[j];
    				array[j]=array[j+1];
    				array[j+1]=temp;
    				change=true;
    			}
    		}
    		
    	}
    	
    	if(n%2==0){		//	若数组有奇数个元素,中位数是array[(n-1)/2]
    		result=((array[n/2-1]+array[n/2])/2);
    		return result;
    	}
    	else{			//若数组有偶数个元素,中位数为array[n/2-1]和array[n/2]两个数的平均值
    		result=array[(n-1)/2];
    		return result;
    	}
    } 
    
    //快速排序求中位数
    int  quicksort(int array[],int min,int max){
    	int high,low;
    	if(min<max){
    		low=min;
    		high=max;
    		int temp=array[low];  
    		while(low!=high){
    			while(low<high&&array[high]>temp){ //从右向左 
    				high--;
    			}
    			if(low<high)
    				array[low++]=array[high];  //比 array[low]小,交换 
    			while(low<high&&array[low]<=temp){ //从左向右 
    				low++;
    			}
    			if(low<high){
    				array[high--]=array[low];  //交换 
    			}
    			}
    	array[low]=temp;		
    	quicksort(array,min,low-1);
    	quicksort(array,high+1,max);
    		}
    	if((max+1)%2==0){		//	若数组有奇数个元素,中位数是array[(n-1)/2]
    		result=((array[(max+1)/2-1]+array[(max+1)/2])/2);
    		return result;
    	}
    	else{			//若数组有偶数个元素,中位数为array[n/2-1]和array[n/2]两个数的平均值
    		result=array[(max)/2];
    		return result;
    	}	
    		
    }
    
    //调整为堆
    void shift(int array[],int s,int n){
    	int q,t;
    	t=array[s];
    	while((q=2*s+1)<n){ //有左孩子 
    		if(q<n-1&&array[q]<array[q+1])
    			q++;
    		if(t<array[q]){
    			array[(q-1)/2]=array[q];
    			s=q;
    		} 
    		else
    			break;
    	}
    	array[(q-1)/2]=t;  //t放在最后一个位置 
    } 
    
    //堆排序求中位数
    int heapsort(int array[],int n){
    	int s,t;
    	s=(n-1)/2;
    	while(s>=0){
    		shift(array,s,n);
    		s--;
    	}
    	s=n-1;
    	while(s>0){  //交换结点 
    		t=array[0];
    		array[0]=array[s];
    		array[s]=t;
    		shift(array,0,s);
    		s--;
    	}
    	if(n%2==0){		//	若数组有奇数个元素,中位数是array[(n-1)/2]
    		result=((array[n/2-1]+array[n/2])/2);
    		return result;
    	}
    	else{			//若数组有偶数个元素,中位数为array[n/2-1]和array[n/2]两个数的平均值
    		result=array[(n-1)/2];
    		return result;
    	}
    } 
    
    //合并两个有序序列 
    void merge(int array[],int p,int q,int r){
    	int n1,n2;
    	n1=q-p+1;
    	n2=r-q+1; 
    	int arr1[n1+1],arr2[n2];
        for(int i=0;i!=n1;++i){
        	arr1[i]=array[i+p];
        
    	}
    		arr1[n1]=2000000;
    	for(int j=0;j!=n2-1;++j){
    		arr2[j]=array[q+j+1];
    	}
    		arr2[n2-1]=200000;
    		int i=0,j=0;
    	for( int k=p;k!=r+1;++k){
    		if(arr1[i]>arr2[j]){
    			array[k]=arr2[j];
    		    ++j;
    		}
    		else{
    			array[k]=arr1[i];
    			++i;
    		}
    	}
    }
    //归并排序求中位数
    void mergesort(int array[],int p,int r){
    	if(p<r){
    		int q=(p+r)/2;
    		mergesort(array,p,q);
    		mergesort(array,q+1,r);
    		merge(array,p,q,r);
    	}
    			
    } 
     
    int midiumnumber(int array[],int n){
    		cout<<endl<<endl<<"1----------简单选择排序求中位数(O(n^2))"<<endl;
    		cout<<"2----------直接插入排序求中位数(O(n^2))---------"<<endl;
    		cout<<"3----------希尔排序求中位数(O(nlog2^n))---------"<<endl;
    		cout<<"4----------冒泡排序求中位数(O(n^2))-------------"<<endl;
    		cout<<"5----------快速排序求中位数(O(nlog2^n))---------"<<endl;
    		cout<<"6----------堆排序求中位数(O(nlog2^n))-----------"<<endl;
    		cout<<"7----------归并求中位数(O(nlog2^n))-----------"<<endl;
    		cout<<"请选择1-7:"<<endl; 
    		int select;
    		cin>>select;
    		switch(select){
    			case 7:
    				cout<<"这列无序数组的中位数为:"<<endl;
    			    mergesort(array,0,n-1);
    			    	if(n%2==0){		//	若数组有奇数个元素,中位数是array[(n-1)/2]
    						result=((array[n/2-1]+array[n/2])/2);
    						return result;
    					}
    					else{			//若数组有偶数个元素,中位数为array[n/2-1]和array[n/2]两个数的平均值
    						result=array[(n-1)/2];
    						return result;
    					}
    				break;
    			case 6:
    				cout<<"这列无序数组的中位数为:"<<endl;
    				return heapsort(array,n);
    				break;	
    			case 5:
    				cout<<"这列无序数组的中位数为:"<<endl;
    				return quicksort(array,0,n-1);
    				break;	
    			case 4:
    				cout<<"这列无序数组的中位数为:"<<endl;
    				return bubblesort(array,n);
    				break;
    			case 1:
    				cout<<"这列无序数组的中位数为:"<<endl;
    				return selectsort(array,n);
    				break;	
    			case 2:
    				cout<<"这列无序数组的中位数为:"<<endl;
    				return insertsort(array,n);
    				break;
    			case 3:
    				//初始化一个增量数组 
    				int n1=n;
    				int m=0;
    				while(n1>1){
    					arr[m++]=n1/2;
    					n1=n1/2;
    				}
    				cout<<"这列无序数组的中位数为:"<<endl;
    				return 	shellsort(array,arr,n,m);
    				break;			
    
    			}
    }
    
    int main(){
    
    	int n,i;
    	cout<<"输入一列无序数组数的个数:"<<endl;
    	cin>>n;
    	cout<<"请输入一列无序数组:"<<endl;
    	for(i=0;i<n;i++){
    		cin>>array[i];
    	}
    
       int flag=1;
       while(flag==1){
    	cout<<midiumnumber(array,n)<<endl;
    }
    //	cout<<selectsort(array,n);
       
    	return 0;
    } 

     

    展开全文
  • 归并排序与堆排序

    2022-01-22 09:51:18
    文章目录归并排序思想代码测试分析堆排序(Heap Sort)堆的定义思想实现测试分析 归并排序 思想 排序一个数组,我们先把... 1 是运算的右移运算,表示右移一,等同于 x 除以 2 再取整,即 x >> 1 === Mat.


    归并排序

    思想

    排序一个数组,我们先把数组从中间分成前后两部分,然后对前后两部分分别排序,再将排好序的两部分合并在一起,这样整个数组就都有序了。
    归并排序采用的是分治思想。
    分治,顾名思义,就是分而治之,将一个大问题分解成小的子问题来解决。小的子问题解决了,大问题也就解决了。
    请添加图片描述

    注:x >> 1 是位运算中的右移运算,表示右移一位,等同于 x 除以 2 再取整,即 x >> 1 === Math.floor(x / 2) 。

    代码

    const mergeSort = arr => {
    	//采用自上而下的递归方法
    	const len = arr.length;
    	if (len < 2) {
    		return arr;
    	}
    	// length >> 1 和 Math.floor(len / 2) 等价
    	let middle = Math.floor(len / 2),
    		left = arr.slice(0, middle),
    		right = arr.slice(middle); // 拆分为两个子数组
    	return merge(mergeSort(left), mergeSort(right));
    };
    
    const merge = (left, right) => {
    	const result = [];
    
    	while (left.length && right.length) {
    		// 注意: 判断的条件是小于或等于,如果只是小于,那么排序将不稳定.
    		if (left[0] <= right[0]) {
    			result.push(left.shift());
    		} else {
    			result.push(right.shift());
    		}
    	}
    
    	while (left.length) result.push(left.shift());
    
    	while (right.length) result.push(right.shift());
    
    	return result;
    };
    
    

    测试

    // 测试
    const arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
    console.time('归并排序耗时');
    console.log('arr :', mergeSort(arr));
    console.timeEnd('归并排序耗时');
    // arr : [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
    // 归并排序耗时: 0.739990234375ms
    
    

    分析

    第一,归并排序是原地排序算法吗 ?
    这是因为归并排序的合并函数,在合并两个有序数组为一个有序数组时,需要借助额外的存储空间。
    实际上,尽管每次合并操作都需要申请额外的内存空间,但在合并完成之后,临时开辟的内存空间就被释放掉了。在任意时刻,CPU 只会有一个函数在执行,也就只会有一个临时的内存空间在使用。临时内存空间最大也不会超过 n 个数据的大小,所以空间复杂度是 O(n)。
    所以,归并排序不是原地排序算法。

    第二,归并排序是稳定的排序算法吗 ?
    merge 方法里面的 left[0] <= right[0] ,保证了值相同的元素,在合并前后的先后顺序不变。归并排序是一种稳定的排序方法。

    第三,归并排序的时间复杂度是多少 ?
    从效率上看,归并排序可算是排序算法中的佼佼者。假设数组长度为 n,那么拆分数组共需 logn 步, 又每步都是一个普通的合并子数组的过程,时间复杂度为 O(n),故其综合时间复杂度为 O(nlogn)。
    最佳情况:T(n) = O(nlogn)。
    最差情况:T(n) = O(nlogn)。
    平均情况:T(n) = O(nlogn)。

    堆排序(Heap Sort)

    堆的定义

    堆其实是一种特殊的树。只要满足这两点,它就是一个堆。

    堆是一个完全二叉树。
    完全二叉树:除了最后一层,其他层的节点个数都是满的,最后一层的节点都靠左排列。
    堆中每一个节点的值都必须大于等于(或小于等于)其子树中每个节点的值。
    也可以说:堆中每个节点的值都大于等于(或者小于等于)其左右子节点的值。这两种表述是等价的。

    对于每个节点的值都大于等于子树中每个节点值的堆,我们叫作大顶堆。
    对于每个节点的值都小于等于子树中每个节点值的堆,我们叫作小顶堆。

    在这里插入图片描述
    其中图 1 和 图 2 是大顶堆,图 3 是小顶堆,图 4 不是堆。除此之外,从图中还可以看出来,对于同一组数据,我们可以构建多种不同形态的堆。

    思想

    1.将初始待排序关键字序列 (R1, R2 … Rn) 构建成大顶堆,此堆为初始的无序区;

    2.将堆顶元素 R[1] 与最后一个元素 R[n] 交换,此时得到新的无序区 (R1, R2, … Rn-1) 和新的有序区 (Rn) ,且满足 R[1, 2 … n-1] <= R[n]。

    3.由于交换后新的堆顶 R[1] 可能违反堆的性质,因此需要对当前无序区 (R1, R2 … Rn-1) 调整为新堆,然后再次将 R[1] 与无序区最后一个元素交换,得到新的无序区 (R1, R2 … Rn-2) 和新的有序区 (Rn-1, Rn)。不断重复此过程,直到有序区的元素个数为 n - 1,则整个排序过程完成。

    实现

    // 堆排序
    const heapSort = array => {
    	console.time('堆排序耗时');
    	// 初始化大顶堆,从第一个非叶子结点开始
    	for (let i = Math.floor(array.length / 2 - 1); i >= 0; i--) {
    		heapify(array, i, array.length);
    	}
    	// 排序,每一次 for 循环找出一个当前最大值,数组长度减一
    	for (let i = Math.floor(array.length - 1); i > 0; i--) {
    		// 根节点与最后一个节点交换
    		swap(array, 0, i);
    		// 从根节点开始调整,并且最后一个结点已经为当前最大值,不需要再参与比较,所以第三个参数为 i,即比较到最后一个结点前一个即可
    		heapify(array, 0, i);
    	}
    	console.timeEnd('堆排序耗时');
    	return array;
    };
    
    // 交换两个节点
    const swap = (array, i, j) => {
    	let temp = array[i];
    	array[i] = array[j];
    	array[j] = temp;
    };
    
    // 将 i 结点以下的堆整理为大顶堆,注意这一步实现的基础实际上是:
    // 假设结点 i 以下的子堆已经是一个大顶堆,heapify 函数实现的
    // 功能是实际上是:找到 结点 i 在包括结点 i 的堆中的正确位置。
    // 后面将写一个 for 循环,从第一个非叶子结点开始,对每一个非叶子结点
    // 都执行 heapify 操作,所以就满足了结点 i 以下的子堆已经是一大顶堆
    const heapify = (array, i, length) => {
    	let temp = array[i]; // 当前父节点
    	// j < length 的目的是对结点 i 以下的结点全部做顺序调整
    	for (let j = 2 * i + 1; j < length; j = 2 * j + 1) {
    		temp = array[i]; // 将 array[i] 取出,整个过程相当于找到 array[i] 应处于的位置
    		if (j + 1 < length && array[j] < array[j + 1]) {
    			j++; // 找到两个孩子中较大的一个,再与父节点比较
    		}
    		if (temp < array[j]) {
    			swap(array, i, j); // 如果父节点小于子节点:交换;否则跳出
    			i = j; // 交换后,temp 的下标变为 j
    		} else {
    			break;
    		}
    	}
    };
    
    

    测试

    const array = [4, 6, 8, 5, 9, 1, 2, 5, 3, 2];
    console.log('原始array:', array);
    const newArr = heapSort(array);
    console.log('newArr:', newArr);
    // 原始 array:  [4, 6, 8, 5, 9, 1, 2, 5, 3, 2]
    // 堆排序耗时: 0.15087890625ms
    // newArr:     [1, 2, 2, 3, 4, 5, 5, 6, 8, 9]
    
    

    分析

    第一,堆排序是原地排序算法吗 ?
    整个堆排序的过程,都只需要极个别临时存储空间,所以堆排序是原地排序算法。

    第二,堆排序是稳定的排序算法吗 ?
    因为在排序的过程,存在将堆的最后一个节点跟堆顶节点互换的操作,所以就有可能改变值相同数据的原始相对顺序。
    所以,堆排序是不稳定的排序算法。

    第三,堆排序的时间复杂度是多少 ?
    堆排序包括建堆和排序两个操作,建堆过程的时间复杂度是 O(n),排序过程的时间复杂度是 O(nlogn),所以,堆排序整体的时间复杂度是 O(nlogn)。
    最佳情况:T(n) = O(nlogn)。
    最差情况:T(n) = O(nlogn)。
    平均情况:T(n) = O(nlogn)。

    展开全文
  • 归并排序

    万次阅读 多人点赞 2020-12-02 11:18:34
    一、归并排序的介绍 基本介绍 归并排序(MERGE- SORT)是利用归并的思想实现的排序方法,该算法采用经典的分治( divide- and-conquer)策略(分治法将问题分(divide)成一些小的问题然后递归求解,而治(conquer)的阶段则...
  • 文章目录一、归并排序介绍 一、归并排序介绍
  • 归并排序简介代码示例排序过程时间复杂度空间复杂度稳定性 简介 归并排序分为两部分:分解,合并。 分解:归并算法会把数组分成两个长度相同的子数组,直到无法再分割,每个数组只有一个元素。此过程不消耗时间资源。...
  • C语言实现归并排序

    2022-04-07 12:46:43
    归并排序每次递归的动作: 将给定数组以中点为界,分为左右两部分,且左右两边的数字分别有序。(至于如何将它做到分别有序,则需使用递归实现) 使用两个指针 L(初始值为左边界) 和 R(初始值为中点右侧的第一个...
  • 请你找出这两个有序数组的中位数,并且要求算法的时间复杂度为 O(log(m + n))。你可以假设 nums1 和 nums2 不会同时为空。 示例 1 :nums1 = [1, 3] nums2 = [2] 则中位数是 2.0 示例 2: nums1 = [1, 2] nums2 = ...
  • 归并排序、基数排序
  • 八大排序算法 一、直接插入 - 1.基本思路 - 2.代码实现 - 3.时间复杂度和空间复杂度 二、希尔排序 - 1.基本思路 - 2.代码实现 - 3.时间复杂度和空间复杂度 三、简单选择 - 1.基本思路 - 2.代码实现 - 3.时间复杂度...
  • 选择排序的基本思想是:每次从待排序的文件选择出排序码最小的记录将该记录放于已排序文件的最后一个位置,直到已排序文件记录个等于初始待排序文件的记录个为止。 直接选择排序(不稳定排序) 树型选择排序 ...
  • 排序算法1:归并排序归并排序1:归并排序基本思想2:归并排序的应用:小和问题和逆序对问题2.1 小和问题和逆序对问题2.2 C++的代码示例2.3 python代码示例 归并排序 1:归并排序基本思想 1:归并排序的过程:递归+...
  • 无序数组中位数,数组排序时间复杂度O(N)算法 排序知识回顾
  • 排序算法——归并排序与快速排序

    万次阅读 多人点赞 2018-07-27 20:50:08
    今天总结一下两种性能优秀的排序算法,归并排序与快速排序。 首先,二者都运用了递归和分治的两种重要思想。在这里递归就不做详细介绍。 分治:顾名思义,分而治之,这是在排序中我们非常常见的一种思想,同时也是...
  • 二分归并排序算法

    千次阅读 2021-03-29 15:29:39
    二分归并排序算法原理(假设数组A中共有n个元素): 将数组An个元素看成n个独立的子序列,因此每个子序列的长度为1,然后两两合并,得到[n/2]个长度为2或1(注意如果n为奇数时,就会出现多出一个元素无法与其他元素...
  • 归并排序(C++实现)言简意赅版

    千次阅读 2022-03-25 01:05:12
    将n个子数列两两排序,得到n/2个有序的分别有两个元素的数列 将n/2个子数列再两两排序,得到n/4个有序的子数列。 重复上述步骤,最终得到一个有序数列 算法实现(递归实现) #include<iostream> #include<...
  • 归并排序 归并排序是分而治之的排序算法。 划分步骤很简单:将当前数组分成两半(如果N是偶数,则将其完全平等,或者如果N是奇数,则一边稍大于一个元素),然后递归地对这两半进行排序。 递归写法 归并排序递归写法...
  • 归并排序思路整理

    2020-06-14 23:29:02
    首先介绍一下归并排序: 归并排序是采用归并的思路进行排序,该算法采用经典的分治策略(把一个大问题分解为若干个小的问题进而求解的过程)。字面上看起来还是很抽象的,接下来给出归并排序的整个示意图: 解释:...
  • C语言 归并排序

    2015-04-22 23:27:56
    c语言 归并排序算法,相邻两个有序子序列的归并。
  • //三 int GetMidIndex(int* a, int begin, int end) { int mid = (begin + end) / 2; if (a[begin] < a[mid]) { if (a[mid] < a[end]) return mid; else if (a[begin] > a[end])
  • 外排序(归并排序算法)

    千次阅读 2020-06-22 19:39:30
    说到排序,大家第一反应基本上是内排序,是的,算法嘛,玩的就是内存,然而内存...一:N路归并排序 1.概序 我们知道算法有一种叫做分治思想,一个大问题我们可以采取分而治之,各个突破,当子问题解决了,大问...
  • 目录 【前言】 【冒泡排序(Bubble Sort)】(稳定) 【快速排序(Quick Sort)】(不稳定) 【插入排序(Insert Sort)】(稳定) ...【归并排序(Merge Sort)】(稳定) 【基数排序(Radix So...
  • 对N个记录进行归并排序,归并趟的数量级是O(NlogN)。() [解析]归并的数量级在O(logN)? 每上下相邻的两层之间,从上层到下层的过程就是一趟归并 满二叉树深度为k的二叉树的最后一层结点个为2^k - 1 所以叶子为N...
  • 上一篇日志讲到了自己对堆排序的学习,堆排序时间复杂度能达到O(NlogN),且不需要额外的...那就是归并排序。 归并操作其实更多用在外部排序中- -、,是外部存储器最常用的排序方法,用分而治之的思想,下面会说。...
  • 分治算法解决归并排序

    千次阅读 2020-03-20 21:44:43
    分治算法 问题引入:  前文说到,叶天帝集结天庭... 这一日,叶天帝与众黑暗至尊展开了白热化的战斗,叶天帝虽强,但终归是双拳难敌四手,战况岌岌可危,叶天帝险象环生。在这千钧一发之际,只见大黑狗施展“行...
  • 归并排序(Merge Sort)是利用归并的思想实现的排序方法,该算法采用经典的分治(divide-and-conquer)策略(分治法将问题分成一些小的问题然后进行递归求解,而治的阶段则将分的阶段得到的各答案“修补”在一起,即...
  • 排序(Sorting)是计算机程序设计的一种重要操作,它的功能是将一个数据元素(或记录)的任意序列,重新排列成一个按关键字有序的序列。由于待排序的记录数量不同,使得排序过程涉及的存储器不同,可将排序方法...
  • 题目:给定两个大小为 m 和 n 的有序数组 nums1 和 nums2 。请找出这两个有序数组的中位数。要求算法的时间复杂度为 O(log (m+n)) ...中位数是 (2 + 3)/2 = 2.5解析:很基本的归并排序合并数组的思想,因为两个...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 47,129
精华内容 18,851
关键字:

归并排序求中位数