【初阶数据结构】深度解析七大常见排序|掌握底层逻辑与原理(一)

简介: 【初阶数据结构】深度解析七大常见排序|掌握底层逻辑与原理

一、排序的概念及其运用

1.1 排序的概念

排序是指使用一串记录,按照其中或某些关键字的大小,递增或递减的排序起来的操作(记录是指待排序的具体数据项)。

其中关于排序可以划分为

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

1.2 排序的稳定性

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

1.3 排序的运用


二、常见的排序算法

2.1 排序实现的接口

#pragma once
#include <time.h>
#include<stdlib.h>
#include <stdio.h>
// 排序实现的接口
// 插入排序
void InsertSort(int* a, int n);
// 希尔排序
void ShellSort(int* a, int n);
// 选择排序
void SelectSort(int* a, int n);
// 堆排序
void AdjustDwon(int* a, int n, int root);
void HeapSort(int* a, int n);
// 冒泡排序
void BubbleSort(int* a, int n)
// 快速排序递归实现
// 快速排序hoare版本
int PartSort1(int* a, int left, int right);
// 快速排序挖坑法
int PartSort2(int* a, int left, int right);
// 快速排序前后指针法
int PartSort3(int* a, int left, int right);
void QuickSort(int* a, int left, int right);
// 快速排序 非递归实现
void QuickSortNonR(int* a, int left, int right)
// 归并排序递归实现
void MergeSort(int* a, int n)
// 归并排序非递归实现
void MergeSortNonR(int* a, int n)
// 计数排序
void CountSort(int* a, int n)
// 测试排序的性能对比
void TestOP()
{
    srand(time(0));
    const int N = 100000;
    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);
    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(a1, 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(a4, N);
    int end4 = clock();
    int begin5 = clock();
    QuickSort(a5, 0, N - 1);
    int end5 = clock();
    int begin6 = clock();
    MergeSort(a6, N);
    int end6 = clock();
    printf("InsertSort:%d\n", end1 - begin1);
    printf("ShellSort:%d\n", end2 - begin2);
    printf("SelectSort:%d\n", end3 - begin3);
    printf("HeapSort:%d\n", end4 - begin4);
    printf("QuickSort:%d\n", end5 - begin5);
    printf("MergeSort:%d\n", end6 - begin6);
    free(a1);
    free(a2);
    free(a3);
    free(a4);
    free(a5);
    free(a6);
}

三、常见排序算法的实现

关于排序算法,我们都是通过先局部(单趟)再整体去理解整段逻辑。

3.1 插入排序(InsertSort)

基本思路:将待排序的数值,根据序列中大小关系,逐渐插入到一个已经有序序列中,直到所有数据插入完为止,得到新的有序序列。实际中玩扑克牌时,就用了插入排序的思想

void InsertSort(int* a, int n)
{
  //[0,end] end+1//下标的意思
  //循环结束的条件 end>0或者找到插入目标
  //end从0开始[0,0]
  for (int i = 0; i < n - 1; i++)
  {
    int end = i;
    int tmp = a[end + 1]; 
    while (end >= 0 && tmp < a[end])//当出现大于前面有序的数据停下,>就是倒过来
    {
      a[end + 1] = a[end];
      end--;
    }
    a[end + 1] = tmp;
  }
};

过程解析:

我们可以通过扑克牌排序的过程去理解插入排序,比如现在我们手上有一副扑克牌可以分为两个部分:有序部分和所需插入记录

将这两个部分划分区间得到[0, end] [end + 1 , size_max-1],代码逻辑是将待插入元素用临时变量tmp记录起来,通过条判断进行数组元素覆盖移动,为待插入元素找到合适的位置。这里需要注意的部分为循环条件是到[0, n - 2]属于有序部分,关于n-1为最后待插入数据。

这里我们还需要考虑下越界访问的情况,由于待插入数据为当前有序区间中最小数值,在匹配过程中不能单纯从大小判断去完成移动,同时需要对end>=0的限制,表示完成了有序区间内数据的比较,结果为最小值需要在最前面插入。

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

  • 元素集合越接近有序,直接插入排序算法的时间效率越高
  • 时间复杂度:逆序O(N2)、顺序有序O(N)
  • 空间复杂度: O(1)
  • 稳定性:稳定

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

