【C语言/数据结构】排序(选择排序,推排序,冒泡排序)

简介: 【C语言/数据结构】排序(选择排序,推排序,冒泡排序)

选择排序


选择排序

过程图如下:



代码呈现

//时间复杂度:O(N^2)
//最好情况下:O(N^2)
void SelectSort(int* a, int n)
{
  int begin = 0, end = n - 1;
  while (begin < end)
  {
  int mini = begin, maxi = begin;
  for (int i = begin + 1; i <= end; i++)
  {
    if (a[i] < a[mini])
    {
    mini = i;
    }
    if (a[i] > a[maxi])
    {
    maxi = i;
    }
  }
  Swap(&a[begin], &a[mini]);
  //当max在begin的位置时
  if (maxi == begin)
  {
    maxi = mini;
  }
  Swap(&a[end], &a[maxi]);
  begin++;
  end--;
  }
}


分析:开始时,begin指向首元素,end是末尾元素下标。这里的选择排序与上图过程略有差异,这里的选择排序每次选出最大和最小值,分别与头和尾交换。然后begin++和end--来缩小选择的范围。需注意,在同时选最大和最小时,要判断max是否在begin的位置上,如果是,就要把maxi改为mini的值。


堆排序


代码呈现

void AdjustDown(int* a, int size, int parent)
{
  int child = parent * 2 + 1;
  while (child < size)
  {
  //假设左孩子小,如果假设错了,就更新一下
  if (child + 1 < size && 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)
{
  //建大堆
  //O(N)
  for (int i = (n - 1 - 1) / 2; i >= 0; i--)
  {
  AdjustDown(a, n, i);
  }
  //O(N*logN)
  int end = n - 1;
  while (end > 0)
  {
  Swap(&a[0], &a[end]);
  AdjustDown(a, end, 0);
  end--;
  }
}


堆排序在前面的文章中已经讲解,这里不再介绍。


交换排序

冒泡排序


//时间复杂度:O(N^2)
//最好情况:O(N);
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])
    {
    Swap(&a[i - 1], &a[i]);
    exchange = true;
    }
  }
  if (exchange == false)
    break;
  }
}


分析:这里简单说下时间复杂度最好情况:O(N)。在第一次外层for循环时,如果内层循环结束后,exchange的值还是false,就说明已经是排序好了的,就可以break掉循环,这时就遍历了一次,时间复杂度就是O(N)。


目录
相关文章
|
29天前
|
算法 数据处理 C语言
C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合
本文深入解析了C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合,旨在帮助读者掌握这一高效的数据处理方法。
45 1
|
1月前
|
存储 算法 搜索推荐
【趣学C语言和数据结构100例】91-95
本文涵盖多个经典算法问题的C语言实现,包括堆排序、归并排序、从长整型变量中提取偶数位数、工人信息排序及无向图是否为树的判断。通过这些问题,读者可以深入了解排序算法、数据处理方法和图论基础知识,提升编程能力和算法理解。
50 4
|
1月前
|
存储 机器学习/深度学习 搜索推荐
【趣学C语言和数据结构100例】86-90
本文介绍并用C语言实现了五种经典排序算法:直接插入排序、折半插入排序、冒泡排序、快速排序和简单选择排序。每种算法都有其特点和适用场景,如直接插入排序适合小规模或基本有序的数据,快速排序则适用于大规模数据集,具有较高的效率。通过学习这些算法,读者可以加深对数据结构和算法设计的理解,提升解决实际问题的能力。
45 4
|
1月前
|
存储 算法 数据处理
【趣学C语言和数据结构100例】81-85
本文介绍了五个经典算法问题及其C语言实现,涵盖图论与树结构的基础知识。包括使用BFS求解单源最短路径、统计有向图中入度或出度为0的点数、统计无向无权图各顶点的度、折半查找及二叉排序树的查找。这些算法不仅理论意义重大,且在实际应用中极为广泛,有助于提升编程能力和数据结构理解。
46 4
|
1月前
|
算法 数据可视化 数据建模
【趣学C语言和数据结构100例】76-80
本文介绍了五种图论算法的C语言实现,涵盖二叉树的层次遍历及广度优先搜索(BFS)和深度优先搜索(DFS)的邻接表与邻接矩阵实现。层次遍历使用队列按层访问二叉树节点;BFS利用队列从源节点逐层遍历图节点,适用于最短路径等问题;DFS通过递归或栈深入图的分支,适合拓扑排序等场景。这些算法是数据结构和算法学习的基础,对提升编程能力和解决实际问题至关重要。
53 4
|
1月前
|
存储 算法 vr&ar
【趣学C语言和数据结构100例】71-75
本文介绍了五个C语言数据结构问题及其实现,涵盖链表与二叉树操作,包括按奇偶分解链表、交换二叉树左右子树、查找节点的双亲节点、计算二叉树深度及求最大关键值。通过递归和遍历等方法,解决了理论与实际应用中的常见问题,有助于提升编程能力和数据结构理解。
43 4
|
1月前
|
存储 算法 C语言
【趣学C语言和数据结构100例】66-70
本书《趣学C语言和数据结构100例》精选了5个典型的数据结构问题及C语言实现,涵盖链表与数组操作,如有序集合的集合运算、有序序列表的合并、数组中两顺序表位置互换、三递增序列公共元素查找及奇偶数重排。通过详细解析与代码示例,帮助读者深入理解数据结构与算法设计的核心思想,提升编程技能。
36 4
|
1月前
|
存储 缓存 算法
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
55 5
|
29天前
|
并行计算 算法 测试技术
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面,旨在通过综合策略提升程序性能,满足实际需求。
62 1
|
1月前
|
存储 机器学习/深度学习 算法
【趣学C语言和数据结构100例】61-65
本文介绍了五个关于C语言和数据结构的经典问题及其实现方法,涵盖查找链表共同后缀、删除重复节点、重新排列链表元素、合并有序链表以及特定条件下的链表排序。每个问题通过具体的算法设计,不仅展示了链表操作的灵活性,还强调了效率优化的重要性。通过这些问题的探讨,读者可以深入理解链表的基本操作和高级应用,提升解决实际问题的能力。
54 4