我的编程空间,编程开发者的网络收藏夹
学习永远不晚

C语言快速排序如何应用

短信预约 -IT技能 免费直播动态提醒
省份

北京

  • 北京
  • 上海
  • 天津
  • 重庆
  • 河北
  • 山东
  • 辽宁
  • 黑龙江
  • 吉林
  • 甘肃
  • 青海
  • 河南
  • 江苏
  • 湖北
  • 湖南
  • 江西
  • 浙江
  • 广东
  • 云南
  • 福建
  • 海南
  • 山西
  • 四川
  • 陕西
  • 贵州
  • 安徽
  • 广西
  • 内蒙
  • 西藏
  • 新疆
  • 宁夏
  • 兵团
手机号立即预约

请填写图片验证码后获取短信验证码

看不清楚,换张图片

免费获取短信验证码

C语言快速排序如何应用

今天小编给大家分享一下C语言快速排序如何应用的相关知识点,内容详细,逻辑清晰,相信大部分人都还太了解这方面的知识,所以分享这篇文章给大家参考一下,希望大家阅读完这篇文章后有所收获,下面我们一起来了解一下吧。

快速排序

快速排序,说白了就是给基准数据找其正确索引位置的过程

1.1快速排序引入

希尔排序相当于直接插入排序的升级,他们属于插入排序类;堆排序相当于简单选择排序的升级,他们同属于选择排序类;而对于交换排序类的冒泡排序升级版本就是快速排序。

1.2快速排序的基本思想

通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字比另一部分记录的关键字小,则可分别对这两部分记录继续进行排序,以达到整个排序的目的。

1.3快速排序的排序流程

  • 首先设定一个分界值,通过该分界值将数组分成左右两部分。

  • 将大于或等于分界值的数据集中到数组右边,小于分界值的数据集中到数组的左边。此时,左边部分中各元素都小于或等于分界值,而右边部分中各元素都大于或等于分界值。

  • 然后,左边和右边的数据可以独立排序。对于左侧的数组数据,又可以取一个分界值,将该部分数据分成左右两部分,同样在左边放置较小值,右边放置较大值。右侧的数组数据也可以做类似处理。

  • 重复上述过程,可以看出,这是一个递归定义。通过递归将左侧部分排好序后,再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后,整个数组的排序也就完成了。

总结来说:就是分治+填数

1.4实例说明

以12、10、8、22、5、13、28、21、11我们要将它按从小到大排序排序过程:

C语言快速排序如何应用

详细过程:

设定两个指针 left 和 right,它们初始分别指向待排序序列的左端和右端;此外还要附设一个基准元素 tmp(一般选取第一个,本例中基准tmp的值为 20)。

C语言快速排序如何应用

首先从 right 所指的位置从右向左搜索找到第一个小于 tmp 的元素,然后将其记录在基准元素所在的位置。

C语言快速排序如何应用

接着从 left 所指的位置从左向右搜索找到第一个大于 tmp的元素,然后将其记录在 right 所指向的位置。

C语言快速排序如何应用

然后再从 right 所指向的位置继续从右向左搜索找到第一个小于 tmp 的元素,然后将其记录在 left 所指向的位置。

C语言快速排序如何应用

接着,left 继续从左向右搜索第一个大于 tmp的元素,如果在搜索过程中出现了 left == right ,则说明一趟快速排序结束。此时将 tmp 记录在 left 和 right 共同指向的位置即可。

C语言快速排序如何应用

以上便是一轮快速排序的详细过程

注意:

  1. 向下划分至少需要这个组两个数据,才有必要划分,0个或者1个都没有必要

  2. 划分时:从右向左找比基准小的(相等)

  3. 从左向右找比基准值大的

1.5代码实现

//一次划分函数  核心函数  //返回基准值最终所在下标int Partition(int *arr, int left, int right){//先讲arr数组里的[left, right]的第一个值 作为基准值int tmp = arr[left];while(left < right){while(left<right && arr[right] > tmp)//左右边界没有相遇且当前右边的值大于基准值tmpright--;if(left < right)//如果此时,左右边界没有相遇,那就只能证明右边right找到了一个小于等于基准值tmp的值{arr[left] = arr[right];}else{break;}while(left<right && arr[left] <= tmp)//左右边界没有相遇且当前左边的值小于等于基准值tmpleft++;if(left < right)//如果此时,左右边界没有相遇,那就只能证明左边left找到了一个大于基准值tmp的值{arr[right] = arr[left];}else{break;}}arr[left] = tmp;//此时 因为 left == rightreturn left;//return right ok}void Quick(int *arr, int left, int right){if(left < right)//通过left <right  保证[left, right]这个范围内至少两个数据{int par = Partition(arr, left, right);if(left < par-1)//基准值左半部分  至少有两个值才有必要去递归{Quick(arr, left, par-1);}if(par+1 < right)//基准值右半部分  至少有两个值才有必要去递归{Quick(arr, par+1, right);}}}void QuickSort(int *arr, int len){Quick(arr, 0, len-1);}

1.6性能分析

越乱越快,越有序越慢

时间复杂度:

最优情况:O(nlogn)每次数据元素都能平均的分成两个部分。得到一个完全二叉树;

最坏情况: O(n^2)这个数仅有右子树或左子树,比较次数为 (n-1)+(n-2) + (n-3) + &hellip; +1=n*(n-1)/2 ;

平均情况:O(nlogn)。

空间复杂度:O(1)。

