【八大数据排序法】快速排序法的图形理解和案例实现 | C++

本文涉及的产品
云原生大数据计算服务MaxCompute,500CU*H 100GB 3个月
简介: 排序算法是我们在程序设计中经常见到和使用的一种算法,它主要是将一堆不规则的数据按照递增或递减的方式重新进行排序。在如今的互联网信息时代,随着大数据和人工智能的发展,大型企业的数据库中有亿级的用户数据量。因此对其进行处理,排序算法也就成为了其中必不可缺的步骤之一。

7634ed785496bd57f53828c2a29f8537_fda870ad3fef413cad22d4791013291e.png

前言

       排序算法是我们在程序设计中经常见到和使用的一种算法,它主要是将一堆不规则的数据按照递增或递减的方式重新进行排序。在如今的互联网信息时代,随着大数据和人工智能的发展,大型企业的数据库中有亿级的用户数据量。因此对其进行处理,排序算法也就成为了其中必不可缺的步骤之一。


认识排序

       排序功能对计算机领域而言,是一项非常重要而且普遍的工作。排序中数据的移动方式可分为直接移动和逻辑移动两种方式,直接移动是直接交换存储数据的位置,而逻辑移动并不会移动数据存储的位置,仅改变指向这些数据辅助指针的值。排序通常按照数据量的多少和所使用的内存,可分为内部排序和外部排序,数据量小可以全部加载到内存来进行排序的,就称为内部排序,大部分排序属于此类。数据量大而无法一次性加载到内存中,必须借助磁带,磁盘等辅助存储器进行排序的,则称为外部排序。随着数据结构科学的进步,如今,陆续被提出的冒泡排序法,选择排序法,插入排序法,合并排序法,快速排序法,堆积排序法,希尔排序法,基数排序法,直接合并排序法等等,它们各有其特色和其应用场合。并且在算法中,我们非常关注算法程序代码的时间复杂度和空间复杂度,因为它会直接体现出我们程序代码的执行效率以及编程人员的逻辑思维等等的综合能力。当数据量相当庞大时,排序算法所花费的时间就显得相当重要,排序算法的时间复杂度可分为最好情况、最坏情况以及平均情况。另外,对于任何的排序算法都会有数据交换的操作,数据互换位置会暂时用到一个额外的空间,这也是排序算法中空间复杂度要考虑到的问题,而在排序算法中所使用的额外空间越小,它的空间复杂度就越好。


一、快速排序法是什么?

1.简要介绍

       快速排序法是由C.A.R.Hoare所提出来的一种排序方法。快速排序法又被称为分割交换排序法,是目前比较公认并且常用的最佳排序法,它使用到了分治法的思想,会先在数据中找到一个虚拟的中间值,并按此中间值将所有排序的数据分为两部分。其中小于中间值的放在左边,大于中间值的放在右边。再以分治法的思想以相同的方式去分别处理左右两边的数据,直到重复完成排序即可。


2.具体情况

       假设有n项记录,R1,R2,R3,...,Rn,其键值为K1,K2,K3,...,Kn。


       (1)先假设K为第一个键值。


       (2)从左向右找出键值,使得。


       (3)从右向左找出键值,使得。


       (4)如果i


       (5)如果i>=j,那么将与交换位置,并且将j作为基准点把数据列划分为左右两个部分,然后对于左右部分再次执行(1)~(5)的相应步骤,直到左边键值等于右边键值为止。


       用快速排序法对下面的10个数据进行从小到大的排序。具体情况如下图所示:

        ①当K=35时,,此时i

       ②当K=35时, 此时i

       ③当K=35时,,此时i>=j,所以将与互换位置,并且以j为基准点将数据列分为左右两个部分。具体情况如下图所示:


        ④经过上述步骤后,小于键值K的数据就被放在了左边,大于键值K的数据就被放在右边。具体情况如下图所示:

2c150969a7bb57fca72b3a80a4365c2c_59577ae7ee434873a181b51ec075e9d6.png


按照上述的排序过程继续对左右两部分分别排序,具体情况如下图所示:

c6729d6ced8081ad1b6f0d91e7961b39_b5b58bccea50426a9c7cb6a70ac0e70d.png


3.算法分析  

       ①快速排序法是不稳定排序法。


       ②快速排序法平均运行时间最快的排序算法。


       ③该排序法在最坏情况下空间复杂度为O(n),在最好情况下空间复杂度为O()。


       ④该排序法在最好情况和平均情况下时间复杂度为O(),在最坏情况下的时间复杂度为O(n^2)。


二、案例实现

1.案例一

①范例情况:用快速排序法对32,5,24,55,40,81,17,48,25,71这十个数据元素进行从小到大的排序,并且输出排序过程中每次处理下的结果情况。


②代码展示:

