数据结构之排序

一、排序的概念及其应用

1、排序的概念

排序:所谓排序,就是使一串记录,按照其中的某个或某些关键字的大小,递增或递减的排列起来的操作。

稳定性:假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中,r[i]=r[j],且r[i]在r[j]之前,而在排序后的序列中,r[i]仍在r[j]之前,则称这种排序算法是稳定的;否则称为不稳定的。


内部排序:数据元素全部放在内存中的排序。
外部排序:数据元素太多不能同时放在内存中,根据排序过程的要求不能在内外存之间移动数据的排序。

2、常见的排序算法

二、常见排序算法的实现

1、插入排序

1)基本思想:

直接插入排序是一种简单的插入排序法,其基本思想是:

把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中,直到所有的记录插入完为 止,得到一个新的有序序列 。

2)直接插入排序

        当插入第i(i>=1)个元素时,前面的array[0],array[1],…,array[i-1]已经排好序,此时用array[i]的排序码与 array[i-1],array[i-2],…的排序码顺序进行比较,找到插入位置即将array[i]插入,原来位置上的元素顺序后移

// 时间复杂度(最坏):O(N^2) -- 逆序
// 时间复杂度(最好):O(N) -- 顺序有序
void InsertSort(int* a, int n) {for (int i = 1; i < n; i++) {int end = i - 1;int tmp = a[i];while (end >= 0) {if (a[end] > tmp) {a[end + 1] = a[end];--end;} else {break;}}a[end + 1] = tmp;}
}

直接插入排序的特性总结:

  1. 元素集合越接近有序,直接插入排序算法的时间效率越高
  2. 时间复杂度:O(N^2)
  3. 空间复杂度:O(1),它是一种稳定的排序算法
  4. 稳定性:稳定

3)希尔排序(缩小增量)

        希尔排序法又称缩小增量法。希尔排序法的基本思想是:先选定一个整数,把待排序文件中所有记录分成个组,所有距离为的记录分在同一组内,并对每一组内的记录进行排序。然后,取,重复上述分组和排序的工作。当到达=1时,所有记录在统一组内排好序。

// O(N^1.3)
void ShellSort(int* a, int n) {// 1、gap>1  预排序// 2、gap==1  直接排序int gap = n;while (gap > 1) {// gap=gap/3+1;  +1可以保证最后一次一定是1gap = gap / 2;for (int i = 0; i < n - gap; i++) {int end = i;int tmp = a[end + gap];while (end >= 0) {if (a[end] > tmp) {a[end + gap] = a[end];end -= gap;} else {break;}}a[end + gap] = tmp;}}
}

希尔排序的特性总结:

  1. 希尔排序是对直接插入排序的优化。
  2. 当gap > 1时都是预排序,目的是让数组更接近于有序。当gap == 1时,数组已经接近有序的了,这样就会很快。这样整体而言,可以达到优化的效果。我们实现后可以进行性能测试的对比。
  3. 希尔排序的时间复杂度不好计算,因为gap的取值方法很多,导致很难去计算,因此在好些树中给出的希尔排序的时间复杂度都不固定:

        因为咱们的gap是按照Knuth提出的方式取值的,而且Knuth进行了大量的试验统计,我们暂时就按照:O(n^{125})O(1.6*n^{1.25})来算。

        4.稳定性:不稳定

2、选择排序

1)基本思想

每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的 数据元素排完 。

2)直接选择排序

  • 在元素集合array[i]--array[n-1]中选择关键码最大(小)的数据元素
  • 若它不是这组元素中的最后一个(第一个)元素,则将它与这组元素中的最后一个(第一个)元素交换
  • 在剩余的array[i]--array[n-2](array[i+1]--array[n-1])集合中,重复上述步骤,直到集合剩余1个元素
