首页
学习
活动
专区
工具
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.6K30
  • 快速排序算法思路分析和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

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

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

    54910

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

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

    21610

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

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

    18010

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

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

    82400

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

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

    12410

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

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

    2.2K10

    快速排序算法的原理与实现

    快速排序算法的原理与实现 快速排序是一种高效的排序算法,其基本思想是使用分治策略将一个大问题分解为两个在某种程度上相等的小问题,然后递归解决这些小问题,最后将这些小问题的解合并得到原问题的解。...让我们通过以下C++代码来理解快速排序的原理: #include using namespace std; const int N = 1e6 + 10; int q[N]; void...quick_sort (q, 0, n - 1); for (int i = 0; i < n; ++i) printf ("%d ", q[i]); return 0; } 这段代码实现了一个基本的快速排序算法...然后,我们定义了一个函数quick_sort,这是我们的主要排序函数。 在quick_sort函数中,我们首先检查是否有需要排序的元素。...当while循环结束后,我们就完成了一次分区操作,此时数组被x分为了两部分,左边的元素都小于x,右边的元素都大于x。 最后,我们递归地对x左边和右边的子数组进行快速排序。这样,整个数组就被排序了。

    8610

    排序算法在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; } 总结 快速排序是一种高效且常用的排序算法

    21410

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

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

    78060

    实现一个二分搜索算法,搜索指定元素在已排序数组中的位置。(递归或者非递归实现)

    实现一个二分搜索算法,搜索指定元素在已排序数组中的位置。(递归或者非递归实现) 简介:实现一个二分搜索算法,搜索指定元素在已排序数组中的位置。...(递归或者非递归实现) 算法思路 算法思路 二分查找是一种在有序数组中查找特定元素的搜索算法。该算法对数组进行比较次数的上限是 O(log n)。...,在实现中我们使用递归方式进行查找。...同时,递归方式的实现还需要注意满足递归退出条件。当当前查找区间[l, r]变成[low, high]时,如果high 递归方式的实现还需要注意满足递归退出条件。当当前查找区间[l, r]变成[low, high]时,如果high < low,则说明不存在目标元素,返回-1即可。

    3500

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

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

    8410
    领券