#include<iostream>
using namespace std;
#define size 10 //事先声明排序数据的个数
class quick {
public:
  int data[size];
  void showresult(){
  for (int i = 0; i < size; i++)
    cout <<" " << data[i];
  cout << endl;
  }
  int num = 0;
  void quick_start(int left,int right) {
  int left_idx, right_idx;
  int temp;
  if (left<right)
  {
    left_idx = left + 1;
    right_idx = right;
    while (1)
    {
    //测试每次排序的中间过程情况
    cout << "第" << num++ << "次排序:";
    showresult();
    //从左向右扫描,找出一个键值大于data[left]的数据元素
    for (int i = left+1; i <= right; i++)
    {
      if (data[i]>data[left])
      {
      left_idx = i;
      break;
      }
      left_idx++;
    }
    //从右向左扫描,找出一个键值小于data[left]的数据元素
    for (int j = right; j >= left+1; j--)
    {
      if (data[j] < data[left])
      {
      right_idx = j;
      break;
      }
      right_idx--;
    }
    //如果left_idx<right_idx,将二者交换位置
    if (left_idx < right_idx){
      temp = data[left_idx];
      data[left_idx] = data[right_idx];
      data[right_idx] = temp;
    }
    else {
      break;
    }
    }
    //如果left_idx>=right_idx
    if (left_idx >= right_idx)
    {
    //将data[left]与data[right_idx]交换位置
    temp = data[left];
    data[left] = data[right_idx];
    data[right_idx] = temp;
    //以递归的方式继续进行左半的快速排序
    quick_start(left,right_idx-1);
    //以递归的方式继续进行右半的快速排序
    quick_start(right_idx+1,right);
    }
  }
  }
};
void text()
{
  quick q;
  cout << "请输入要排序的" << size << "个数据" << endl;
  for (int i = 0; i < size; i++)
  cin >> q.data[i];
  cout << "排序前:" << endl;
  q.showresult();
  q.quick_start(0,size-1);
  cout << "排序后:" << endl;
  q.showresult();
}
int main()
{
  text();
}

③结果展示:

701892d3e990e54aaa1c3ae299f591aa_a89909b520264d688beb7fe7f6d916d9.png


总结

       以上就是快速排序法的所有内容,其实从我们上面的代码中不难看出,快速排序法就是分治、冒泡、递归这些经典算法的结合应用。该排序算法启示我们,算法是可以通过像组装的方式来结合应用的,这样就可以去解决更复杂的问题。从而也说明了学习算法和数据结构,核心是去学它的思想和方法,并且用其来解决我们要去解决的问题。