void SelectSort(int* a, int n) {int begin = 0, end = n - 1;while (begin < end) {int maxi = begin, mini = begin;for (int i = begin; i <= end; i++) {if (a[i] > a[maxi]) {maxi = i;}if (a[i] < a[mini]) {mini = i;}}Swap(&a[begin], &a[mini]);// 如果maxi和begin重叠,修正一下即可if (begin == maxi) {maxi = mini;}Swap(&a[end], &a[maxi]);++begin;--end;}
}

直接选择排序的特性总结:

  1. 直接选择排序思考非常好理解,但是效率不是很好。实际中很少使用
  2. 时间复杂度:O(N^2)
  3. 空间复杂度:O(1)
  4. 稳定性:不稳定

3)堆排序

堆排序(Heapsort)是指利用堆积树(堆)这种数据结构所设计的一种排序算法,它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆,排降序建小堆。

void AdjustDown(int* a, int n, int parent) {int child = parent * 2 + 1;while (child < n) {//找小的那个孩子if (child + 1 < n && a[child + 1] > a[child]) {++child;}if (a[child] > a[parent]) {Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;} else {break;}}
}//排升序
void HeapSort(int* a, int n) {for (int i = (n - 1 - 1) / 2; i >= 0; --i) {AdjustDown(a, n, i);}int end = n - 1;while (end > 0) {Swap(&a[0], &a[end]);AdjustDown(a, end, 0);--end;}
}

堆排序的特性总结:

  1. 堆排序使用堆来选数,效率就高了很多。
  2. 时间复杂度:O(N*logN)
  3. 空间复杂度:O(1)
  4. 稳定性:不稳定

3、交换排序

        基本思想:所谓交换,就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置,交换排序的特点是:将键值较大的记录向序列的尾部移动,键值较小的记录向序列的前部移动。

1)冒泡排序

void BubbleSort(int* a, int n) {for (int j = 0; j < n; ++j) {bool exchange = false;for (int i = 1; i < n - j; i++) {if (a[i - 1] > a[i]) {int tmp = a[i];a[i] = a[i - 1];a[i - 1] = tmp;exchange = true;}}if (exchange == false)break;}
}

冒泡排序的特性总结:

  1. 冒泡排序是一种非常容易理解的排序
  2. 时间复杂度:O(N^2)
  3. 空间复杂度:O(1)
  4. 稳定性:稳定

2)快速排序

        快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法,其基本思想为:任取待排序元素序列中的某元素作为基准值,按照该排序码将待排序集合分割成两子序列,左子序列中所有元素均小于基准值,右子序列中所有元素均大于基准值,然后最左右子序列重复该过程,直到所有元素都排列在相应位置上为止。

// 假设按照升序对array数组中[left, right)区间中的元素进行排序
void QuickSort(int array[], int left, int right) {if (right - left <= 1)return;// 按照基准值对array数组的 [left, right)区间中的元素进行划分int div = partion(array, left, right);// 划分成功后以div为边界形成了左右两部分 [left, div) 和 [div+1, right)// 递归排[left, div)QuickSort(array, left, div);// 递归排[div+1, right)QuickSort(array, div + 1, right);
}

上述为快速排序递归实现的主框架,发现与二叉树前序遍历规则非常像,同学们在写递归框架时可想想二叉 树前序遍历规则即可快速写出来,后序只需分析如何按照基准值来对区间中数据进行划分的方式即可。

将区间按照基准值划分为左右两半部分的常见方式有:

1. hoare版本

