首页 > 其他分享 >排序Part3——归并排序

排序Part3——归并排序

时间:2024-08-06 09:25:47浏览次数:13  
标签:归并 调用 合并 指针 列表 Part3 排序 left

续上篇,我们继续讲述排序的内容:

归并排序

首先我们先考虑两个已经排好序的列表,现在要使他们合成一个列表并且保证合成的列表也有序,那应该怎么做呢?
其实呢,以上过程我们成为一次合并

一次合并

其实算法很简单,我们先分别设置两个指针,一个指向表1,一个指向表2,同时按顺序历遍:
第一步比较两个指针指向元素的大小,小的先存到一个新的数组中,并且小的数的指针要加1.
在这里插入图片描述

第二步:循环往复,直到有一个表历遍完成就退出循环
在这里插入图片描述

第三步:检查有无剩余的元素未进入新表的按顺序入表
在这里插入图片描述

def one_merge(li,left,mid,right):
	i=left
	j=mid+1
	newli=[]
	#用两个指针访问列表
	while i<=mid and j<=high:
		if ll[i]<=li[j]:
			num=li[i]
			i+=1
		else:
			num=li[j]
			j++1
		newli.append(num)
#检查有无遗漏的元素,添加进去
	while i<=mid:
		newli.append(li[i])
		i+=1
	while j<=high:
		newli.append(li[j])
		j+=1
	li。clear()#清空原有列表
	li[low:high+1]=newli#装回原来列表中

在一次合并的基础上,我们可以思考一下怎么得到一个完整有序的列表:在实际的情况中,其实我们无法得到一个列表由两个有序的部分组成,那怎么得到一个有序的小列表呢,显然我们也可以用一次合并的方法。这样排序的算法显然是要把一次合并递归调用。

调用一次合并完成排序

第一步:设置终止条件,显然列表只有一个值不用再排序和递归
第二步:左边调用排序函数得到排序好的左表
第三步:右边调用排序函数得到排序好的右表
第三步:将排序好的左表和右表进行一次合并

def merge_sort(li,left,right):#考虑到用递归实现必须要设置左右的参数来界定
	if left<right:
		mid=(left+right)//2
		merge_sort(li,left,mid)#左边调用排序函数得到排序好的左表
		merge_sort(li.mid+1,right)#右边调用排序函数得到排序好的右表
		one_merge(li,left,mid,right)#将排序好的左表和右表进行一次合并

标签:归并,调用,合并,指针,列表,Part3,排序,left
From: https://blog.csdn.net/hh222_/article/details/140931090

相关文章

  • COUNTING-SORT(计数排序) and
    计数排序             计数排序假设n个输入元素(适用于小范围区间)中的每一个都是在0到k区间内的一个整数,其中k为某个整数。当k=O(n)时,排序的运行时间为.    计数排序的基本思想:对每一个输入的元素x,确定小于x的元素个数。利用这一信息,就可以直接把x......
  • 排序算法2:直接选择排序与快速排序
    目录1.直接选择排序1.1直接选择排序的优化2.快速排序2.1基准值的置位(Hoare版) 2.2挖坑法2.3lomuto前后指针前言前面我们进入了排序算的讲解。今天我们将继续学习几种重要的排序思想,好,咱们三连上车开始今天的内容。1.直接选择排序在元素的集合中选出最大值(最小值),......
  • P9596 冒泡排序 2 题解
    题目链接。Statement记\(f(A)\)为序列\(A\)的冒泡排序趟数,操作:单点改,全局查\(f(A)\).\(n,m\le5\cdot10^5\),值域1e9.Solution结论:\[Ans=\max_{i\in[1..n]}\left\{\sum_{j\in[1..i]}[A_j>A_i]\right\}\]怎么观察出来啊QAQ证明:对于每个位置\(p\),观察到每趟都......
  • MySQL 是如何实现数据的排序的?
    1.背景或许你面试的时候被问到了mysql的排序问题又或许你在学习排序算法的时候想到了数据库的排序是如何实现的呢下面重点从面试的角度来回答这个问题2.面试回答1.普通面试者回答普通面试者的回答通常是点对点的回答,如下:MySQL实现数据的排序主要通过排序算法和索引结构......
  • 希尔排序, 插入排序, 冒泡排序, 选择排序【C++】
    希尔排序,插入排序,冒泡排序,选择排序测试代码希尔排序选择排序冒泡排序插入排序测试代码#include<iostream>usingnamespacestd;intmain(){intarr[6]={0};intlen=sizeof(arr)/sizeof(int);for(inti=0;i<len;i++){......
  • python用List的内建函数list.sort进行排序
    对List进行排序,Python提供了两个方法方法1用List的内建函数listsort进行排序listsort(func=None,key=None,reverse=False)Python实对List进行排序,Python提供了两个方法方法1.用List的内建函数list.sort进行排序list.sort(func=None,key=None,reverse=False)>>>list=......
  • 数据结构-------------------二叉排序树的查找
    #include<stdio.h>#include<stdlib.h>typedefstructBSTNode{intkey;structBSTNode*lchild;structBSTNode*rchild;}BSTNode,*BSTTree;//递归实现二叉排序树的查找操作BSTNode*BSTSearch(BSTTreeT,intkey){if(T......
  • 冒泡排序法
    1publicclassmaopao{2//编写一个main方法3publicstaticvoidmain(String[]args){45//冒泡排序6//要求从小到大7//要求从大到小8int[]arr={20,-1,89,2,890,7};910inttemp=0;//......
  • 冒泡排序最外层循环最少所需执行次数计算
    给定一个长为\(n\)的排列\(a\),按下列代码执行排序,询问最终\(ans\)的值inlineintBF(){ memcpy(b,a,sizeof(b)); intans=0; for(inti=1;i<n;++i){ boolflag=1; for(inti=1;i<n;++i){ if(b[i]>b[i+1]){ flag=0; swap(b[i],b[i+1]); } } if(fl......
  • 无聊写了一个二叉排序
    staticvoidMain(string[]args){varbinarySortTree=newBinarySortTree();vartestSortArray=newint[]{9,8,7,6,5,4,3,2,1,100,99,88};foreach(varitemintestSortArray){......