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

本文涉及的产品
云原生大数据计算服务MaxCompute,500CU*H 100GB 3个月
云原生大数据计算服务 MaxCompute,5000CU*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;
目录
相关文章
|
2天前
|
存储 C++ 容器
C++标准库中提供了哪些数据容器作为数组的替代
C++标准库中提供了哪些数据容器作为数组的替代
11 5
|
1天前
|
设计模式 监控 Go
C++部分原有的数据发送能力是怎样的
C++部分原有的数据发送能力是怎样的?
6 1
|
29天前
|
C++ 容器
C++之评委打分案例(vector与deque容器练习)
C++之评委打分案例(vector与deque容器练习)
17 1
|
29天前
|
C++ 容器
C++之deque容器(构造、赋值、大小、插入与删除、存取、排序)
C++之deque容器(构造、赋值、大小、插入与删除、存取、排序)
17 1
|
1月前
|
数据安全/隐私保护 C++
C++语言深入理解类的封装与数据隐藏
深入理解类的封装与数据隐藏
|
1月前
|
C++
C++函数的返回数据写法的思路
C++函数使用尾置返回类型、decltype、类型别名返回一个数组引用
|
15天前
|
安全 算法 编译器
C++一分钟之-内存模型与数据竞争
【7月更文挑战第10天】了解C++11内存模型对多线程编程至关重要。它定义了线程间同步规则,包括顺序一致性、原子操作和内存屏障。数据竞争可能导致不确定行为,如脏读和丢失更新。可通过互斥量、原子操作和无锁编程避免竞争。示例展示了`std::mutex`和`std::atomic`的使用。掌握内存模型规则,有效防止数据竞争,确保多线程安全和性能。
21 0
|
1月前
|
存储 编译器 C++
c++primer plus 6 读书笔记 第三章 处理数据
c++primer plus 6 读书笔记 第三章 处理数据
|
29天前
|
算法 搜索推荐 C++
C++之STL常用算法(遍历、查找、排序、拷贝、替换、算数生成、集合)
C++之STL常用算法(遍历、查找、排序、拷贝、替换、算数生成、集合)
19 0
|
29天前
|
C++
C++之员工分组案例
C++之员工分组案例
10 0