基本思路:通过预排序使得无序接近有序序列,大体流程:先选定一个整数gap,将待排序序列中所有记录分组,所有距离为gap记录分在同一组,并对每一组记录进行排序,重复上述分组和排序的工作(gap不断缩小),当gap到达1,此时记录已经接近有序,最后整体进行插入排序,使得记录排好序。

希尔排序分为两部分:

  • 预排序:分布对每组进行插入排序,当gap>1时,目的让他接近有序
  • 直接插入排序:当gap==1时,目的是让他有序

关于gap的取数,有两种选择:

  • gap=gap/2;
  • gap=gap/3+1;

3.2.1 预排序

单组排序:

int gap=3;//规定每隔三个空为一组,单独插入排序
for(int j=0;j<gap;j++)//一共有三组
{
  for(int i=j;i<n-gap;i+=gap)//每一组之间的插入排序
    {
        int end=i;
        int tmp=a[end+gap];
        while(end>=0)
        {
      if(tmp<a[end])
            {
                a[end+gap]=a[end];
                end-=gap;
            }
            else
                break;
        }
        a[end+gap]=tmp;
    }
}

这里使用下标(N- gap) -1作为分界线,是为了方便大家理解这里内层循环条件为什么这样子写,而实际中分组是通过数据去划分的,需要大家从下标转化到对应数值中。关于第二层循环i,这里是根据(n - gap - 1)+ gap = n - 1为最后一个待排序元,比如红色、蓝色、绿最后一个元素超过了当前分界线说明这就是它们分组的最后一个元素,如果继续i+=gap就会发生越界访问。

希尔排序是对于插入排序的优化,对此逻辑上跟插入排序没有太大区别。区别在于希尔排序先用了预排序使得无序序列变得接近有序序列,

多组同时排序(每组并不是单独阶段完全处理)

int gap=3;//规定每隔三个空为一组,单独插入排序
  for(int i=j;i<n-gap;i++)//多个组同时排序
    {
        int end=i;
        int tmp=a[end+gap];
        while(end>=0)
        {
      if(tmp<a[end])
            {
                a[end+gap]=a[end];
                end-=gap;
            }
            else
                break;
        }
        a[end+gap]=tmp;
    }

过程解析:

  • gap越大,大的值越快调到后面,小的值可以更快的调到前面,越不接近有序
  • gap越小,跳得越慢,但是越接近有序。如果gap==1就是直接插入排序

整理过程(上述属于单躺排序)

int gap = n;
  while (gap > 1)
  {
        //gap不断发生变换
    gap =gap / 3 + 1;
    for (int i = 0; i < n - gap; i++)//多组
    {
      int end = i;
      int tmp = a[end + gap];
      while (end >= 0 && tmp < a[end])
      {
        a[end + gap] = a[end];
        end -= gap;
      }
      a[end + gap] = tmp;
    }
  }
}

每次预排序都会产生作用,意味着上一组预排序会影响下一组预排序导致影响时间复杂度.

希尔排序的特点总结:

  • 希尔排序是对直接插入排序的优化。
  • 当gap>1时都是属于预排序,目的是让数组更接近有序。
  • 当gap=1时,数据已经接近有序,就是简单插入排序,直接插入排序算法的时间效率越高
  • 稳定性:不稳定

3.2.2 关于希尔排序时间复杂度

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

《数据结构(C语言版)》— 严蔚敏

《数据结构-用面相对象方法与C++描述》— 殷人昆

小总结:

  • 插入排序:数据量小或已经部分排序,足够好且实现简单
  • 希尔排序:数据量大,希尔排序通常能提供更好的性能


【初阶数据结构】深度解析七大常见排序|掌握底层逻辑与原理(二)https://developer.aliyun.com/article/1617281

