数据结构——排序算法(C语言)

简介: 数据结构——排序算法(C语言)

本篇将详细讲一下以下排序算法

  1. 直接插入排序
  2. 希尔排序
  3. 选择排序
  4. 快速排序
  5. 归并排序
  6. 计数排序


排序的概念

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

稳定性的概念

假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序保持不变。如一下例子,

5 2 3 4 5 9 8

经过排序,如果红5和蓝5的相对顺序不对,这就叫稳定,反之则不稳定。

直接插入排序

直接插入排序的思想:将待排序的记录按其关键码值的大小逐个插入到一个已经排好序的序列中,直到所有的序列为有序序列。

实际中,我们玩扑克牌时,就用到了这样的一个排序算法。


时间复杂度:

直接插入排序时一个稳定的排序,如果有相同的元素,它们的相对位置不会发生变化。它时间复杂度最好的情况下是O(N),当一个数插入到已经排好序的序列中,只需要比较一次就好了。

最坏情况:O(N^2) ,在完全逆序的情况下,要排升序。

希尔排序

希尔排序其实和插入排序很像,只不过希尔排序的思想是:先预排序,最后插入排序。

预排序的意义在哪里??

  • 大的数更快到后面去,小的数更快到前面去。gap越大跳的越快,越不有序,当gap =1 时就是插入排序。
  • 时间复杂度

希尔排序的时间复杂度:大约为O(N^1.3)

选择排序

选择排序的思想:选择排序可以在一次查找中找到最大的数和最小的数,然后把最大的数放到最后,最小的数放到最前面。

时间复杂度

时间复杂度是O(N^2)

稳定性:差



快速排序

快排思想:说到排序,或多或少都听过快速排序,快速排序是Hoare于1962年提出的一种二叉树结构的交换方法,其基本思想为:任取待排序元素序列中的某个元素作为基准值,按照该排序吗将待排序集合分割成2个子序列,左序列小于keyi值,右序列大于keyi值,然后重复此方法,最后拍完序。

快速排序一次可以确定一个值在正确的位置上。(这个值就是key值)

  if (begin >= end)
  {
    return;
  }
  int left = begin, right = end;
  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]);
  keyi = left;
  //[begin,keyi-1]  keyi [keyi+1,end]
  QuickSort(a,begin,keyi-1);
  QuickSort(a,keyi+1,end);

最常见的就是上面的递归代码,这是Hoare的一种方式实现快排。

Hoare思想:让基准值的右边先走,直到找到比基准值小的数,然后让左边走,直到找到比基准值大的数,然后交换,最后left=right相等的时候,将left位置的值与基准值交换。这样就实现了一次排序。


这里我们想一想快速排序为什么要让基准值的对面开始????


挖坑法: 用一个tmp记录第一个值的坑位,让右边先走,直到找到比坑位小的数,然后让a[right]赋值给坑位,然后把坑位给给right,继续让左边先走,直到找到比坑位大的数,然后把值赋给坑位,让坑位给给left,一直循环。


前后指针法:让prev指向key值,cur指向key值之后的一个值,当a[cur] < a[key] 的时候,就让prev++和cur交换,然后一直循环。

 

快排的非递归: 快排的思想其实不难发现像一个栈(后进先出),因为快排每次可以确定一个基准值的位置,所以,第一次push进left和right,让他们进行一次排序,就接着push进right和keyi+1,再push进keyi-1和left,注意顺序,因为快排的中间也是一个后进先出的思想。

快排的缺点

快排其实是有缺点的,因为快排的时间复杂度不一定是O(N*logN),如果排升序,给一个倒序的序列,就有可能达到O(N^2)。所以有了这么一个缺点,就可以做一个三数区中的优化,其实Sort函数中也有这样的处理,而且Sort中还优化了一次快排递归深度过深的时候会用堆排序,在接近有序的时候会用插入排序,而且Sort中只对了右边进行递归处理。如果有兴趣,可以去了解一下Sort的源码,里面有详细解释。


归并排序

归并排序:它是建立在归并操作上的一种有效的排序算法,该算法采用了分治的思想。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段有序。若将两个有序表合并成一个有序表,称为二路归并。        

归并排序可以看出是一个后序的排序, 先递归,然后从前面开始排好序,然后再memcpy到原数组。

