蓝桥杯C语言知识点补充——快速排序详解

今天刚准备更新一道习题的,结果发现有些知识点生疏了不少,今天就更新2个知识点吧。

可以说是非常好的算法

快速排序

简介

快速排序(Quicksort)是对冒泡排序的一种改进。

快速排序由C. A. R. Hoare在1962年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

原理图

在快速排序算法中,使用了分治策略。首先把序列分成两个子序列,递归地对子序列进行排序,直到整个序列排序结束。

步骤如下:

在序列中选择一个关键元素做为轴;

对序列进行重新排序,将比轴小的元素移到轴的前边,比轴大的元素移动到轴的后面。在进行划分之后,轴便在它最终的位置上;

递归地对两个子序列进行重新排序:含有较小元素的子序列和含有较大元素的子序列。

下面的动画展示了快速排序算法的工作原理。

代码

void sort(int *a, int left, int right) {     if(left >= right)/*如果左边索引大于或者等于右边的索引就代表已经整理完成一个组了*/     {         return ;     }     int i = left;     int j = right;     int key = a[left];           while(i < j)                               /*控制在当组内寻找一遍*/     {         while(i < j && key <= a[j])         /*而寻找结束的条件就是,1,找到一个小于或者大于key的数(大于或小于取决于你想升         序还是降序)2,没有符合条件1的,并且i与j的大小没有反转*/          {             j--;/*向前寻找*/         }                   a[i] = a[j];         /*找到一个这样的数后就把它赋给前面的被拿走的i的值(如果第一次循环且key是         a[left],那么就是给key)*/                   while(i < j && key >= a[i])         /*这是i在当组内向前寻找,同上,不过注意与key的大小关系停止循环和上面相反,         因为排序思想是把数往两边扔,所以左右两边的数大小与key的关系相反*/         {             i++;         }                   a[j] = a[i];     }           a[i] = key;/*当在当组内找完一遍以后就把中间数key回归*/     sort(a, left, i - 1);/*最后用同样的方式对分出来的左边的小组进行同上的做法*/     sort(a, i + 1, right);/*用同样的方式对分出来的右边的小组进行同上的做法*/                        /*当然最后可能会出现很多分左右,直到每一组的i = j 为止*/ }

1234567891011121314151617181920212223242526272829303132333435363738

void sort(int *a, int left, int right){    if(left >= right)/*如果左边索引大于或者等于右边的索引就代表已经整理完成一个组了*/    {        return ;    }    int i = left;    int j = right;    int key = a[left];         while(i < j)                               /*控制在当组内寻找一遍*/    {        while(i < j && key <= a[j])        /*而寻找结束的条件就是,1,找到一个小于或者大于key的数(大于或小于取决于你想升        序还是降序)2,没有符合条件1的,并且i与j的大小没有反转*/         {            j--;/*向前寻找*/        }                 a[i] = a[j];        /*找到一个这样的数后就把它赋给前面的被拿走的i的值(如果第一次循环且key是        a[left],那么就是给key)*/                 while(i < j && key >= a[i])        /*这是i在当组内向前寻找,同上,不过注意与key的大小关系停止循环和上面相反,        因为排序思想是把数往两边扔,所以左右两边的数大小与key的关系相反*/        {            i++;        }                 a[j] = a[i];    }         a[i] = key;/*当在当组内找完一遍以后就把中间数key回归*/    sort(a, left, i - 1);/*最后用同样的方式对分出来的左边的小组进行同上的做法*/    sort(a, i + 1, right);/*用同样的方式对分出来的右边的小组进行同上的做法*/                       /*当然最后可能会出现很多分左右,直到每一组的i = j 为止*/}

视频详解

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏专注数据中心高性能网络技术研发

[LeetCode]Array主题系列{1,11,15,16,18,26,27,31,33,34题}

1.内容介绍 开一篇文章记录在leetcode中array主题下面的题目和自己的思考以及优化过程,具体内容层次按照{题目,分析,初解,初解结果,优化解,优化解结...

2906
来自专栏吉浦迅科技

DAY 1: 学习CUDA C Programming Guide

1663
来自专栏一心无二用,本人只专注于基础图像算法的实现与优化。

SSE图像算法优化系列十二:多尺度的图像细节提升。

无意中浏览一篇文章,中间提到了基于多尺度的图像的细节提升算法,尝试了一下,还是有一定的效果的,结合最近一直研究的SSE优化,把算法的步骤和优化过程分享给大家。...

1978
来自专栏python读书笔记

《python算法教程》Day3 - 递归递归简介代码示例

这是《python算法教程》的第3篇读书笔记。由于之前看书的效率太低了,所以拖了一个多星期才写第三篇读书笔记。这次主要简单总结一下递归(recursion)。 ...

2528
来自专栏软件开发 -- 分享 互助 成长

散列表(哈希表)

序言: 如果将一系列的记录按照关键字的某种函数存储,那么在查找某个数据的时候就可以直接通过关键字计算出来了,而不在需要“比较”,这样会非常高效,这就是散列技术。...

1768
来自专栏爱撒谎的男孩

回溯算法

1483
来自专栏ml

cf------(round)#1 C. Ancient Berland Circus(几何)

C. Ancient Berland Circus time limit per test 2 seconds memory limit per test ...

2333
来自专栏Java Web

最长公共子序列问题

问题描述: 求两个字符序列的公共最长子序列。 ---- 最长公共子串 在回到子序列问题之前,先来了解一下子串的问题。 例如,HISH和FISH两个字符序列的公...

3024
来自专栏吉浦迅科技

DAY2:阅读CUDA C Programming Guide之编程模型

1264
来自专栏小樱的经验随笔

从零开始学算法:高精度计算

前言:由于计算机运算是有模运算,数据范围的表示有一定限制,如整型int(C++中int 与long相同)表达范围是(-2^31~2^31-1),unsigned...

33913

扫码关注云+社区