相关文章
|
7月前
|
安全 算法 网络协议
解析:HTTPS通过SSL/TLS证书加密的原理与逻辑
HTTPS通过SSL/TLS证书加密,结合对称与非对称加密及数字证书验证实现安全通信。首先,服务器发送含公钥的数字证书,客户端验证其合法性后生成随机数并用公钥加密发送给服务器,双方据此生成相同的对称密钥。后续通信使用对称加密确保高效性和安全性。同时,数字证书验证服务器身份,防止中间人攻击;哈希算法和数字签名确保数据完整性,防止篡改。整个流程保障了身份认证、数据加密和完整性保护。
|
7月前
|
NoSQL 算法 安全
Redis原理—1.Redis数据结构
本文介绍了Redis 的主要数据结构及应用。
Redis原理—1.Redis数据结构
|
6月前
|
JavaScript 算法 前端开发
JS数组操作方法全景图,全网最全构建完整知识网络!js数组操作方法全集(实现筛选转换、随机排序洗牌算法、复杂数据处理统计等情景详解,附大量源码和易错点解析)
这些方法提供了对数组的全面操作,包括搜索、遍历、转换和聚合等。通过分为原地操作方法、非原地操作方法和其他方法便于您理解和记忆,并熟悉他们各自的使用方法与使用范围。详细的案例与进阶使用,方便您理解数组操作的底层原理。链式调用的几个案例,让您玩转数组操作。 只有锻炼思维才能可持续地解决问题,只有思维才是真正值得学习和分享的核心要素。如果这篇博客能给您带来一点帮助,麻烦您点个赞支持一下,还可以收藏起来以备不时之需,有疑问和错误欢迎在评论区指出~
|
7月前
|
存储 机器学习/深度学习 算法
C 408—《数据结构》图、查找、排序专题考点(含解析)
408考研——《数据结构》图,查找和排序专题考点选择题汇总(含解析)。
281 29
|
7月前
|
存储 机器学习/深度学习 人工智能
C 408—《数据结构》易错考点200题(含解析)
408考研——《数据结构》精选易错考点200题(含解析)。
492 27
|
8月前
|
存储 人工智能 算法
【C++数据结构——内排序】二路归并排序(头歌实践教学平台习题)【合集】
本关任务是实现二路归并算法,即将两个有序数组合并为一个有序数组。主要内容包括: - **任务描述**:实现二路归并算法。 - **相关知识**: - 二路归并算法的基本概念。 - 算法步骤:通过比较两个有序数组的元素,依次将较小的元素放入新数组中。 - 代码示例(以 C++ 为例)。 - 时间复杂度为 O(m+n),空间复杂度为 O(m+n)。 - **测试说明**:平台会对你编写的代码进行测试,提供输入和输出示例。 - **通关代码**:提供了完整的 C++ 实现代码。 - **测试结果**:展示代码运行后的排序结果。 开始你的任务吧,祝你成功!
198 10
|
8月前
|
搜索推荐 算法 数据处理
【C++数据结构——内排序】希尔排序(头歌实践教学平台习题)【合集】
本文介绍了希尔排序算法的实现及相关知识。主要内容包括: - **任务描述**:实现希尔排序算法。 - **相关知识**: - 排序算法基础概念,如稳定性。 - 插入排序的基本思想和步骤。 - 间隔序列(增量序列)的概念及其在希尔排序中的应用。 - 算法的时间复杂度和空间复杂度分析。 - 代码实现技巧,如循环嵌套和索引计算。 - **测试说明**:提供了测试输入和输出示例,帮助验证代码正确性。 - **我的通关代码**:给出了完整的C++代码实现。 - **测试结果**:展示了代码运行的测试结果。 通过这些内容,读者可以全面了解希尔排序的原理和实现方法。
148 10
|
8月前
|
搜索推荐 C++
【C++数据结构——内排序】快速排序(头歌实践教学平台习题)【合集】
快速排序是一种高效的排序算法,基于分治策略。它的主要思想是通过选择一个基准元素(pivot),将数组划分成两部分。一部分的元素都小于等于基准元素,另一部分的元素都大于等于基准元素。然后对这两部分分别进行排序,最终使整个数组有序。(第一行是元素个数,第二行是待排序的原始关键字数据。本关任务:实现快速排序算法。开始你的任务吧,祝你成功!
200 7
|
10月前
|
Java 开发者 Spring
Spring AOP深度解析:探秘动态代理与增强逻辑
Spring框架中的AOP(Aspect-Oriented Programming,面向切面编程)功能为开发者提供了一种强大的工具,用以将横切关注点(如日志、事务管理等)与业务逻辑分离。本文将深入探讨Spring AOP的底层原理,包括动态代理机制和增强逻辑的实现。
196 4
|
10月前
|
前端开发 Java Maven
深入解析:如何用 Spring Boot 实现分页和排序
深入解析:如何用 Spring Boot 实现分页和排序
751 2

推荐镜像

更多
  • DNS