【数据结构】初步了解排序

简介: 【数据结构】初步了解排序

1.排序的概念及其运用

       1.1排序的概念

       

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

列起来的操作。


稳定性:假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这

些记录的相对次序保持不变,即在原序列中,r[i]=r[j],且r[i]在r[j]之前,而在排序后的序列中,r[i]仍

在r[j]之前,则称这种排 序算法是稳定的;否则称为不稳定的。

 内部排序:数据元素全部放在内存中的排序。

       

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

数据的排序。


2.常见排序算法的实现

       

       2.1插入排序

                       思路:



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


               其实和摸牌的过程是一样的,两个变量之间进行比较,调换位置,根据循环,不断的进


行比较,升序情况下:如果前面一个变量的大于后一个变量,则直接进行交换位置,再和前面的位


置进行比较,知道位置到-1,则不再进行比较


 4be407354f9e40f7be36733bf136a027.png


代码实现:

                       

                             

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. 稳定性:稳定


2.2希尔排序

           

概念:

                       

希尔排序法又称缩小增量法。希尔排序法的基本思想是:先选定一个整数,把待排序文


件中所有记录分成个组,所有距离为的记录分在同一组内,并对每一组内的记录进行排序。


然后,取,重复上述分组和排序的工作。当到达=1时,所有记录在统一组内排好序。


思路:

   

以gap距离大小为一组进行比较,我们对其进行排序,之后不断缩小,gap的距离


再次进行排序,随着gap的减小,最后gap缩短为1,排序即可完成


e0bc9c272b554b2d90dff47c0ce8d4ba.png

问题:gap是多少合适?

               gap越大,跳的越快,越不接近有序,但是排序的速度更快,gap越小跳的越慢,

但是越接近有序,实际当中其界定应该是变化的

       

       

void ShellSort(int* a, int n)
{
  int gap = n;
  while (gap > 1)
  {
    gap /= 2;
    for (int i = 0; i < n-gap; i++)
    {
      int end = i;
      int tmp = a[i+gap];
      while (end >= 0)
      {
        if ( tmp < a[end] )
        {
          a[end + gap] = a[end];
          end -= gap;
        }
        else
        {
          break;
        }
      }
      a[end + gap] = tmp;
    }
    PrintArry(a,n);
  }
}


希尔排序的特性总结:


1. 希尔排序是对直接插入排序的优化。


2. 当gap > 1时都是预排序,目的是让数组更接近于有序。当gap == 1时,数组已经接近有序的了,这样就会很快。这样整体而言,可以达到优化的效果。我们实现后可以进行性能测试的对比。


3. 希尔排序的时间复杂度不好计算,因为gap的取值方法很多,导致很难去计算,因此在好些树中给出的

目录
打赏
0
0
0
0
24
分享
相关文章
C 408—《数据结构》图、查找、排序专题考点(含解析)
408考研——《数据结构》图,查找和排序专题考点选择题汇总(含解析)。
69 29
【C++数据结构——内排序】二路归并排序(头歌实践教学平台习题)【合集】
本关任务是实现二路归并算法,即将两个有序数组合并为一个有序数组。主要内容包括: - **任务描述**:实现二路归并算法。 - **相关知识**: - 二路归并算法的基本概念。 - 算法步骤:通过比较两个有序数组的元素,依次将较小的元素放入新数组中。 - 代码示例(以 C++ 为例)。 - 时间复杂度为 O(m+n),空间复杂度为 O(m+n)。 - **测试说明**:平台会对你编写的代码进行测试,提供输入和输出示例。 - **通关代码**:提供了完整的 C++ 实现代码。 - **测试结果**:展示代码运行后的排序结果。 开始你的任务吧,祝你成功!
38 10
【C++数据结构——内排序】希尔排序(头歌实践教学平台习题)【合集】
本文介绍了希尔排序算法的实现及相关知识。主要内容包括: - **任务描述**:实现希尔排序算法。 - **相关知识**: - 排序算法基础概念,如稳定性。 - 插入排序的基本思想和步骤。 - 间隔序列(增量序列)的概念及其在希尔排序中的应用。 - 算法的时间复杂度和空间复杂度分析。 - 代码实现技巧,如循环嵌套和索引计算。 - **测试说明**:提供了测试输入和输出示例,帮助验证代码正确性。 - **我的通关代码**:给出了完整的C++代码实现。 - **测试结果**:展示了代码运行的测试结果。 通过这些内容,读者可以全面了解希尔排序的原理和实现方法。
60 10
|
1月前
|
【C++数据结构——内排序】快速排序(头歌实践教学平台习题)【合集】
快速排序是一种高效的排序算法,基于分治策略。它的主要思想是通过选择一个基准元素(pivot),将数组划分成两部分。一部分的元素都小于等于基准元素,另一部分的元素都大于等于基准元素。然后对这两部分分别进行排序,最终使整个数组有序。(第一行是元素个数,第二行是待排序的原始关键字数据。本关任务:实现快速排序算法。开始你的任务吧,祝你成功!
43 7
数据结构与算法学习十三:基数排序,以空间换时间的稳定式排序,速度很快。
基数排序是一种稳定的排序算法,通过将数字按位数切割并分配到不同的桶中,以空间换时间的方式实现快速排序,但占用内存较大,不适合含有负数的数组。
59 0
数据结构与算法学习十三:基数排序,以空间换时间的稳定式排序,速度很快。
【用Java学习数据结构系列】七大排序要悄咪咪的学(直接插入,希尔,归并,选择,堆排,冒泡,快排)以及计数排序(非比较排序)
【用Java学习数据结构系列】七大排序要悄咪咪的学(直接插入,希尔,归并,选择,堆排,冒泡,快排)以及计数排序(非比较排序)
44 1
【初阶数据结构】深度解析七大常见排序|掌握底层逻辑与原理(二)
【初阶数据结构】深度解析七大常见排序|掌握底层逻辑与原理
【初阶数据结构】深度解析七大常见排序|掌握底层逻辑与原理(一)
【初阶数据结构】深度解析七大常见排序|掌握底层逻辑与原理
蓝桥杯宝藏排序 | 数据结构 | 快速排序 归并排序
蓝桥杯宝藏排序 | 数据结构 | 快速排序 归并排序
05_用一个栈实现另一个栈的排序
05_用一个栈实现另一个栈的排序
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等