稳定性:因为关键字的比较和交换是跳跃进行的,会改变数据元素的相对位置;因此,快速排序是一种不稳定的排序方法,但是也是内排序中平均效率最高的排序算法。

以上就是“C语言快速排序如何应用”这篇文章的所有内容,感谢各位的阅读!相信大家阅读完这篇文章都有很大的收获,小编每天都会为大家更新不同的知识,如果还想学习更多的知识,请关注编程网行业资讯频道。

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

C语言快速排序如何应用

下载Word文档到电脑,方便收藏和打印~

下载Word文档

猜你喜欢

C语言快速排序如何应用

今天小编给大家分享一下C语言快速排序如何应用的相关知识点,内容详细,逻辑清晰,相信大部分人都还太了解这方面的知识,所以分享这篇文章给大家参考一下,希望大家阅读完这篇文章后有所收获,下面我们一起来了解一下吧。快速排序快速排序,说白了就是给基准
2023-06-30

C语言如何实现快速排序

今天小编给大家分享一下C语言如何实现快速排序的相关知识点,内容详细,逻辑清晰,相信大部分人都还太了解这方面的知识,所以分享这篇文章给大家参考一下,希望大家阅读完这篇文章后有所收获,下面我们一起来了解一下吧。交换排序的思想基本思想:所谓交换,
2023-07-02

如何使用C语言实现快速排序

本篇内容主要讲解“ 如何使用C语言实现快速排序”,感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷,实用性强。下面就让小编来带大家学习“ 如何使用C语言实现快速排序”吧!快速排序的基本思想是:任取待排序数列中的一个数作为 key 值,通过
2023-07-05

C语言实现快速排序

快速排序不一定是稳定排序,这篇文章主要为大家详细介绍了C语言实现快速排序算法,具有一定的参考价值,感兴趣的同学可以借鉴阅读
2023-05-14

C语言如何实现快速排序算法

这篇文章将为大家详细讲解有关C语言如何实现快速排序算法,小编觉得挺实用的,因此分享给大家做个参考,希望大家阅读完这篇文章后可以有所收获。代码#define _CRT_SECURE_NO_WARNINGS 1//快速排序算法,递归求解#in
2023-06-22

c语言快速排序算法怎么使用

使用快速排序算法,需要先定义一个快速排序函数,然后在主函数中调用该函数。下面是一个示例的C语言快速排序算法的实现:```c#include void quickSort(int arr[], int left, int right) {in
2023-09-21

C语言归并排序如何应用

这篇文章主要介绍“C语言归并排序如何应用”的相关知识,小编通过实际案例向大家展示操作过程,操作方法简单快捷,实用性强,希望这篇“C语言归并排序如何应用”文章能帮助大家解决问题。一.归并排序1.1归并排序引入对于堆排序来说,因为用到了完全二叉
2023-06-30

c语言快速排序代码怎么写

下面是一个使用C语言实现快速排序的示例代码:```c#include // 交换两个元素的值void swap(int* a, int* b) {int temp = *a;*a = *b;*b = temp;}// 将数组划分为两部分,并
2023-10-11

c语言如何排序

这篇文章给大家分享的是有关c语言如何排序的内容。小编觉得挺实用的,因此分享给大家做个参考,一起跟随小编过来看看吧。c语言排序方法有:1、简单选择排序,基于O(n2)时间复杂度的排序算法;2、冒泡排序;3、简单插入排序;4、希尔排序;5、归并
2023-06-20

C语言标准库函数qsort(快速排序函数)

qsort函数是C语言标准库中提供的一个快速排序函数。它的函数原型如下:```cvoid qsort(void *base, size_t nmemb, size_t size,int (*compar)(const void *, con
2023-09-23

编程热搜

  • Python 学习之路 - Python
    一、安装Python34Windows在Python官网(https://www.python.org/downloads/)下载安装包并安装。Python的默认安装路径是:C:\Python34配置环境变量:【右键计算机】--》【属性】-
    Python 学习之路 - Python
  • chatgpt的中文全称是什么
    chatgpt的中文全称是生成型预训练变换模型。ChatGPT是什么ChatGPT是美国人工智能研究实验室OpenAI开发的一种全新聊天机器人模型,它能够通过学习和理解人类的语言来进行对话,还能根据聊天的上下文进行互动,并协助人类完成一系列
    chatgpt的中文全称是什么
  • C/C++中extern函数使用详解
  • C/C++可变参数的使用
    可变参数的使用方法远远不止以下几种,不过在C,C++中使用可变参数时要小心,在使用printf()等函数时传入的参数个数一定不能比前面的格式化字符串中的’%’符号个数少,否则会产生访问越界,运气不好的话还会导致程序崩溃
    C/C++可变参数的使用
  • css样式文件该放在哪里
  • php中数组下标必须是连续的吗
  • Python 3 教程
    Python 3 教程 Python 的 3.0 版本,常被称为 Python 3000,或简称 Py3k。相对于 Python 的早期版本,这是一个较大的升级。为了不带入过多的累赘,Python 3.0 在设计的时候没有考虑向下兼容。 Python
    Python 3 教程
  • Python pip包管理
    一、前言    在Python中, 安装第三方模块是通过 setuptools 这个工具完成的。 Python有两个封装了 setuptools的包管理工具: easy_install  和  pip , 目前官方推荐使用 pip。    
    Python pip包管理
  • ubuntu如何重新编译内核
  • 改善Java代码之慎用java动态编译

目录