关键词:
数据结构之八大算法详解(1)——希尔排序,堆排序,插入排序,选择排序,冒泡排序!
插入排序
基本思想
把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中,直到所有的记录插入完为止,得到一个新的有序序列 。
直接插入排序的特性总结:
-
元素集合越接近有序,直接插入排序算法的时间效率越高
-
时间复杂度:O(N^2^)
-
空间复杂度:O(1),它是一种稳定的排序算法
-
稳定性:稳定
希尔排序( 缩小增量排序 )
希尔排序法又称缩小增量法。希尔排序法的基本思想是:先选定一个整数,把待排序文件中所有记录分成个 组,所有距离为的记录分在同一组内,并对每一组内的记录进行排序。然后,取,重复上述分组和排序的工 作。当到达=1时,所有记录在统一组内排好序。
希尔排序的特点
-
希尔排序是对直接插入排序的优化。
-
当gap > 1时都是预排序,目的是让数组更接近于有序。当gap == 1时,数组已经接近有序的了,这样就会很快。
-
希尔排序的时间复杂度不好计算,因为gap的取值方法很多,导致很难去计算,因此在好些树中给出的 希尔排序的时间复杂度都不固定:
我们的gap取值是用kunyh提出来的方法进行取值的,而且kunth,而且Knuth进行了大量的试验统计,我们就按O(n^1.25^)到O(1.6n^1.25^)来算!
- 稳定性:不稳定
堆排序
堆排序(Heapsort)是指利用堆积树(堆)这种数据结构所设计的一种排序算法,它是选择排序的一种。它是 通过堆来进行选择数据。需要注意的是排升序要建大堆,排降序建小堆。
- 堆排序使用堆来选数,效率就高了很多。
- 时间复杂度:O(N*logN)(每一次调整堆的时间复杂度为logN)
- 空间复杂度:O(1)
- 稳定性:不稳定
分为两步
//代码演示
typedef int HPdataType;
void AdjustDown(HPdataType* a,int parent,int size)
int child = parent*2+1;
while(child < size)
if(child +1 < size && a[child] < a[child+1])
child++;
if(a[parent] < a[child])
swap(&a[parent],&a[child]);
parent = child;
child = parent*2+1;
else
break;
void swap(HPdataType* x,HPdataType* y)
HPdataType temp = *x;
*x = *y;
*y = temp;
int main()
HPdataType a[] = 1,4,19,15,7,34,65,25,27,8;
int size = sizeof(a)/sizeof(a[0]);
for(int i = (size-2)/2;i>=0;i--)//i>0的话无法调整到顶部!
AdjustDown(a,i,size);
//完成建堆
for(int i = 1;i<size;i++)
swap(&a[0],&a[size-1-i]);//为什么要-i呢,因为把该堆最大(小)的放在最后面,然后就不要动他,开始放次大(小)
AdjustDown(a,0,size-i);//然后开始进行调整!
return 0;
直接选择排序
每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的 数据元素排完 。
void SlectSort(int* a, int size)//升序
int begin = 0; int end = size - 1;
while (begin < end)
int mini = begin;
int maxi = begin;
for (int i = begin+1; i <= end; i++)
if (a[mini] > a[i])
mini = i;
if (a[maxi] < a[i])
maxi = i;
swap(&a[mini], &a[begin]);//因为begin == maxi 所以这样写的话,先是最大和最小互换,然后是最小的最大互换又换回来了!
swap(&a[maxi], &a[end]);
begin++;
end--;
void SlectSort(int* a, int size)//升序
int begin = 0; int end = size - 1;
while (begin < end)
int mini = begin;
int maxi = begin;
for (int i = begin+1; i <= end; i++)
if (a[mini] > a[i])
mini = i;
if (a[maxi] < a[i])
maxi = i;
swap(&a[mini], &a[begin]);
if (maxi == begin)
maxi = mini;//修正一下,bigini的位置被换到mini的位置那边去了!
swap(&a[maxi], &a[end]);
begin++;
end--;
直接选择排序的特点
-
直接选择排序思考非常好理解,但是效率不是很好。实际中很少使用
-
时间复杂度为O(^2^)
-
空间复杂度为O(1)
-
稳定性 :不稳定!
冒泡排序
空间复杂度:O(1)
稳定性:稳定
数据结构之八大排序算法(c语言实现)(代码片段)
排序文章目录排序排序的概念及其应用排序的概念排序的定义排序的稳定性排序在现实生活中的应用常见的排序算法常见排序算法的实现直接插入排序希尔排序选择排序堆排序冒泡排序冒泡排序的优化快速排序Hoare法快速排序时... 查看详情
初学c语言很难?带你快速掌握关键字!
...个总结,以便于大家能更好的理解其在代码中的用途。C语言关键字总结static关键字C语言const关键字C语言register关键字用法auto关键字inline内联函数1.static关键字static可以用来修饰局部变量、全局变量、函数局部变量生命周期:原... 查看详情
数据结构c语言排序方法——快速排序详解!
快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序n个项目要Ο(nlogn)次比较。在最坏状况下则需要Ο(n2)次比较,但这种状况并不常见。事实上,快速排序通常明显比其他Ο(nlogn)算法更快,因为它... 查看详情
carson带你学数据结构:图文详解-动态查找静态查找散列查找(代码片段)
前言查找是数据结构中的重要操作今天,我将主要讲解介绍查找的相关知识,如查找算法等,希望你们会喜欢。目录1.简介本节将介绍关于查找的相关基础概念具体请看下图:2.查找需求场景对于不同的查找需求场... 查看详情
算法图解八大排序(代码片段)
...序递归版非递归八、计数排序总结 注:本文基于C语言编写,由VisualStudio2019所实现前言 在我们生活的这个世界中到处都是被排序过的东东,可以说排序是无处不在。常见的莫过于点外卖,按照「销量最高... 查看详情
多个岗位需要的sql语言你掌握了吗?简单例子+详细代码带你一文掌握(代码片段)
数据库以及sql入门知识基础版:多个岗位需要的sql语言你掌握了吗?简单例子+详细代码带你一文掌握带你熟练掌握–进阶版:什么样的程度才是“熟练掌握sql”–MySQL进阶版简单例子+详细代码带你一文掌握关于... 查看详情
8大排序算法图文讲解
...的排序记录,在排序过程中需要访问外存。我们这里说说八大排序就是内部排序。 当n较大,则应采用时间复杂度为O(nlog2n)的排序方法:快速排序、堆排序或归并排序序。 快速排序: 查看详情
数据结构八大排序(超详解+附动图+源码)(代码片段)
目录前言常见排序算法的实现1.插入排序2.希尔排序3.选择排序4.堆排序5.冒泡排序6.快速排序6.1hoare版本6.2挖坑法6.3前后指针法6.4快速排序优化6.5快速排序非递归实现7.归并排序7.1递归实现7.2非递归实现8.计数排序(了解)排序算法复... 查看详情
多个岗位需要的sql语言你掌握了吗?简单例子+详细代码带你一文掌握(代码片段)
数据库以及sql入门知识基础版:多个岗位需要的sql语言你掌握了吗?简单例子+详细代码带你一文掌握带你熟练掌握–进阶版:什么样的程度才是“熟练掌握sql”–MySQL进阶版简单例子+详细代码带你一文掌握关于... 查看详情
八大排序算法总结:快速排序(代码片段)
目的:掌握快速排序 的 基本思想与过程、代码实现、时间复杂度1、基本思想与过程:(分治思想,挖坑填数) (1)从数列中选择一个数作为key值; (2)将比这个数小的数全部放在它的左边,大于或等于它的数... 查看详情
如何快速掌握mysql?附leetcode上出现频率最高的50道数据库题目详解(代码片段)
...且过程中不会什么补什么,就是巩固和提升自己的SQL语言能力最快捷的方法。LeetCode中有不少题是需要Plus会员才能查看并答题的& 查看详情
英雄哪里出来一文带你吃透算法(代码片段)
...算法入门1、「算法零基础100讲」五、算法进阶1、「画解数据结构」2、「算法进阶50讲」3、「LeetCode算法题集汇总」4、「夜深人静写算法」六、「三年之约」七、配套赠送福利前言 很多人看到我的博客,太多专栏不知道... 查看详情
[八大排序]0基础c语言实现八大排序,详解快排,归并,希尔(代码片段)
八大排序前言一、冒泡排序1.复杂度,稳定性分析二、插入排序2.复杂度,稳定性分析三、选择排序3.复杂度,稳定性分析四、希尔排序(缩小增量排序)4.复杂度,稳定性分析五、快排1.1.hoare版本2.1挖坑法3... 查看详情
八大排序算法浅析
...的排序记录,在排序过程中需要访问外存。我们这里说说八大排序就是内部排序。 当n较大,则应采用时间复杂度为O(nlog2n)的排序方法:快速排序、堆排序或归并排序序。快速排序:是目前基于比较的内部排序中被认为是最... 查看详情
❤️c语言文件的操作与处理❤️----1.6w字详解,带你搞懂文件操作!!!(代码片段)
⭐️前面的话⭐️🔵🔵🔵大家好!本篇博客是为了后续做出文件版本的通讯录做准备的。之前博主虽然对简易版通讯录进行了修改,使他可以动态开辟内存,但是只要一关闭,数据就会丢失,如... 查看详情
八大排序算法
...的排序记录,在排序过程中需要访问外存。我们这里说说八大排序就是内部排序。 当n较大,则应采用时间复杂度为O(nlog2n)的排序方法:快速排序、堆排序或归并排序序。 快速排 查看详情
八大排序算法(java实现)
...全部的排序记录,在排序过程中需要访问外存。我整理的八大排序就是内部排序。当数据较多时应该采用时间复杂度为o(nlog2n)的排序方法:快速排序、堆排序、归并排序快速排序是这几种内部排序中最好的方法,想待排序的关键... 查看详情
二万字《算法和数据结构》三张动图,三十张彩图,c语言基础教学,之二叉搜索树详解(建议收藏)
本文已收录于专栏🌳《画解数据结构》🌳前言 我们知道,「顺序表」可以「快速索引」数据,而「链表」则可以快速的进行数据的「插入和删除」。那么,有没有一种数据结构,可以快速的实现「增... 查看详情