数据结构六大排序

news/2024/3/29 16:11:44/文章来源:https://blog.csdn.net/qq1053984219/article/details/129261023

 

1.插入排序

 1.插入排序在这里插入图片描述

 思路:

从第一个元素开始认为是有序的,去一个元素tem从有序序列从后往前扫描,如果该元素大于tem,将该元素一刀下一位,循环步骤3知道找到有序序列中小于等于的元素将tem插入到该元素后,如果已排序所有元素都大于tem则将插入到下标为0的位置, 如此重复。

红线前认为是有序的 。

void InsertSort(int* arr, int n)
{for (int i = 0; i < n - 1; ++i){//记录有序序列最后一个元素的下标int end = i;//待插入的元素int tem = arr[end + 1];//单趟排while (end >= 0){//比插入的数大就向后移if (tem < arr[end]){arr[end + 1] = arr[end];end--;}//比插入的数小,跳出循环else{break;}}//tem放到比插入的数小的数的后面arr[end  + 1] = tem;//代码执行到此位置有两种情况://1.待插入元素找到应插入位置(break跳出循环到此)//2.待插入元素比当前有序序列中的所有元素都小(while循环结束后到此)}
}

插入排序:待排序列接近逆序时是最坏情况O(N*N),接近升序是最快为O(N)。

空间复杂度O(1)

2.希尔排序 

 2.希尔排序

在这里插入图片描述思路:

将待排序序列进行预排序再进行插入排序。选定一个整数gap作为组距,将距离为gap的元素认为是一组进行直接插入排序,再取一个比原gap小的新gap重复操作 当gap为1时预排序完毕最后进行一次直接插入排序。

//希尔排序
void ShellSort(int* arr, int n)
{int gap = n;while (gap>1){//每次对gap折半操作gap = gap / 2;//或者gap=gap/3+1    //单趟排序for (int i = 0; i < n - gap; ++i){int end = i;int tem = arr[end + gap];while (end >= 0){if (tem < arr[end]){arr[end + gap] = arr[end];end -= gap;}else{break;}}arr[end + gap] = tem;}}
}

时间复杂度平均:O(N^1.3)(记住就行了)
空间复杂度:O(1)

3.选择排序

3.选择排序在这里插入图片描述

 每次从待排序列中选出一个最小值和最大值,分别放在序列头和尾。用到SWAP

//选择排序
void swap(int* a, int* b)
{int tem = *a;*a = *b;*b = tem;
}
void SelectSort(int* arr, int n)
{//保存参与单趟排序的第一个数和最后一个数的下标int begin = 0, end = n - 1;while (begin < end){//保存最大值的下标int maxi = begin;//保存最小值的下标int mini = begin;//找出最大值和最小值的下标for (int i = begin; i <= end; ++i){if (arr[i] < arr[mini]){mini = i;}if (arr[i] > arr[maxi]){maxi = i;}}//最小值放在序列开头swap(&arr[mini], &arr[begin]);//防止最大的数在begin位置被换走if (begin == maxi){maxi = mini;}//最大值放在序列结尾swap(&arr[maxi], &arr[end]);++begin;--end;}
}

注意因为先交换最小值,可能导致一开始最大值在gegin最小值交换后最大值也被换走。所以加一句判断,如果最大值是begin,则交换最大值时先把maxi赋值成mini才正确。

时间复杂度:O(N^2)
空间复杂度:O(1)

4.冒泡排序

 在这里插入图片描述

void bubble_sort(int* arr, int sz)
{int i = 0;for (i = 0; i < sz-1; i++){//每一趟冒泡排序int j = 0;for (j = 0; j < sz-i-1; j++){if (arr[j]>arr[j + 1]){int tmp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = tmp;}//两两相邻元素进行交换}}}

时间复杂度:最坏情况:O(N^2)
      最好情况:O(N)
空间复杂度:O(1)

5.堆排序

                 参考(77条消息) 二叉树——堆_RoseLJ的博客-CSDN博客

6.快速排序

 (1)左右指针法

在这里插入图片描述

思路:

1.定义一个key一般是最左边或最右。

2.定义一个begin和end(重点如果选择最左边的数据为key,则需要end先走;如果选择最右边的数据为key,则需要begin先走

3.走的过程中end遇到小于key的树停下,begin开始走直到遇到一个大于key的数,begin和end内容交换,然后end再开始走,如此进行下去直到最终begin和end相遇,相遇后将相遇点与key交换(此步骤为选取左边为key时)。此时key左边都是小于key的树,右边都是大于kkey的数。

4.将key的左右序列重复以上操作知道左右序列只有一个数据或者不存在时停止。

//快速排序   hoare版本(左右指针法)
void QuickSort(int* arr, int begin, int end)
{//只有一个数或区间不存在if (begin >= end)return;int left = begin;int right = end;//选左边为keyint keyi = begin;while (begin < end){//右边选小   等号防止和key值相等    防止顺序begin和end越界while (arr[end] >= arr[keyi] && begin < end){--end;}//左边选大while (arr[begin] <= arr[keyi] && begin < end){++begin;}//小的换到右边,大的换到左边swap(&arr[begin], &arr[end]);}swap(&arr[keyi], &arr[end]);keyi = begin;//[left,keyi-1]keyi[keyi+1,right]QuickSort(arr, left, keyi - 1);QuickSort(arr,keyi + 1,right);
}

时间复杂度在这里插入图片描述

嵌套过程类似于二叉树高度为logN,每层约有N个数

(2)挖坑法(递归)

思路:与左右指针法类似

1.选出一个数(最左或最右)放在key中,在该数据位置形成一个坑。

2.定义l和r(如果在最左边挖坑则需要r先走;在最右边挖坑需要l先走)。

后面思路类似于双指针。

在这里插入图片描述

//快速排序法  挖坑法
void QuickSort1(int* arr, int begin, int end)
{if (begin >= end)return;int left = begin,right = end;int key = arr[begin];while (begin < end){//找小while (arr[end] >= key && begin < end){--end;}//小的放到左边的坑里arr[begin] = arr[end];//找大while (arr[begin] <= key && begin < end){++begin;}//大的放到右边的坑里arr[end] = arr[begin];}arr[begin] = key;int keyi = begin;//[left,keyi-1]keyi[keyi+1,right]QuickSort1(arr, left, keyi - 1);QuickSort1(arr, keyi + 1, right);
}

快速排序优化:三数取中

在有序或接近有序时,快速排序效率较低,利用三数取中可提高效率。

三数取中就是从待排序列的第一个元素,中间元素和最后一个元素中选出大小位于中间的元素,把这个元素作为基准值key。

int GetMid(int* a,int left,int mid,int right)
{if(a[left] >a[mid]){if(a[mid] > a[right]){return mid;}else if(a[left] > a[right]){return right;}else{return left;}}else //a[left] < a[mid]{if(a[mid] < a[right]){return mid;}else if(a[left] > a[right]){return right;}else{return left;}}
}

 挖坑法非递归

//单趟排
int PartSort(int* arr, int begin, int end)
{int key = arr[begin];while (begin < end){while (key <= arr[end] && begin < end){--end;}arr[begin] = arr[end];while (key >= arr[begin] && begin < end){++begin;}arr[end] = arr[begin];}arr[begin] = key;int meeti = begin;return meeti;
}void QuickSortNoR(int* arr, int begin, int end)
{stack<int> st;//先入右边st.push(end);//再入左边st.push(begin);while (!st.empty()){//左区间int left = st.top();st.pop();//右区间int right = st.top();st.pop();//中间数int mid = PartSort(arr, left, right);//当左区间>=mid-1则证明左区间已经排好序了if (left < mid - 1){st.push(mid - 1);st.push(left);}//当mid+1>=右区间则证明右区间已经排好序if (right > mid + 1){st.push(right);st.push(mid + 1);}}
}

(3) 前后指针法

 思路

1.选出key(最左或最右)。

2.cur找比key小的找到停下来。

3.++prev,交换prev位置和cur位置的值。

int partion(int* array,int begin,int end)//待排序数组的首指针,待排序的首尾元素下标
{int key = array[begin];//选取第一个元素为基准值int prev = begin;//前指针int cur = prev + 1;//后指针whiel(cur <= end){if(array[cur] > key&&++prev != cur)//如果cur的值小于key判断++prev的值是否等于cur//若不等于,则交换prev和cur的值swap(array,prev,cur);cur++;//cur向后移动}//当跳出循环时,说明prev及之前的值都是小于基准值的数,则交换prev指向的值和基准值swap(array,prev,begin);return prev;//返回此时基准值的下标,便于下次递归调用时分组
}
void quicksort(int* array,int begin,int end)
{if(begin >= end)return ;int keypos = partion(array,begin,end);quicksort(array,begin,keypos - 1);quicksort(array,keypos + 1,end);
}

6.归并排序

思路:

1.将待排序的线性表不断切分成诺干个子表知道每个子表只包含一个元素,这是可以认为包含一个元素的子表是有序表。

2.将有序表两两合并,每合并一次就产生一个新的更长的有序表,重复合并知道最后只剩下一个表。

(1)递归实现 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_75551.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

如何防止DNS污染?

对于DNS污染&#xff0c;一般除了使用代理服务器和VPN之类的软件之外&#xff0c;并没有什么其它办法。但是利用我们对DNS污染的了解&#xff0c;还是可以做到不用代理服务器和VPN之类的软件就能解决DNS污染的问题&#xff0c;从而在不使用代理服务器或VPN的情况下访问原本访问…

设计模式系列 - 代理模式及动态代理详解

定义 为其他对象提供一种代理以控制对这个对象的访问。在某些情况下&#xff0c;一个对象不适合或者不能直接引用另一个对象&#xff0c;而代理对象可以在客户端和目标对象之间起到中介的作用。 结构 抽象角色&#xff1a;通过接口或抽象类声明真实角色实现的业务方法。 代…

C++ STL:容器 Container

文章目录1、序列容器1.1、容器共性1.2、vectorvector 结构* vector 扩容原理* vector 迭代器失效1.3、dequedeque 结构deque 迭代器deque 模拟连续空间1.4、listlist 特殊操作list 结构list 迭代器2、关联式容器2.1、容器共性2.2、容器特性3、无序关联式容器3.1、容器共性3.2、…

电子科技大学 高级计算机系统结构 考试回忆

首先题量不算小&#xff0c;因此没有太多时间把题都记出来&#xff0c;但是叙述一下题的类型希望能帮到以后选了这门课大家&#xff0c;在网上确实没有搜到这门课有关考试的任何资料&#xff0c;所以我也没啥参考全凭记忆和老师的PPT结合。复习的时候老师给了大纲&#xff0c;就…

【k8s】Kubernetes的学习(1.k8s概念和架构)

目录 1.首先要知道&#xff0c;Kubernetes为什么简称为k8s? 2.Kubernetes概述 2.1 kubernetes基本介绍 2.2 kubernetes的特性 2.3 kubernetes集群架构组件 2.3.1 Master (主控节点) 2.3.2 node (工作节点) 2.4 k8s核心概念 2.4.1 Pod 2.4.2 controller 2.4.3 Se…

Python自动发周报给老板,到点赶紧跑

嗨害大家好鸭&#xff01;我是小熊猫~ 作为一个社畜人 …勤勤恳恳的打工人&#xff01;&#xff01;&#xff01; 几乎每周都要写周报 没办法只能用点小技术 用python写个小工具 让它来给老板发周报哈哈哈 更多python摸鱼小技巧、基础知识:点击此处跳转文末名片获取 目标细…

收下这份十万商家称赞的开店攻略,带你发家致富!

理想与现实之间的距离&#xff0c;大概就是开店吧&#xff01;总觉得自己投点钱&#xff0c;一两年回本&#xff0c;后面每月轻松赚几万、几十万&#xff1b;结果却发现房租太贵、人工太贵、自己什么都不懂&#xff0c;然后随波逐流的没有特色。其实&#xff0c;细心的朋友会发…

【VUE】二 vue指令

目录 一、插值表达式 二、v-bind指令(对标签中的属性进行操作) 三、v-model指令&#xff08;input、select、textarea等。【双向绑定】&#xff09; 四、v-for循环指令 五、v-on(事件指令) 六、v-if条件判断 七、v-show&#xff08;条件显示或隐藏&#xff09; 八、案例…

王道计算机网络课代表 - 考研计算机 第五章 传输层 究极精华总结笔记

本篇博客是考研期间学习王道课程 传送门 的笔记&#xff0c;以及一整年里对 计算机网络 知识点的理解的总结。希望对新一届的计算机考研人提供帮助&#xff01;&#xff01;&#xff01; 关于对 “传输层” 章节知识点总结的十分全面&#xff0c;涵括了《计算机网络》课程里的全…

MySQL 学习笔记(借鉴黑马程序员MySQL)

MySQL视频课链接 MySQL概述 数据库相关概念 数据库是存储数据的仓库&#xff0c;数据是有组织的进行存储&#xff08;DataBase&#xff09; 数据库管理系统是操纵和管理数据库的大型软件&#xff08;DataBase Management System&#xff09; SQL是操作关系型数据库的编程语…

_Linux (HTTP协议)

文章目录1. 认识URL2. urlencode和urldecode3. HTTP协议格式3-1. HTTP请求3-1. HTTP响应4. HTTP的方法5. HTTP的状态码6. TTP常见Header7. 最简单的HTTP服务器虽然我们说, 应用层协议是我们程序猿自己定的但实际上, 已经有大佬们定义了一些现成的, 又非常好用的应用层协议, 供我…

Android问题笔记 - 打开Android Studio先弹出项目选择框

专栏分享点击跳转>Unity3D特效百例点击跳转>案例项目实战源码点击跳转>游戏脚本-辅助自动化点击跳转>Android控件全解手册点击跳转>Scratch编程案例 &#x1f449;关于作者 众所周知&#xff0c;人生是一个漫长的流程&#xff0c;不断克服困难&#xff0c;不断…

【JavaWeb】Servlet基础

文章目录1.Tomcat服务器安装注意事项2.编写WebApp3.BS系统角色和协议4.模拟Servlet4.1模拟sun公司4.2模拟Tomcat服务器4.3模拟WebApp开发者5.开发一个带有Servlet的WebApp5.1创建一个名为crm的项目5.2 在项目中创建一个名为WEB-INF的文件&#xff08;必须&#xff09;5.3在WEB-…

MATLAB常用函数-gcf / gca / gco

MATLAB R2019a gcf: 返回当前图像对象的句柄值 语法&#xff1a; h gcf % 返回当前图像的句柄&#xff0c;如果没有图像&#xff0c;则会自动创建一个&#xff0c;然后返回其句柄 gca: 返回当前坐标轴对象的句柄值 语法&#xff1a; h gca % 返回当前图像中的当前坐标…

21_FreeRTOS内存管理

目录 FreeRTOS内存管理 FreeRTOS内存管理算法 内存管理相关API函数介绍 实验源码 FreeRTOS内存管理 在使用FreeRTOS创建任务、队列、信号量等对象的时,一般都提供了两种方法: 动态方法创建 自动地从 FreeRTOS 管理的内存堆中申请创建对象所需的内存&#xff0c;并且在对…

Git学习(1)pro git阅读

目录 目录&#xff1a; 1. 起步 2. Git 基础 3. Git 分支 4. 服务器上的 Git 5. 分布式 Git 第一章 1.3 Git是什么 1.6运行git前的配置 该开源图书网站 Git - Book (git-scm.com) 目录&#xff1a; 1. 起步 1.1 关于版本控制1.2 Git 简史1.3 Git 是什么&#xff1f;1…

卡方检验

一、卡方检验假设检验的一种&#xff0c;以实际观测值与期望值之间的偏离程度&#xff0c;解决是服从某个构成比率和是否具有相关性的问题。其偏离程度决定卡方值的大小&#xff0c;卡方值越小&#xff0c;偏差越小&#xff0c;实际值越趋于符合期望值。二、步骤在显著性为α0.…

Malware Dev 01 - 免杀之 PPID Spoofing 原理解析

写在最前 如果你是信息安全爱好者&#xff0c;如果你想考一些证书来提升自己的能力&#xff0c;那么欢迎大家来我的 Discord 频道 Northern Bay。邀请链接在这里&#xff1a; https://discord.gg/9XvvuFq9Wb我会提供备考过程中尽可能多的帮助&#xff0c;并分享学习和实践过程…

Active Directory管理帮助台

随着组织规模扩大&#xff0c;需要大幅增加Active Directory帮助台指派。随着组织开始在新地点开设办事处&#xff0c;管理员管理所有地点的用户变得极为繁琐。在这样的情况下&#xff0c;帮助台指派需要横跨不同的域以方便多域管理。尝试使用本机AD工具或PowerShell执行帮助台…

守护进程与TCP通讯

目录 一.守护进程 1.1进程组与会画 1.2守护进程 二.创建守护进程 setsid函数&#xff1a; 三. TCP通讯流程 3.1三次握手&#xff1a; 3.2 数据传输的过程 3.3四次挥手 一.守护进程 1.1进程组与会画 进程组&#xff1a;进程组由一个进程或者多个进程组成&#xff0c;每…