【八大排序(十)】八大排序效率与稳定性分析

这篇具有很好参考价值的文章主要介绍了【八大排序(十)】八大排序效率与稳定性分析。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

💓博主CSDN主页:杭电码农-NEO💓

⏩专栏分类:八大排序专栏⏪

🚚代码仓库:NEO的学习日记🚚

🌹关注我🫵带你学习排序知识
  🔝🔝


【八大排序(十)】八大排序效率与稳定性分析


1. 前言

比较八大排序不能直接将
这八个排序放在一起讨论
我们根据大致效率将它们分为两组:
(每个排序的详情链接在后面)

1. 第一组

  • 插入排序 详情
  • 选择排序 详情
  • 冒泡排序 (略)

2. 第二组

  • 堆排序 详情
  • 希尔排序 详情
  • 快速排序 详情
  • 归并排序 详情

【八大排序(十)】八大排序效率与稳定性分析

各大排序的进阶版本被放在了专栏:
    八大排序专栏

本篇文章将从稳定性和效率两个方面
来分析这两组排序


2. 什么是排序算法的稳定性?

官方话语是这样的:

排序序列中,有多个具有相同关键字的记录经过排序,记录对应的相对次序保持不变,这就是排序的稳定性。

举个例子,定义一个无序数组:

int a[]={5(i),3,6,4,5(j),2,8};

数组中有两个5
把第一个5记为 i
第二个5记为 j
当我们用任意算法排好序后

int a[]={2,3,4,5,5,6,8};//排好序后的数组

若 i 还在 j 前面,则这个算法是稳定的

int a[]={2,3,4,i,j,6,8};

若 i 在 j 后面,则算法不稳定

int a[]={2,3,4,j,i,6,8};

3. 各大排序稳定性分析

想要搞清楚排序是否稳定
就要明白内部的实现思路!


3.1 插入和希尔排序的分析

1. 插入排序:

插入排序是从数组中第一个元素开始
一一和它后面的元素做比较
并且一个元素向前挪动停下来的条件是:
当前元素的值大于等于正在挪动的元素

结论: 是稳定的

2. 希尔排序:

虽然希尔排序是对插入排序的优化
但是希尔排序多了一个分组预排序
当相同的数组被分到同一组时
它们的顺序不会变化
但是当相同的数据分到不同组时
排好序后的顺序就有可能改变!

结论: 不是稳定的


3.2 选择,堆排序的分析

1. 选择排序:

选择排序明显是不稳定的
当前循环选出的最大值是
这个值第一次出现的位置
将它放在数组最后,第二层循环
寻找次大值时若和刚刚的值相同
这个次打值就到倒数第二个位置了

结论: 不稳定的

2. 堆排序:

堆排序和选择排序类似
我们直接举个向下调整的例子:

【八大排序(十)】八大排序效率与稳定性分析

蓝色的5从第一个位置跑到最后一个了

结论: 不稳定的


3.3 冒泡,快速排序的分析

1. 冒泡排序:

冒泡排序是挨个儿比较
挨个儿交换.所以不会将相同的值
交换到不同的位置

结论: 稳定的

2. 快速排序

快速排序比较特殊.
当基准值key和L,R指针相遇的点
对应的值相同时,会改变位置!
画图说明:

【八大排序(十)】八大排序效率与稳定性分析

5的前后顺序发生了变化

结论: 不稳定的


3.4 归并排序分析

归并排序可以稳定也可以不稳定
当左右子数组中出现相同值时
如果先将左子数组的数据入数组
那么归并排序就是稳定的
如果先将右子数组的数据入数组
那么归并排序就是不稳定的

所以我们写归并排序时
数据相同时尽量先下左边

结论: 稳定的!


4. 各大算法效率比较

现实生活中处理的信息量往往非常大
这里我们随机生成五百万个数排序
试一试每一个排序算法要花多少毫秒?

注:clock是记录程序
走到当前这一行运行的时长
两个clock相减就是中间程序运行的时间