相关实践学习
基于MaxCompute的热门话题分析
本实验围绕社交用户发布的文章做了详尽的分析,通过分析能得到用户群体年龄分布,性别分布,地理位置分布,以及热门话题的热度。
SaaS 模式云数据仓库必修课
本课程由阿里云开发者社区和阿里云大数据团队共同出品,是SaaS模式云原生数据仓库领导者MaxCompute核心课程。本课程由阿里云资深产品和技术专家们从概念到方法,从场景到实践,体系化的将阿里巴巴飞天大数据平台10多年的经过验证的方法与实践深入浅出的讲给开发者们。帮助大数据开发者快速了解并掌握SaaS模式的云原生的数据仓库,助力开发者学习了解先进的技术栈,并能在实际业务中敏捷的进行大数据分析,赋能企业业务。 通过本课程可以了解SaaS模式云原生数据仓库领导者MaxCompute核心功能及典型适用场景,可应用MaxCompute实现数仓搭建,快速进行大数据分析。适合大数据工程师、大数据分析师 大量数据需要处理、存储和管理,需要搭建数据仓库?学它! 没有足够人员和经验来运维大数据平台,不想自建IDC买机器,需要免运维的大数据平台?会SQL就等于会大数据?学它! 想知道大数据用得对不对,想用更少的钱得到持续演进的数仓能力?获得极致弹性的计算资源和更好的性能,以及持续保护数据安全的生产环境?学它! 想要获得灵活的分析能力,快速洞察数据规律特征?想要兼得数据湖的灵活性与数据仓库的成长性?学它! 出品人:阿里云大数据产品及研发团队专家 产品 MaxCompute 官网 https://www.aliyun.com/product/odps&nbsp;
目录
相关文章
|
13天前
|
存储 监控 算法
基于 C++ 哈希表算法实现局域网监控电脑屏幕的数据加速机制研究
企业网络安全与办公管理需求日益复杂的学术语境下,局域网监控电脑屏幕作为保障信息安全、规范员工操作的重要手段,已然成为网络安全领域的关键研究对象。其作用类似网络空间中的 “电子眼”,实时捕获每台电脑屏幕上的操作动态。然而,面对海量监控数据,实现高效数据存储与快速检索,已成为提升监控系统性能的核心挑战。本文聚焦于 C++ 语言中的哈希表算法,深入探究其如何成为局域网监控电脑屏幕数据处理的 “加速引擎”,并通过详尽的代码示例,展现其强大功能与应用价值。
36 1
|
20天前
|
存储 C++
UE5 C++:自定义Http节点获取Header数据
综上,通过为UE5创建一个自定义HTTP请求类并覆盖GetResult方法,就能成功地从HTTP响应的Header数据中提取信息。在项目中使用自定义类,不仅可以方便地访问响应头数据,也可随时使用这些信息。希望这种方法可以为你的开发过程带来便利和效益。
76 35
|
3月前
|
算法 Serverless 数据处理
从集思录可转债数据探秘:Python与C++实现的移动平均算法应用
本文探讨了如何利用移动平均算法分析集思录提供的可转债数据,帮助投资者把握价格趋势。通过Python和C++两种编程语言实现简单移动平均(SMA),展示了数据处理的具体方法。Python代码借助`pandas`库轻松计算5日SMA,而C++代码则通过高效的数据处理展示了SMA的计算过程。集思录平台提供了详尽且及时的可转债数据,助力投资者结合算法与社区讨论,做出更明智的投资决策。掌握这些工具和技术,有助于在复杂多变的金融市场中挖掘更多价值。
96 12
|
3月前
|
存储 监控 算法
公司监控上网软件架构:基于 C++ 链表算法的数据关联机制探讨
在数字化办公时代,公司监控上网软件成为企业管理网络资源和保障信息安全的关键工具。本文深入剖析C++中的链表数据结构及其在该软件中的应用。链表通过节点存储网络访问记录,具备高效插入、删除操作及节省内存的优势,助力企业实时追踪员工上网行为,提升运营效率并降低安全风险。示例代码展示了如何用C++实现链表记录上网行为,并模拟发送至服务器。链表为公司监控上网软件提供了灵活高效的数据管理方式,但实际开发还需考虑安全性、隐私保护等多方面因素。
52 0
公司监控上网软件架构:基于 C++ 链表算法的数据关联机制探讨
|
4月前
|
存储 人工智能 算法
【C++数据结构——内排序】二路归并排序(头歌实践教学平台习题)【合集】
本关任务是实现二路归并算法,即将两个有序数组合并为一个有序数组。主要内容包括: - **任务描述**:实现二路归并算法。 - **相关知识**: - 二路归并算法的基本概念。 - 算法步骤:通过比较两个有序数组的元素,依次将较小的元素放入新数组中。 - 代码示例(以 C++ 为例)。 - 时间复杂度为 O(m+n),空间复杂度为 O(m+n)。 - **测试说明**:平台会对你编写的代码进行测试,提供输入和输出示例。 - **通关代码**:提供了完整的 C++ 实现代码。 - **测试结果**:展示代码运行后的排序结果。 开始你的任务吧,祝你成功!
126 10
|
4月前
|
搜索推荐 算法 数据处理
【C++数据结构——内排序】希尔排序(头歌实践教学平台习题)【合集】
本文介绍了希尔排序算法的实现及相关知识。主要内容包括: - **任务描述**:实现希尔排序算法。 - **相关知识**: - 排序算法基础概念,如稳定性。 - 插入排序的基本思想和步骤。 - 间隔序列(增量序列)的概念及其在希尔排序中的应用。 - 算法的时间复杂度和空间复杂度分析。 - 代码实现技巧,如循环嵌套和索引计算。 - **测试说明**:提供了测试输入和输出示例,帮助验证代码正确性。 - **我的通关代码**:给出了完整的C++代码实现。 - **测试结果**:展示了代码运行的测试结果。 通过这些内容,读者可以全面了解希尔排序的原理和实现方法。
108 10
|
4月前
|
搜索推荐 C++
【C++数据结构——内排序】快速排序(头歌实践教学平台习题)【合集】
快速排序是一种高效的排序算法,基于分治策略。它的主要思想是通过选择一个基准元素(pivot),将数组划分成两部分。一部分的元素都小于等于基准元素,另一部分的元素都大于等于基准元素。然后对这两部分分别进行排序,最终使整个数组有序。(第一行是元素个数,第二行是待排序的原始关键字数据。本关任务:实现快速排序算法。开始你的任务吧,祝你成功!
100 7
|
4月前
|
存储 算法 搜索推荐
【C++面向对象——群体类和群体数据的组织】实现含排序功能的数组类(头歌实践教学平台习题)【合集】
1. **相关排序和查找算法的原理**:介绍直接插入排序、直接选择排序、冒泡排序和顺序查找的基本原理及其实现代码。 2. **C++ 类与成员函数的定义**:讲解如何定义`Array`类,包括类的声明和实现,以及成员函数的定义与调用。 3. **数组作为类的成员变量的处理**:探讨内存管理和正确访问数组元素的方法,确保在类中正确使用动态分配的数组。 4. **函数参数传递与返回值处理**:解释排序和查找函数的参数传递方式及返回值处理,确保函数功能正确实现。 通过掌握这些知识,可以顺利地将排序和查找算法封装到`Array`类中,并进行测试验证。编程要求是在右侧编辑器补充代码以实现三种排序算法
82 5
|
8月前
|
编译器 C++
【C++核心】指针和引用案例详解
这篇文章详细讲解了C++中指针和引用的概念、使用场景和操作技巧,包括指针的定义、指针与数组、指针与函数的关系,以及引用的基本使用、注意事项和作为函数参数和返回值的用法。
116 3
|
8月前
|
C++
【C++案例】一个项目掌握C++基础-通讯录管理系统
这篇文章通过一个通讯录管理系统的C++项目案例,详细介绍了如何使用C++实现添加、显示、删除、查找、修改和清空联系人等功能。
147 3

热门文章

最新文章