// 1、排序 hore
int PartSort(int* a, int left, int right) {int mid=GetMidIndex(a, left, right);Swap(&a[left],&a[mid]);int keyi = left;while (left < right) {//右边找小while (left < right && a[right] >= a[keyi]) {--right;}//左边找大while (left < right && a[left] <= a[keyi]) {++left;}Swap(&a[left], &a[right]);}Swap(&a[keyi], &a[left]);return left;
}

2.挖坑法

// 2、排序 挖坑法
//[left,right]
int PartSort2(int* a, int left, int right) {int mid=GetMidIndex(a, left, right);Swap(&a[left],&a[mid]);int key = a[left];int hole = left;while (left < right) {// 右边找小while (left < right && a[right] >= key) {--right;}a[hole] = a[right];hole = right;// 左边找大while (left < right && a[left] <= key) {++left;}a[hole] = a[left];hole = left;}a[hole] = key;return hole;
}

3.前后指针法

// 3、排序 前后指针法
int PartSort3(int* a, int left, int right) {int mid=GetMidIndex(a, left, right);Swap(&a[left],&a[mid]);int keyi = left;int prev = left;int cur = left + 1;while (cur <= right) {if (a[cur] < a[keyi] && ++prev != cur) {Swap(&a[cur], &a[prev]);}++cur;}Swap(&a[prev], &a[keyi]);keyi = prev;return keyi;
}

3)快速排序优化

  1. 三数取中法选key
  2. 递归到小的子区间时,可以考虑使用插入排序

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

4)快速排序非递归

void QuickSortNonR(int* a, int begin, int end) {ST st;STInit(&st);STPush(&st, end);STPush(&st, begin);while (!STEmpty(&st)){int left = STTop(&st);STPop(&st);int right = STTop(&st);STPop(&st);int keyi = PartSort3(a, left, right);if (keyi + 1 < right) {STPush(&st, right);STPush(&st, keyi + 1);}if (left < keyi - 1) {STPush(&st,keyi-1);STPush(&st, left);}}STDestroy(&st);
}

快速排序的特性总结:

  1. 快速排序整体的综合性能和使用场景都是比较好的,所以才敢叫快速排序
  2. 时间复杂度:O(N*logN)
  3. 空间复杂度:O(logN)
  4. 稳定性:不稳定

4、归并排序

基本思想:

        归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有 序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。 归并排序核心步骤:

//时间复杂度:O(logN* n)
//空间复杂度:O(N)
void _MergeSort(int* a, int begin, int end, int* tmp) { if (begin == end)return;int mid = (begin + end) / 2;//[begin, mid] [mid+1, end]_MergeSort(a, begin, mid, tmp);_MergeSort(a, mid + 1, end, tmp);int begin1 = begin, end1 = mid;int begin2 = mid+1, end2 = end;int i = begin;while (begin1<=end1&&begin2<=end2) {if (a[begin1] < a[begin2]) {tmp[i++] = a[begin1++];} else {tmp[i++] = a[begin2++];}}while (begin1 <= end1) {tmp[i++] = a[begin1++];}while (begin2 <= end2) {tmp[i++] = a[begin2++];}memcpy(a+begin, tmp+begin, sizeof(int) * (end - begin + 1));
}void MergeSort(int* a, int n) { int* tmp = (int*)malloc(sizeof(int) * n);_MergeSort(a, 0, n - 1, tmp);free(tmp);
}

归并排序的特性总结:

  1. 归并的缺点在于需要O(N)的空间复杂度,归并排序的思考更多的是解决在磁盘中的外排序问题。
  2. 时间复杂度:O(N*logN)
  3. 空间复杂度:O(N)
  4. 稳定性:稳定

5、非比较排序

思想:

        计数排序又称为鸽巢原理,是对哈希直接定址法的变形应用。

操作步骤:

  1. 统计相同元素出现次数
  2. 根据统计的结果将序列回收到原来的序列中

计数排序的特性总结:

  1. 计数排序在数据范围集中时,效率很高,但是适用范围及场景有限。
  2. 时间复杂度:O(MAX(N,范围))
  3. 空间复杂度:O(范围)
  4. 稳定性:稳定

三、排序算法复杂度及稳定性

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

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

相关文章

宝塔面板Docker+Uwsgi+Nginx+SSL部署Django项目

这次为大家带来的是从零开始搭建一个django项目并将它部署到linux服务器上。大家可以按照我的步骤一步步操作&#xff0c;最终可以完成部署。 步骤1&#xff1a;在某个文件夹中创建一个django项目 安装django pip install django创建一个django项目将其命名为djangoProject …

