首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

如何用c实现快速排序算法中的递归?

快速排序是一种常用的排序算法,它通过递归地将数组分成较小和较大的两个子数组来实现排序。下面是用C语言实现快速排序算法中的递归部分的示例代码:

代码语言:txt
复制
#include <stdio.h>

// 交换数组中两个元素的位置
void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 将数组划分为两个子数组,并返回划分点的下标
int partition(int arr[], int low, int high) {
    int pivot = arr[high];  // 选取最后一个元素作为基准点
    int i = low - 1;  // i指向小于基准点的元素

    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }

    swap(&arr[i + 1], &arr[high]);
    return i + 1;
}

// 递归地对子数组进行快速排序
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pivotIndex = partition(arr, low, high);
        quickSort(arr, low, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, high);
    }
}

int main() {
    int arr[] = {9, 5, 2, 7, 1, 8, 3};
    int n = sizeof(arr) / sizeof(arr[0]);

    quickSort(arr, 0, n - 1);

    printf("排序结果:");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

在上述代码中,swap函数用于交换数组中两个元素的位置。partition函数用于将数组划分为两个子数组,并返回划分点的下标。quickSort函数是递归地对子数组进行快速排序的主要函数。

快速排序的基本思想是选取一个基准点,将数组划分为两个子数组,其中一个子数组的元素都小于基准点,另一个子数组的元素都大于基准点。然后,递归地对两个子数组进行快速排序,直到子数组的长度为1或0时停止递归。

快速排序算法的优势在于平均时间复杂度为O(nlogn),且具有原地排序的特点,不需要额外的存储空间。它在处理大规模数据时表现出色,并且在实际应用中被广泛使用。

腾讯云提供了多种云计算相关产品,例如云服务器、云数据库、云存储等。具体推荐的产品和产品介绍链接地址可以根据实际需求和情况进行选择。

页面内容是否对你有帮助?
有帮助
没帮助

相关·内容

快速排序(三种算法实现和非递归实现)

快速排序(Quick Sort)是对冒泡排序一种改进,基本思想是选取一个记录作为枢轴,经过一趟排序,将整段序列分为两个部分,其中一部分值都小于枢轴,另一部分都大于枢轴。...对于快速排序一次排序,有很多种算法,我这里列举三种。 左右指针法 选取一个关键字(key)作为枢轴,一般取整组记录第一个数/最后一个,这里采用选取序列最后一个数为枢轴。...当left >= right时,一趟快速排序就完成了,这时将Key和array[left]值进行一次交换。...2、直接插入 由于是递归程序,每一次递归都要开辟栈帧,当递归到序列里值不是很多时,我们可以采用直接插入排序来完成,从而避免这些栈帧消耗。...,所以这里要 - 1; } ---- 非递归实现 递归算法主要是在划分子区间,如果要非递归实现快排,只要使用一个栈来保存区间就可以了。

