首页
学习
活动
专区
工具
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; } ---- 非递归实现 递归算法主要是在划分子区间,如果要非递归实现快排,只要使用一个栈来保存区间就可以了。

77130

快速排序算法思路分析和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.4K70

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

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

75700

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

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

9810

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

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

12210

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

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

10410

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

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

1.6K10

排序算法在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时就会直接使用插入排序 选择五个均匀间隔元素作为使用不同快速排序方法判断标准 如果五个元素互不相等那么使用双轴快速排序(两个枢轴为

1K30

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次。

68240

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

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

74860

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

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

12500

java开发C语言编译器:把C实现快速排序算法编译成jvm字节码

在本节,我们将用C语言开发快速排序算法,然后利用我们编译器把它编译成java字节码,让C语言编写快速排序算法能在java虚拟机上顺利执行,完成本节内容后,编译器可以正确将下列代码编译成java字节码...《算法导论》所编写实现快速排序算法,主函数先初始化一个乱序数组,然后通过调用quicksort函数实现排序。...我一直把编译器能够解释编译C语言快速排序代码作为章节终点,一来快速排序算法实现包含了循环,ifelse分支判断,递归等编程语言关键要素,能正确解释和编译它意味着编译器达到了一定成熟度。...而本节完成后,我们编译器能正确编译快速排序C语言实现后,整个编译器实现课程经历两年时光,也该画上句号了。 我们看看代码实现,这次代码与前面代码一大不同之处就是函数递归调用。...,如果函数体内发送递归调用,那么编译器还会再次进入到 * 这里,如果进入时判断到函数名跟我们这里存储函数名一致,那表明发生了递归调用。

69820

【数据结构和算法】--- 基于c语言排序算法实现(2)

div - 1); // 递归排[div + 1, end] QuickSort(a, div + 1, end); } 上述为快速排序递归实现主框架,发现与二叉树前序遍历规则非常像,我们可以参照二叉树前序遍历...(如有疑问请参考:【数据结构和算法】— 二叉树(3)–二叉树链式结构实现(1))规则即可快速写出来,后序只需分析如何按照基准值来对区间中数据进行划分方式即可。...1.4 快排非递归版 根据递归版快排特性,相当于二叉树前序遍历,那么我们便可利用栈后进先出特性,来模拟递归实现排序,栈实现还请参考:【数据结构和算法】— 栈。...快排非递归整体逻辑大致如下: 在实现时我们要先创建栈并初始化,然后进栈一对数据(整个待排序数组下标范围), 以!STEmpty(&s)作为循环条件,当栈无节点时,便会结束。...两种排序递归写法,本质上与二叉树遍历极其相似。区别在于快速排序递归相当于二叉树前序遍历,可以利用栈后进先出特性来实现;而归并排序相当于二叉树后序遍历,只能用循环来模拟实现

8410

【数据结构和算法】--- 基于c语言排序算法实现(1)

稳定性: 假定在待排序记录序列,存在多个具有相同关键字记录,若经过排序,这些记录相对次序保持不变,即在原序列,r[i]=r[j],且r[i]在r[j]之前,而在排序序列,r[i]仍在r...此处排序便是由排序算法实现,下面将对不同排序算法进行剖析。 1.3 常见排序算法 下面将基于c语言,对以上七种排序逐一实现。...希尔排序时间复杂度不好计算,因为gap取值方法很多,导致很难去计算,因此在好些书中给出希尔排序时间复杂度都不固定: 《数据结构(C语言版)》— 严蔚敏 《数据结构-用面相对象方法与C+...实际很少使用 时间复杂度: O(N^2) 空间复杂度: O(1) 稳定性: 不稳定 3.2 堆排序排序(Heapsort)是指利用堆积树(堆)这种数据结构所设计一种排序算法,它是选择排序一种。...因为之前已经介绍过了,所以这里就不多讲了,详细请参考:【数据结构和算法】—二叉树(2)–堆实现和应用 直接选择排序特性总结: 堆排序使用堆来选数,效率就高了很多。

5710
领券