热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

开发笔记:考研数据结构——内部排序

本文由编程笔记#小编为大家整理,主要介绍了考研数据结构——内部排序相关的知识,希望对你有一定的参考价值。考研数据结构——排序
本文由编程笔记#小编为大家整理,主要介绍了考研数据结构——内部排序相关的知识,希望对你有一定的参考价值。

考研数据结构——排序


直冒简希,快堆并基


直接插入排序

算法思路:将待排序的关键字与已经排好的部分有序序列的中关键字从后往前进行比较,插入到合适位置,直至所有关键字都被插入到有序序列中

void insertSort(int R[],int n)//数组元素个数
{
int i,j;
int temp;
for(i=1;i {
temp=R[i];
j=i-1;
while(j>0&&temp {
R[j+1]=R[j];
--j;
}
R[j+1]=temp;
}
}

冒泡排序

算法思路:每一趟排序从第一个关键字开始,与其后一个进行比较,如果前一个大于后一个则交换,否则不交换,这样第一趟就可以把序列中最大的关键字交换到最后,第二趟可以把第二大的关键字交换到倒数第二个位置上......排序结束的条件是在一趟排序过程中没有发生关键字交换

void bubbleSort(int R[],int n)
{
int i,j,flag,temp;
for(i=n-1;i>=1;--i)
{
flag=0;
for(j=i;j<=i;j++)
{
if(R[j-1]>R[j])
{
temp=R[j];
R[j]=R[j-1];
R[j-1]=temp;
flag=1;//发生了关键字交换
}
}
if(flag==0)
return;
}
}

简单选择排序

算法思路:从无序序列中每趟挑出一个最小的关键字,与第i个关键字交换。

void selectSort(int R[],int n)
{
int i,j,k,temp;
for(i=0;i {
k=i;
//从无序序列中挑出最小的一个关键字
for(j=k+1;j if(R[k]>R[j])
k=j;
//将上面挑出的最小关键字与i位置上的关键字交换
temp=R[i];
R[i]=R[k];
R[k]=temp;
}
}

希尔排序

算法思路:将序列按照规则划分为几个子序列,分别对这几个子序列进行直接插入排序。缩小增量,最后一个增量一定是1。如有10个关键字,第一个增量为5,则0-5,1-6,2-7,3-8,4-9;第二个增量为3,则0-3-6-9,1-4-7,2-5-8;第三个增量为1,直接插入排序。

//考研数据结构需重点掌握其执行流程
void shellSort(int R[],int n)
{
int temp;
for(int gap=n/2;gap>0;gap/=2)
{
for(int i=gap;i {
temp=R[i];
int j;
for(j=1;j>=gap&&R[j-gap]>temp;j-=gap)
R[j]=R[j-gap];
R[j]=temp;
}
}
}

快速排序

算法思路:每一趟选择序列的第一个关键字作为枢轴,将序列中比枢轴小的放到枢轴前面,比枢轴大的放到枢轴后面。

void quickSort(int R[],int low,int high)
{
int temp;
int i=low,j=high;//指向头尾关键字
if(low {
temp=R[low];//第一个数作为枢轴
while(i {
//从后往前扫描,遇到比枢轴小的关键字,停到这里
while(j>i&&R[j]>=temp)
--j;
//将j位置上这个比枢轴小的值放到前面i位置上
if(i {
R[i]=R[j];
++i;
}
//从前往后扫描,遇到比枢轴大的关键字,停到这里
while(i ++i;
//将i位置上这个比枢轴大的值放到后面j位置上
if(i {
R[j]=R[i];
--j;
}
}
//i和j相遇后,把枢轴放入这个i等于j的位置
R[i]=temp;
//分别对枢轴左边和右边的序列进行递归划分
quickSort(R,low,i-1);
quickSort(R,i+1,high);
}
}

堆排序

算法思路:将待排序序列构造成一个大顶堆,此时,整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换,此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆,这样会得到n个元素的次小值。如此反复执行,便能得到一个有序序列。

void sift(int R[],int low,int high)//节点调整
{
int i=low,j=2*i;
int temp=R[i];
while(j<=high)
{
if(j ++j;
if(temp {
R[i]=R[j];
i=j;
j=2*i;
}
else
break;
}
R[i]=temp;
}
void heapSort(int R[],int n)
{
int i,temp;
for(i=n/2;i>=1;--i)
sift(R,i,n);
for(i=n;i>=2;--i)
{
//换出根节点的关键字,将其放入最终位置
temp=R[1];
R[1]=R[i];
R[i]=temp;
sift(R,1,i-1);
}
}

归并排序

算法思路:先将序列分为两半,对两个序列进行归并排序,得到两个有序序列,然后将这两个有序序列合并成为一个有序序列。

void merge(int arr[],int low,int mid,int high)
{
int i,j,k;
int n1=mid-low+1;
int n2=high-mid;
int L[n1],R[n2];
for(i=0;i L[i]=arr[low+i];
for(j=0;j R[j]=arr[mid+1+j];
i=0;
j=0;
k=low;
while(i {
if(L[i]<=R[j])
arr[k]=L[i++];
else
arr[k]=R[j++];
k++;
}
while(i arr[k++]=L[i++];
while(j arr[k++]=R[j++];
}
void mergeSort(int R[],int low,int high)
{
if(low {
int mid=(low+high)/2;
mergeSort(R,low,mid);
mergeSort(R,mid+1,high);
merge(R,low,mid,high);//把R数组中low到mid和mid+1到high范围内的两段有序序列归并成一段有序序列
}
}

基数排序

算法思路:不用比较,有最低位优先和最高位优先两种。以最低位优先为例,第一趟按最低位放入对应的桶中,收集时从0号桶从下往上收集,依次排开,收集结果最低位有序。依次对中间位和高位进行分配和收集,最后整个序列有序。


推荐阅读
  • 本文回顾了作者在求职阿里和腾讯实习生过程中,从最初的迷茫到最后成功获得Offer的心路历程。文中不仅分享了个人的面试经历,还提供了宝贵的面试准备建议和技巧。 ... [详细]
  • 贡献转移在计算每个元素的作用的时候,我们可以通过反向枚举作用效果,添加到作用元素的身上,这种方法叫做贡献转移。更正式的说, ... [详细]
  • Python3爬虫入门:pyspider的基本使用[python爬虫入门]
    Python学习网有大量免费的Python入门教程,欢迎大家来学习。本文主要通过爬取去哪儿网的旅游攻略来给大家介绍pyspid ... [详细]
  • 深入解析 C++ 中的 String 和 Vector
    本文详细介绍了 C++ 编程语言中 String 和 Vector 的使用方法及特性,旨在帮助开发者更好地理解和应用这两个重要的容器。 ... [详细]
  • 使用Matlab创建动态GIF动画
    动态GIF图可以有效增强数据表达的直观性和吸引力。本文将详细介绍如何利用Matlab软件生成动态GIF图,涵盖基本代码实现与高级应用技巧。 ... [详细]
  • 本文详细介绍了在Luat OS中如何实现C与Lua的混合编程,包括在C环境中运行Lua脚本、封装可被Lua调用的C语言库,以及C与Lua之间的数据交互方法。 ... [详细]
  • 本文深入探讨了动态赋值的概念及其在编程实践中的应用,特别是通过Java代码示例来展示如何利用循环结构动态地为数组分配值。 ... [详细]
  • 在解决ACM竞赛题目或力扣挑战时,通常面临1秒到2秒的时间限制。为了确保程序能够高效运行,C++等语言的代码执行次数建议不超过1千万次。 ... [详细]
  • OpenCV中的霍夫圆检测技术解析
    本文详细介绍了如何使用OpenCV库中的HoughCircles函数实现霍夫圆检测,并提供了具体的代码示例及参数解释。 ... [详细]
  • 本文提供了一种有效的方法来解决当Android Studio因电脑意外重启而导致的所有import语句出现错误的问题。通过清除缓存和重建项目结构,可以快速恢复开发环境。 ... [详细]
  • 本文介绍了如何利用OpenCV库进行图像的边缘检测,并通过Canny算法提取图像中的边缘。随后,文章详细说明了如何识别图像中的特定形状(如矩形),并应用四点变换技术对目标区域进行透视校正。 ... [详细]
  • 函子(Functor)是函数式编程中的一个重要概念,它不仅是一个特殊的容器,还提供了一种优雅的方式来处理值和函数。本文将详细介绍函子的基本概念及其在函数式编程中的应用,包括如何通过函子控制副作用、处理异常以及进行异步操作。 ... [详细]
  • 本文将探讨一个经典算法问题——最大连续子数组和。我们将从问题定义出发,逐步深入理解其背后的逻辑,并通过实例分析加深理解。 ... [详细]
  • Maven + Spring + MyBatis + MySQL 环境搭建与实例解析
    本文详细介绍如何使用MySQL数据库进行环境搭建,包括创建数据库表并插入示例数据。随后,逐步指导如何配置Maven项目,整合Spring框架与MyBatis,实现高效的数据访问。 ... [详细]
  • 软件测试行业深度解析:迈向高薪的必经之路
    本文深入探讨了软件测试行业的发展现状及未来趋势,旨在帮助有志于在该领域取得高薪的技术人员明确职业方向和发展路径。 ... [详细]
author-avatar
zhousulian
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有