首页 > 其他分享 >排序

排序

时间:2024-10-06 19:12:02浏览次数:8  
标签:放到 元素 枢轴 算法 序列 排序

排序的定义

排序就是重新排列表中的元素,使表中的元素满足关键字有序的过程

算法的稳定性:若待排序表中有两个元素相等,经过排序后原来位置这两个元素的相对位置不变,则称这个算法是稳定的

根据在排序过程中数据元素是否完全放在内存中,可以将排序算法分为两类:内部排序和外部排序。内部排序是指在排序期间元素全部存放在内存中的排序,外部排序是指在排序期间元素无法同时存放在内存中,必须在排序的过程中根据要求不断地在内外存之间移动的排序

不同排序的比较

时间复杂度、空间复杂度、稳定性

img

解释说明:快排所需要的额外空间来自其递归栈

算法简要描述

非常抱歉,之前的回答可能有误。以下是正确识别的表格内容:

算法种类 算法简要描述 备注
直接插入排序 第i趟排序开始之前,前i-1个元素有序,将第i个元素插入到这个序列中 -
冒泡排序 每次排序将待排序序列的最大值或者最小值放到最终的位置 -
简单选择排序 每次选出最大值或者最小值放到最终的位置
希尔排序 构造一个增量序列,在子序列内部选用插入排序 -
快速排序 选择一个枢轴,每趟排序将比枢轴大的数都放到枢轴一边,比枢轴小的数放到另一边 -
堆排序 构造堆这种数据结构,利用堆来进行排序 注意每次弹出的元素是放到最后一个位置,所以构造递增序列要用大根堆
二路归并排序 每次合并两个有序序列 -
基数排序 按照每一位的大小来构造排序 注意在第二趟排序完成后,最低位将可能不再有序

各排序算法的其他性质

算法种类 比较次数是否与序列相关 备注
直接插入排序 -
冒泡排序 -
简单选择排序
希尔排序 -
快速排序 -
堆排序 -
二路归并排序 -
基数排序 - 基数排序不依赖于元素之间的比较

标签:放到,元素,枢轴,算法,序列,排序
From: https://www.cnblogs.com/AH20/p/18449304

相关文章

  • CCF-CSP认证资格考试题解系列——第4次第2题数字排序
    #include<iostream>#include<algorithm>usingnamespacestd;structre{ intvalue;//数值 intnum;//次数}re[1010];boolcmp(structrea,structreb){ if(a.num==b.num)returna.value<b.value;//次数相同是小的优先 returna.num>b.num;//次数不相同是次数优......
  • 信息学奥赛复赛复习13-CSP-J2021-02插入排序-排序稳定性、插入排序、sort排序、结构体
    PDF文档公众号回复关键字:202410061P7910[CSP-J2021]插入排序[题目描述]插入排序是一种非常常见且简单的排序算法。小Z是一名大一的新生,今天H老师刚刚在上课的时候讲了插入排序算法。假设比较两个元素的时间为O(1),则插入排序可以以O(n^2)的时间复杂度完成长度为......
  • 归并排序笔记
    inttmp[];//temp数组存储数据voidmerge_sort(inta[],intl,intr){ if(l>=r)return;//递归到最后只有一个数返回 intmid=(l+r)/2;//确定分界点l~midmid+1~r; merge_sort(a,l,mid); merge_sort(a,mid+1,r);//递归左右两边 intk=0,i=l,j=mi......
  • 各种排序算法相关性质整理
    排序算法稳定性最优时间复杂度平均时间复杂度最坏时间复杂度空间复杂度选择排序不稳定\(O(N^2)\)\(O(N^2)\)\(O(N^2)\)\(O(1)\)冒泡排序稳定\(O(N)\)\(O(N^2)\)\(O(N^2)\)\(O(1)\)插入排序稳定\(O(N)\)\(O(N^2)\)\(O(N^2)\)\(O(1)\)计数排序......
  • 归并排序
    inttmp[];//temp数组存储数据voidmerge_sort(inta[],intl,intr){if(l>=r)return;//递归到最后只有一个数返回intmid=(l+r)/2;//确定分界点l~midmid+1~r;merge_sort(a,l,mid);merge_sort(a,mid+1,r);//递归左右两边intk=0,i=l,j=mid+1;......
  • 快速排序
    取数组中任意一个数,用两个指针i,j(i在j左侧)分别从左右边界向中间逼近,当i>=x时,i停止移动,j开始逼近当i>=x并且j<=x时,交换两个指针所指的数的数值,开启下一轮迭代直到i与j分别越过中间数(i在j右侧)开启下一轮快速排序(递归quick_sort分割数组寻找不同的x)最后使得数组排序完毕·注意数......
  • 53_初识搜素引擎_上机动手实战如何定制搜索结果的排序规则
    1、默认排序规则默认情况下,是按照_score降序排序的然而,某些情况下,可能没有有用的_score,比如说filterGET/_search{"query":{"bool":{"filter":{"term":{"author_id":1}}}}}当然,也可以是constant_scoreGET/_search{"query"......
  • 54_初识搜索引擎_解密如何将一个field索引两次来解决字符串排序问题
    如果对一个stringfield进行排序,结果往往不准确,因为分词后是多个单词,再排序就不是我们想要的结果了通常解决方案是,将一个stringfield建立两次索引,一个分词,用来进行搜索;一个不分词,用来进行排序PUT/website{"mappings":{"article":{"properties":{"title":{"type":"t......
  • pbootcms列表页排序切换(时间/浏览量/推荐…)
    为了让PBootCMS列表页支持多种排序方式,并且在点击按钮时能够切换排序方式,可以通过给URL添加参数并在前端标签中进行判断来实现。以下是详细的实现步骤和代码示例。实现步骤添加按钮中的URL参数在列表调用标签中处理排序参数整合代码详细步骤1.添加按钮中的URL参数在按钮......
  • 快速排序算法及多线程试验
    1)快速排序算法算法实现:选定一个起点/终点位置上的数A小于数A的放在A左侧,大于的放在右侧对A左侧和右侧数组递归的执行步骤2//分区函数template<typenameT>intpartition(Tarr[],intlength){ if(length<=1) return1; inti=1; intj=length-1; //se......