计算机网络 实验指导 实验17

实验17 配置无线网络实验 1.实验拓扑图 Table PC0 和 Table PC1 最开始可能还会连Access Point0&#xff0c;无影响后面会改 名称接口IP地址网关地址Router0fa0/0210.10.10.1fa0/1220.10.10.2Tablet PC0210.10.10.11Tablet PC1210.10.10.12Wireless互联网220.10.10.2LAN192.16…

05.MySQL索引事务

1. 索引 1.1 概念 索引是一种特殊的文件&#xff0c;包含着对数据表里所有记录的引用指针。 可以对表中的一列或多列创建索引&#xff0c;并指定索引的类型&#xff0c;各类索引有各自的数据结构实现 1.2 作用 数据库中的表、数据、索引之间的关系&#xff0c;类似于书架上的…

分布式ID的方案和架构

超过并发&#xff0c;超高性能分布式ID生成系统的要求 在复杂的超高并发、分布式系统中&#xff0c;往往需要对大量的数据和消息进行唯一标识如在高并发、分布式的金融、支付、餐饮、酒店、电影等产品的系统中&#xff0c;数据日渐增长&#xff0c;对数据分库分表后需要有一个唯…

LeetCode-31-下一个排列问题

题目说明 实现获取下一个排列的函数&#xff0c;算法需要将给定数字序列重新排列成字典序中下一个更大的排列。 如果不存在下一个更大的排列&#xff0c;则将数字重新排列成最小的排列&#xff08;即升序排列&#xff09;。 必须原地修改&#xff0c;只允许使用额外常数空间。…

数据结构与算法——20.B-树

这篇文章我们来讲解一下数据结构中非常重要的B-树。 目录 1.B树的相关介绍 1.1、B树的介绍 1.2、B树的特点 2.B树的节点类 3.小结 1.B树的相关介绍 1.1、B树的介绍 在介绍B树之前&#xff0c;我们回顾一下我们学的树。 首先是二叉树&#xff0c;这个不用多说&#xff…

网络篇09 | 运输层 udp

网络篇09 | 运输层 udp 01 简介UDP 是面向报文的 02 报文协议 01 简介 UDP 只在 IP 的数据报服务之上增加了一些功能&#xff1a;复用和分用、差错检测 UDP 的主要特点&#xff1a;无连接。发送数据之前不需要建立连接。 使用尽最大努力交付。即不保证可靠交付。 面向报文。…

eclipse 取消生成注释 TODO Auto-generated method stub

eclipse 取消生成注释 // TODO Auto-generated method stub 基本步骤 windows -> preferencesJava -> Code Style -> Code TemplatesCode -> Method body -> 编辑删除 // ${todo} Auto-generated method stub参考材料 Eclipse 中取消生成 TODO Auto-generated…

(四)C++自制植物大战僵尸游戏启动流程

植物大战僵尸游戏开发教程专栏地址http://t.csdnimg.cn/ErelL 一、启动方式 鼠标左键单机VS2022上方工具栏中绿色三角按钮&#xff08;本地Windows调试器&#xff09;进行项目启动。第一次启动项目需要编译项目中所有代码文件&#xff0c;编译生成需要一定的时间。不同性能的电…

Qt快速入门(Opencv小案例之人脸识别)

Qt快速入门&#xff08;Opencv小案例之人脸识别&#xff09; 编译出错记录 背景 因为主要使用qt&#xff0c;并且官网下载的win版本的编译好的opencv默认是vc的&#xff0c;所以我们需要自己下载opencv的源码使用mingw自行编译&#xff0c;我直接使用的vscode。 报错 报错…

Rust取代C++? 保守了!关于未来的讨论