归并排序其实用在解决磁盘外的外排序问题中,如果有下面的场景,归并排序就起到了很大的作用。

时间复杂度

归并排序也是一种经典的O(N*logN)  空间复杂度是O(N),这时因为开辟了一块tmp临时数组


计数排序

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

步骤:1.统计想相同元素出现的次数

2.根据统计的结果将序列回收到原来的序列中

 

计数排序的特性:

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


相关文章
|
3月前
|
存储 监控 安全
企业上网监控系统中红黑树数据结构的 Python 算法实现与应用研究
企业上网监控系统需高效处理海量数据,传统数据结构存在性能瓶颈。红黑树通过自平衡机制,确保查找、插入、删除操作的时间复杂度稳定在 O(log n),适用于网络记录存储、设备信息维护及安全事件排序等场景。本文分析红黑树的理论基础、应用场景及 Python 实现,并探讨其在企业监控系统中的实践价值,提升系统性能与稳定性。
78 1
|
3月前
|
存储 监控 算法
基于跳表数据结构的企业局域网监控异常连接实时检测 C++ 算法研究
跳表(Skip List)是一种基于概率的数据结构,适用于企业局域网监控中海量连接记录的高效处理。其通过多层索引机制实现快速查找、插入和删除操作,时间复杂度为 $O(\log n)$,优于链表和平衡树。跳表在异常连接识别、黑名单管理和历史记录溯源等场景中表现出色,具备实现简单、支持范围查询等优势,是企业网络监控中动态数据管理的理想选择。
91 0
|
11月前
|
算法 数据处理 C语言
C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合
本文深入解析了C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合,旨在帮助读者掌握这一高效的数据处理方法。
427 1
|
7月前
|
存储 算法 Java
算法系列之数据结构-二叉树
树是一种重要的非线性数据结构,广泛应用于各种算法和应用中。本文介绍了树的基本概念、常见类型(如二叉树、满二叉树、完全二叉树、平衡二叉树、B树等)及其在Java中的实现。通过递归方法实现了二叉树的前序、中序、后序和层次遍历,并展示了具体的代码示例和运行结果。掌握树结构有助于提高编程能力,优化算法设计。
200 10
 算法系列之数据结构-二叉树
|
7月前
|
算法 Java
算法系列之数据结构-Huffman树
Huffman树(哈夫曼树)又称最优二叉树,是一种带权路径长度最短的二叉树,常用于信息传输、数据压缩等方面。它的构造基于字符出现的频率,通过将频率较低的字符组合在一起,最终形成一棵树。在Huffman树中,每个叶节点代表一个字符,而每个字符的编码则是从根节点到叶节点的路径所对应的二进制序列。
160 3
 算法系列之数据结构-Huffman树
|
7月前
|
算法 Java
算法系列之数据结构-二叉搜索树
二叉查找树(Binary Search Tree,简称BST)是一种常用的数据结构,它能够高效地进行查找、插入和删除操作。二叉查找树的特点是,对于树中的每个节点,其左子树中的所有节点都小于该节点,而右子树中的所有节点都大于该节点。
215 22
|
8月前
|
存储 机器学习/深度学习 算法
C 408—《数据结构》算法题基础篇—链表(下)
408考研——《数据结构》算法题基础篇之链表(下)。
205 30
|
8月前
|
存储 算法 C语言
C 408—《数据结构》算法题基础篇—链表(上)
408考研——《数据结构》算法题基础篇之链表(上)。
330 25
|
8月前
|
存储 人工智能 算法
C 408—《数据结构》算法题基础篇—数组(通俗易懂)
408考研——《数据结构》算法题基础篇之数组。(408算法题的入门)
302 23
|
9月前
|
搜索推荐 C语言
数据结构(C语言)之对归并排序的介绍与理解
归并排序是一种基于分治策略的排序算法,通过递归将数组不断分割为子数组,直到每个子数组仅剩一个元素,再逐步合并这些有序的子数组以得到最终的有序数组。递归版本中,每次分割区间为[left, mid]和[mid+1, right],确保每两个区间内数据有序后进行合并。非递归版本则通过逐步增加gap值(初始为1),先对单个元素排序,再逐步扩大到更大的区间进行合并,直至整个数组有序。归并排序的时间复杂度为O(n*logn),空间复杂度为O(n),且具有稳定性,适用于普通排序及大文件排序场景。

热门文章

最新文章