//测试性能
void TestOP()
{
	srand(time(0));
	const int N = 5000000;
	int* a1 = (int*)malloc(sizeof(int) * N);
	int* a2 = (int*)malloc(sizeof(int) * N);
	int* a3 = (int*)malloc(sizeof(int) * N);
	int* a4 = (int*)malloc(sizeof(int) * N);
	int* a5 = (int*)malloc(sizeof(int) * N);
	int* a6 = (int*)malloc(sizeof(int) * N);
	int* a7 = (int*)malloc(sizeof(int) * N);

	for (int i = 0; i < N; ++i)
	{
		a1[i] = rand();
		a2[i] = a1[i];
		a3[i] = a1[i];
		a4[i] = a1[i];
		a5[i] = a1[i];
		a6[i] = a1[i];
	}

	int begin1 = clock();
	InsertSort(a2, N);
	int end1 = clock();

	int begin2 = clock();
	ShellSort(a2, N);
	int end2 = clock();

	int begin3 = clock();
	SelectSort(a3, N);
	int end3 = clock();

	int begin4 = clock();
	HeapSort(a2, N);
	int end4 = clock();

	int begin5 = clock();
	QuickSort(a2, 0, N - 1);
	QuickSort(a2, 0, N - 1);
	int end5 = clock();

	int begin6 = clock();
	MergeSort(a2, N);
	int end6 = clock();

	printf("InsertSort:%d ms\n", end1 - begin1);
	printf("ShellSort:%d ms\n", end2 - begin2);
	printf("SelectSort:%d ms\n", end3 - begin3);
	printf("HeapSort:%d ms\n", end4 - begin4);
	printf("QuickSort:%d ms\n", end5 - begin5);
	printf("MergeSort:%d ms\n", end6 - begin6);

	free(a1);
	free(a2);
	free(a3);
	free(a4);
	free(a5);
	free(a6);
}

对于五百万个数据来说
插入,选择,冒泡排序运行的时间会很长
所以我们这里直接比较第二组排序
:

五百万个数据:

【八大排序(十)】八大排序效率与稳定性分析

一百万个数据:
【八大排序(十)】八大排序效率与稳定性分析

每个排序效率都不错
快排与归并格外的好!


5. 总结与代码分享

八大排序整体完结!
下面分享一个知识表格大全:

排序方法 最好情况 最坏情况 辅助空间 稳定性
冒泡排序 O(N) O(N2) O(1) 稳定
选择排序 O(N2 O(N2 O(1) 不稳定
插入排序 O(N) O(N2 O(1) 稳定
希尔排序 O(N1.3) O(N2) O(1) 不稳定
堆排序 O(N*log2N) O(N*log2N) O(N) 不稳定
快速排序 O(N*log2N) O(N2) O(log2N~N) 不稳定
归并排序 O(N*log2N) O(N*log2N) O(N) 稳定

我将C语言实现八大排序
所有代码汇总分享给大家:

gitee代码仓库

八大排序所有内容结束!
【八大排序(十)】八大排序效率与稳定性分析文章来源地址https://www.toymoban.com/news/detail-502770.html

🔎 下期预告:C嘎嘎初阶 🔍

到了这里,关于【八大排序(十)】八大排序效率与稳定性分析的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • Lyapunov稳定性分析1(正定函数、二次型正定判定)

    1.1 定义: 令 V ( x )是向量 x 的 标量函数 , S 是x空间包含原点的封闭有限区域。如果对于 S 中的所有 x ,都有: 则 V ( x )是 正定的 (半正定)。正定函数更直观的描述如下图所示: 如果条件(3)中不等式的符号 反向 ,则称V(x)是 负定的 (负半定的)。 如果在S域内,不论

    2024年02月16日
    浏览(45)
  • 毕业设计-基于 Matlab 的电力系统稳定性分析与仿真

    目录 前言 课题背景和意义 实现技术思路 一、简单电力系统仿真软件简介 二、电力系统稳定性仿真分析 三、结论 实现效果图样例 最后     📅大四是整个大学期间最忙碌的时光,一边要忙着备考或实习为毕业后面临的就业升学做准备,一边要为毕业设计耗费大量精力。近几年

    2024年02月02日
    浏览(170)
  • 基于STATCOM的风力发电机稳定性问题仿真分析(Simulink)

    💥💥💞💞 欢迎来到本博客 ❤️❤️💥💥 🏆博主优势: 🌞🌞🌞 博客内容尽量做到思维缜密,逻辑清晰,为了方便读者。 ⛳️ 座右铭: 行百里者,半于九十。 📋📋📋 本文目录如下: 🎁🎁🎁 目录 💥1 概述 📚2 运行结果 🎉3 参考文献 🌈4 Matlab代码实现 ​ STAT

    2024年02月02日
    浏览(53)
  • TI 高精度实验室《运算放大器系列--稳定性分析》

    TI 高精度实验室《运算放大器系列–稳定性分析》 一个不稳定的运放电路将会得到失真的瞬态响应,输出波形不是预期的结果。当输入或者负载变化时,这就会引起输出较大的过冲和失调,甚至导致持续的振荡波形。 通常稳定性问题源于在运放输出或者反相输入端连接了电

    2024年02月04日
    浏览(53)
  • 模拟电路设计(12)--- 运算放大器闭环增益计算及放大器电路稳定性分析

    闭环增益计算 运算放大器深度负反馈状态,放大电路的增益为1/F(s)。而在实际应用中很少去计算F(s),一般通过深度负反馈时的“虚短”、“虚断”概念去计算。深度负反馈时,1+A(s)F(s) 1,则A(s)F(s) = Xf(s)/X’i(s) 1,而Xi(s)=X’i(s)+Xf(s),那么X’i(s)可以忽略不计,Xi(s)=Xf(s)。 对于

    2024年02月16日
    浏览(54)
  • 振弦传感器和在线监测系统保障岩土工程项目稳定性:案例分析

    振弦传感器和在线监测系统保障岩土工程项目稳定性:案例分析 以下是一个振弦传感器和振弦采集仪及在线监测系统形成一套完整链条的岩土工程监测案例: 项目背景:一家建设公司在中国某地进行了一项岩土工程项目,该项目涉及到一座桥梁的建设。建设公司决定使用振

    2024年02月15日
    浏览(59)
  • 现控报告-- 分析倒立摆系统稳定性、能控性及能观性分析,设计PID控制方案(附matlab)

    目录 摘要 数学建模 1、 倒立摆系统简介         2、 直线倒立摆系统数学模型 系统传递函数模型  系统状态空间数学模型  系统分析 3、 直线一级倒立摆系统分析 (1)系统稳定性分析  (2)系统能控性和能观性分析 仿真 4、 直线倒立摆系统PID控制与仿真  (1)PID控制

    2024年02月07日
    浏览(76)
  • 【ARM Linux 系统稳定性分析入门及渐进12 -- GDB内存查看命令 “x“(examine)】

    请阅读 【ARM Linux 系统稳定性分析专栏导读】 上篇文章:ARM Linux 系统稳定性分析入门及渐进11 – GDB( print 和 p 的使用| @ 和 ::的使用|ptype|{<type>} <addr> ) examine 是GDB中x命令的全称,用于检查内存中的内容。这个命令非常强大,可以以多种格式显示内存内容。 examine 命令

    2024年02月12日
    浏览(37)
  • ARM Linux 系统稳定性分析入门及渐进 13 -- gdb 反汇编 disassemble 命令详细介绍及举例】

    请阅读 【ARM Linux 系统稳定性分析专栏导读】 在GNU调试器(GDB)中,有许多命令可以帮助我们调试应用程序。 gdb : 这是一个强大的Unix下的程序调试工具。以下是使用gdb的一个简单示例: 在这个例子中,我们启动了 gdb 并将我们的程序 test 作为参数传递。 可执行程序 test 是由

    2024年02月11日
    浏览(57)
  • 八大排序算法(含时间复杂度、空间复杂度、算法稳定性)

    下列算法默认都是对数组进行升序 1.1、算法思想 插入排序是一种简单直观的排序算法,它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。 插入排序的具体步骤如下: 从第一个元素开始,该元素可以认为已经被排序;

    2024年02月08日
    浏览(47)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包