当各种平台在大肆讨论rust即将取代C/C的时候&#xff0c;已经有不少人意识到这种讨论是聒噪而无聊的。笔者和老师们通过周末茶会的讨论&#xff0c;认为现今世界常见的大多数编程语言都会在50-80年内被AI取代&#xff0c;同时供人类审计而诞生的“审计语言”会兴起。届时计算机…

Niobe开发板OpenHarmony内核编程开发——事件标志

本示例将演示如何在Niobe Wifi IoT开发板上使用cmsis 2.0 接口使用事件标志同步线程 EventFlags API分析 osEventFlagsNew() /// Create and Initialize an Event Flags object./// \param[in] attr event flags attributes; NULL: default values./// \return e…

【C++】详解类的--封装思想(让你丝滑的从C语言过度到C++!!)

目录 一、前言 二、【面向过程】 与 【面向对象】 三、结构体 与 类 &#x1f34e;C中结构体的变化 &#x1f349;C中结构体的具体使用 &#x1f350;结构体 --> 类 ✨类-----语法格式&#xff1a; ✨类的两种定义方式&#xff1a; 四、类的访问限定符及封装【⭐】 …

【opencv】示例-stiching_detailed.cpp 使用OpenCV进行图像拼接的整体流程

#include <iostream> // 引入输入输出流库 #include <fstream> // 引入文件流库&#xff0c;用于文件输入输出 #include <string> // 引入字符串库 #include "opencv2/opencv_modules.hpp" // 引入OpenCV模块 #include <opencv2/core/utility.h…

数据结构-堆详解

堆 图片&#xff1a; 二叉堆的父节点为这个子树的最值。 如何维护它。 我们发现它是一棵二叉树&#xff0c;那就自然满足若父节点为 x x x 则左儿子节点为 x 2 x\times2 x2 右儿子为 x 2 1 x\times 2 1 x21 这是显然的&#xff0c;但如果写成指针或结构体就太麻烦了&…

王道汽车4S企业管理系统 SQL注入漏洞复现

0x01 产品简介 王道汽车4S企业管理系统(以下简称“王道4S系统”)是一套专门为汽车销售和维修服务企业开发的管理软件。该系统是博士德软件公司集10余年汽车行业管理软件研发经验之大成,精心打造的最新一代汽车4S企业管理解决方案。 0x02 漏洞概述 王道汽车4S企业管理系统…

MySQL优化慢SQL的6种方式

⛰️个人主页: 蒾酒 &#x1f525;系列专栏&#xff1a;《mysql经验总结》 &#x1f30a;山高路远&#xff0c;行路漫漫&#xff0c;终有归途 目录 写在前面 优化思路 优化方法 1.避免查询不必要的列 2.分页优化 3.索引优化 4.JOIN优化 5.排序优化 6.UNION 优化…

redis的设计与实现(五)——独立功能

1. Redis的其他功能 redis 除了简单对对象的增删改查的功能之外&#xff0c;其实还有其他高级功能&#xff0c;了解这些内容有利于我们更灵活的使用 redis 完成我们的业务功能。 2. 发布与订阅 2.1. 基本概念 很多中间件都有发布与订阅功能&#xff0c;但是&#xff0c;作为一…

软件无线电安全之GNU Radio基础 -上

GNU Radio介绍 GNU Radio是一款开源的软件工具集&#xff0c;专注于软件定义无线电&#xff08;SDR&#xff09;系统的设计和实现。该工具集支持多种SDR硬件平台&#xff0c;包括USRP、HackRF One和RTL-SDR等。用户可以通过GNU Radio Companion构建流程图&#xff0c;使用不同…

idea运行Tomcat,控制台日志的中文乱码

一 版本 win10&#xff0c;idea2022,jdk18,tomcat9 二 问题描述 在idea上可以运行Tomcat。服务器启动后&#xff0c;可以正常访问本地的html文件。但是控制台的Tomcat日志出现了乱码&#xff1a;server与Tomcat Catlina Log两处。 三 无效的解决之道 1 idea的Help选项Edit …