1.3K30
  • 快速排序算法思路分析和C++源代码(递归和非递归)

    快速排序由于排序效率在同为O(N*logN)几种排序方法效率较高,因此经常被采用,再加上快速排序思想----分治法也确实实用,因此很多软件公司笔试面试喜欢考这个。...快速排序C.R.A.Hoare于1962年提出一种划分交换排序。它采用了一种分治策略,通常称其为分治法(Divide-and-ConquerMethod)。...总关键字比较次数:O(nlgn)   尽管快速排序最坏时间为O(n*n),但就平均性能而言,它是基于关键字比较内部排序算法中速度最快者,快速排序亦因此而得名。...它平均时间复杂度为O(nlgn)。   快排空间复杂度:在通常情况下为O(log2n),需要使用深O(log2n)实现递归,如果是最坏情况的话,很显然就要O(n)空间了。...*********************************** 应用场景:   快排算法一般应用在排序,但是分治法思想应用广泛,比如在《剑指Offer》, 题40:最小k个数和题39:数组中出现次数超过一半数字均用到了分治法思想

    1.5K70

    快速排序:高效分割与递归排序领域王者算法

    文章目录 前言 一、快速排序介绍 二、快速排序实现 2.1 hoare版本 为什么每次相遇位置都比key要小 2.2 挖坑法 2.3 前后指针版本 三、快速排序优化 快排最坏情况 3.1 三数取...3.2 递归到小子区间时使用插入排序 3.3 快速排序最终代码 四、快速排序总结 快速排序特性总结: 一、快速排序介绍 快速排序是一种基于分治思想高效排序算法,由Tony Hoare于1960...二、快速排序实现 快速排序是一种基于分治思想高效排序算法其核心就是每次找到最中间位置然后再进行递归继续找到最中间位置然后再分割一直分割到只剩一个数时候那么这个数组就是有序了。...每次找到中间值之后利用分治思想,大问题化为小问题 然后递归进行排序递归完成时每个中间值都找到就是排序时候 而要搞定一个排序首先最先解决就是其中单趟排序下面就是各位大佬想出来单趟排序方法: 先把部分单趟排序搞出来后面来实现整体排序就简单多了...,每次都需要全部遍历一遍才找到一个数据 所以就有了三数取这个算法 3.1 三数取 顾名思义,三数取中就是把,left 和 mid right 里面找到一个中间数下标来进行返回 然后再把 left

    20110

    【数据结构与算法】:非递归实现快速排序、归并排序

    1.非递归实现快速排序 快速排序递归实现主要依赖于栈(stack)来模拟递归过程函数调用栈。...递归版本快速排序通过递归调用自身来处理子数组,而非递归版本则通过手动管理一个栈来跟踪接下来需要排序子数组边界 那么怎样通过栈来实现排序过程呢?...思路如下: 使用栈实现快速排序是对递归版本模拟。在递归快速排序,函数调用栈隐式地保存了每次递归调用状态。...但是在非递归实现,你需要显式地使用一个辅助栈来保存子数组边界 以下是具体步骤和栈操作过程: 初始化辅助栈: 创建一个空栈。...下面是归并排序算法步骤: 递归分解数组:如果数组长度大于1,首先将数组分解成两个部分。

    42010

    排序算法 | 快速排序(含C++Python代码实现

    导言 排序算法,就是使得序列按照一定要求排列方法。排序算法有很多,本文将介绍面试中常常被问到经典排序算法快速排序,并分别利用C++和Python进行实现。...前戏 Amusi 作为一个2019年秋招大军中一员,经历过数次面试。就个人经历而言,今天分享快速排序算法属于常见问题排行榜前五。...之前CVer推送了 排序算法 | 冒泡排序(含C++/Python代码实现),一些同学反映太简单了,想知道其它复杂排序算法介绍,Shell排序和桶排序等。...(这个过程,我们可以使用递归快速实现) 步骤 快速排序使用分治法来把一个串(list)分为两个子串(sub-lists)。...这里Amusi可是花了很大决心才将自制图像po出来,因为画实在... 好,我们直接看代码吧 代码实现 注:下面都是利用递归实现快速排序

    79800

    【数据结构与算法快速排序递归实现方法

    一.前言 如果数据量过大的话,不断递归就会出现栈溢出现象,这个时候你代码是没问题,但就是跑不起来,这个时候就要把递归改成非递归。...一般有两种改法: 1.直接改,利用循环等; 2.借助栈辅助。 而快速排序递归实现方法就需要借助栈辅助。...二.非递归实现 通过观察我们发现,每次递归调用传过去是一个数组和一个区间,数组自不用说,这个区间就是我们突破点; 也就是说我们只要想办法在循环时候拿到本次要排序区间就行了,那要怎么做呢?...2.取出栈顶两个数据,分别赋给 begin 和 end ,注意在这之后要pop掉取出数据; 3.然后就是快排逻辑,有三种方法,哪种都可以; 如果不清楚这三种方法的话,请点击:快速排序三种实现方法...出一个就要pop掉一个数据 Stackpop(&st); int end = Stacktop(&st); Stackpop(&st); int keyi = begin; //以下为快速排序逻辑

    16810

    排序篇】快速排序递归实现与归并排序实现

    1 快速排序递归 利用迭代方式来模仿递归快速排序递归本质也就是它可以拿到那些待排序区间,那么不就说明了只要我们右那些待排序区间就可以不再需要递归了。...为此我们只需要用一个容器来存储这些区间就可以了,在众多数据结构我选择利用栈来实现这个方法,如果你要用队列也可以,只是存储区间而已。那么如何获取这些区间呢?...好像和递归差不多,每次就是差不多,快速排序逻辑是不会变,我们只把原来递归处理改成了迭代。 将区间保存到栈可以写一个结构体,也可以直接传,取出时也一次取两个就可以了,不影响。...归并排序 基本思想: 归并排序(MERGT-SORT)是建立在归并操作上一种有效排序算法,该算法是采用分治(Divide and Conquer)一个非常典型应用。...不同是,因为快速排序是确定基准值,因为基准值已经到了它排序最终位置,后续传区间就是基准值左右区间,但是归并排序可不是这样,归并排序是直接找数组中间下标,然后将数组一分为二,这样的话也就表示了再这过程

    11110

    C语言实现快速排序算法「建议收藏」

    大家好,又见面了,我是你们朋友全栈君。 一、快速排序算法(Quicksort) 1. 定义 快速排序C. A. R. Hoare在1962年提出。...快速排序是对冒泡排序一种改进,采用了一种分治策略。 2....基本思想 通过一趟排序将要排序数据分割成独立两部分,其中一部分所有数据都比另外一部分所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列...先从数列取出一个数作为基准数。 b. 分区过程,将比这个数大数全放到它右边,小于或等于它数全放到它左边。 c. 再对左右区间重复第二步,直到各区间只有一个数。...Version:1.0 Date: 2016/11/04 Description: 对数组进行快速排序 Funcion List: 实现快速排序算法 *******************

    2K10

    排序算法在JDK应用(二)快速排序

    作者|杨旭 来源|https://blog.csdn.net/Alex_NINE 改进后快速排序 在分析上述代码时,可以发现程序会在特殊情况调用sort()方法即改进后得快速排序,接下来就来分析sort...()快速排序代码实现。...* 通过双轴快速排序对指定范围内数据进行排序 * @param a the array to be sorted 被排序数组 * @param left the...Therefore in float and 因此在单双精度排序算法我们必须使用更加精确赋值即a[less]=a[great] * double...sort()源码部分,总结一下主要有以下几个要点 当待排数组长度小于47时就会直接使用插入排序 选择五个均匀间隔元素作为使用不同快速排序方法判断标准 如果五个元素互不相等那么使用双轴快速排序(两个枢轴为

    1.1K30

    排序算法快速排序升级版--三路快排详解 + 实现c语言)

    前言 之前我们学习了快速排序算法及其实现: 【排序算法】八大排序(下)(c语言实现)(附源码)-CSDN博客 不过它缺陷也很明显:当数组存在大量相同元素时,那些与基准值相同元素划分方法是未定义...基于此问题,今天给大家介绍快速排序升级版--三路快排,它能够很大程度地解决大量数据相同情况。...之前我们快速排序当中,都是默认将数组首元素作为基准值,如果该值是数组最大值或者最小值,那么划分操作相当于只是将该值进行了排序,时间复杂度就会退化为O(N^2)。...我们画图模拟一下它划分过程: 注意划分完成后left和right所处位置,便于确定下次递归区间。 二、三路快排具体实现 接下来,我们开始实现三路快排。...sz - 1); for (int i = 0; i < sz; i++)//打印数组 { printf("%d ", arr[i]); } return 0; } 总结 快速排序是一种高效且常用排序算法

    13610

    PHP快速排序算法实现原理及代码详解

    算法原理 下列动图来自五分钟学算法,演示了快速排序算法原理和步骤。 ?...步骤: 从数组中选个基准值 将数组中大于基准值放同一边、小于基准值放另一边,基准值位于中间位置 递归对分列两边数组再排序 代码实现 function quickSort($arr) {...9, 6, 3, 2, 5, 4, 8 after sort: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 use time: 0.0009009838104248s 时间复杂度 快速排序时间复杂度在最坏情况下是...快速排序是采用分治法进行遍历,我们将它看作一棵二叉树,它需要遍历次数就是二叉树深度,而根据完全二叉树定义,它深度至少是lg(N+1)。因此,快速排序遍历次数最少是lg(N+1)次。...这个应该非常简单,还是将快速排序看作一棵二叉树,它深度最大是N。因此,快读排序遍历次数最多是N次。

    70940

    算法图解》NOTE 4 快速排序法1.递归与分治法2.快速排序实现3.快速排序时间复杂度(用渐近表示法表示)

    这是《算法图解》第四篇读书笔记,主要涉及快速排序法。 1.递归与分治法 快速排序法(quick sort)之所以有这个名称,源于其排序速度,相较于其他排序方式来说,较快。...具体数学证明,请参考相关资料。 分治法思路是否和上一篇读书笔记所述递归(recursion)相似呢。实,分治法是通过递归实现。...2.快速排序实现 如上文所说,快速排序法应用了分治法思想。...其具体思路如下: 1.从原序列中选择一个数作为基础值 2.将原序列元素按照与基础值大小比较结果,分为大于基础值、小于基础值两个序列:S1和S2. 3.将元素列按照S1、基础值和S2顺序组合成一个新序列并将新序列返回...(用渐近表示法表示) 基于分治思想快速排序法,其时间复杂度为n*log2 n 。

    77660

    【初阶数据结构与算法】一命通关“快速排序“(内含快速排序三个版本以及非递归

    快速排序单趟排序 - 算法思想(十分重要) 在我们开始写代码时,理解算法思路是不可或缺一部分,所以接下来我们就来理解一下快速排序算法思想。(我们算法讲解思路都是以升序排序为主。...最终效果: 到这里,快速排序单趟排序思想就讲解完毕了!!! 接下来就进入用代码实现上述思想环节了。 2....快速排序单趟排序 - 代码实现 其实上述我们讲解思路,就是发明该算法的人提出,此人名为hoare。...快速排序整体排序 3.1 快速排序整体排序算法思路 从单趟排序我们就可以知道,单趟排序目的就是将我们所选key值放到待排序数组中正确位置上。...快速排序递归 我们都知道如果递归深度过深时,会导致栈溢出情况,从而使整个程序崩溃。 所以我们就必须具备一种能力,将递归改为非递归

    7910

    C语言中排序算法及其实现方法

    C语言中排序算法及其实现方法排序算法是计算机科学重要部分,它们在数据处理和算法设计起着关键作用。在C语言编程开发,掌握不同排序算法及其实现方法对于提高代码质量和性能至关重要。...本文将围绕C语言中排序算法展开讨论,介绍几种常见排序算法及其实现方法。1C语言中排序算法及其实现方法首先,我们来讨论插入排序算法。插入排序算法核心思想是将待排序元素逐个插入到已排序部分。...快速排序算法通过将一个数组分割为较小和较大两个子数组,然后递归排序子数组,从而实现排序。...,我们对C语言中排序算法及其实现方法有了初步了解。...插入排序、选择排序快速排序和归并排序都是常用排序算法,它们各自有着不同特点和适用场景。在实际应用,我们需要根据具体情况选择最合适排序算法

    15700
    领券