首页 > 其他分享 >排序------快速排序(C语言实现)

排序------快速排序(C语言实现)

时间:2024-08-25 22:25:37浏览次数:13  
标签:int 基准 元素 C语言 数组 ------ 排序 快速

目录

快速排序算法

例题

题目描述

具体代码:

代码分析

函数定义:

主函数:


快速排序算法

快速排序(QuickSort)是一种高效的排序算法,它采用分治策略,通过选择一个“基准”元素并将其他元素重新排列为两部分,一部分小于基准,另一部分大于基准,然后递归地对这两部分进行排序。快速排序的基本步骤包括:

  1. 选择基准:从数组中选择一个元素作为基准。常见的选择方法有选择第一个元素、最后一个元素、随机选择或中间元素。
  2. 分区:将数组划分为两部分,使得所有小于基准的元素都在基准的左边,所有大于基准的元素都在基准的右边。分区后,基准元素位于其最终排序位置。
  3. 递归排序:对基准元素左边和右边的子数组分别进行快速排序,直到子数组的大小为1或0。

快速排序的平均时间复杂度为O(n log n),但在最坏情况下,如果每次选择的基准元素都导致极端不平衡的划分,时间复杂度会退化到O(n²)。为了避免最坏情况,可以采用随机化选择基准或“三数取中”策略。

空间复杂度方面,快速排序的空间复杂度主要取决于递归调用的栈空间,平均情况下为O(log n)。

快速排序在实际应用中广泛使用,因为它通常比其他O(n log n)算法更快,且在内存使用上是原地排序算法. 

例题

题目描述


快速排序是一种常见的排序方式,但是你知道这个排序是怎么实现的吗?现在要求你不使用库函数,实现快速排序。

输入格式
第一行输入一个整数 n,表示数列的长度。
第二行输入 n 个数,表示数列中的元素。

输出格式
输出 n 个数,表示排好序的数列。

输入输出样例
输入
4
4 3 2 1

输出
1 2 3 4

样例说明
4 3 2 1
排序结束是
1 2 3 4

具体代码:

#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 - 1; j++) {
        // 当前元素小于或等于pivot
        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) {
        // pi是分区后的基准元素索引
        int pi = partition(arr, low, high);

        // 递归排序基准元素左右两侧的子数组
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

int main() {
    int n;
    scanf("%d", &n);
    int arr[n];
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }

    quickSort(arr, 0, n - 1);

    for (int i = 0; i < n; i++) {
        printf("%d", arr[i]);
        if (i < n - 1) {
            printf(" ");
        }
    }
    printf("\n");

    return 0;
}

代码分析

  1. 函数定义

    • swap:交换两个整数变量的值。
    • partition:选择基准,将数组划分,并返回基准的最终位置。
    • quickSort:递归地进行快速排序。
  2. 主函数

    • 读取输入的n,然后读取n个整数到数组arr中。
    • 调用quickSort函数对arr进行排序。
    • 输出排序后的数组元素。

标签:int,基准,元素,C语言,数组,------,排序,快速
From: https://blog.csdn.net/markingyi/article/details/141535066

相关文章

  • Shopee虾皮api python获取商品买家评论数据信息
    此api接口可用于获取虾皮平台商品买家评论信息,目前land参数支持id、vn、my、th、sg、ph、tw(印尼、越南、马来、泰国、新加坡、菲律宾、台湾)。若有需要,请点击文末链接联系我们。详细采集页面如下https://shopee.tw/%E9%99%8D%E5%83%B9%E5%85%8D%E9%81%8B%E4%B8%AD%F0%9F%94%A5......
  • Shopee虾皮api python获取虾皮购物平台的商品数据信息 数据采集
    虾皮购物(英语:Shopee)是一个电商平台,总公司设在新加坡,归属于SeaGroup(之前称之为Garena),该企业于2009年由李小冬(ForrestLi)创办。虾皮购物于2015年初次在新加坡推出,现阶段已拓展到马来西亚、泰国、印度尼西亚、越南和菲律宾。虾皮购物为全球华人地区的客户提供线上购物和销售......
  • 【深度学习】文本张量表示方法
    1文本张量表示将一段文本使用张量进行表示,其中一般将词汇为表示成向量,称作词向量,再由各个词向量按顺序组成矩阵形成文本表示.举个例子:["人生","该","如何","起头"]==>#每个词对应矩阵中的一个向量[[1.32,4,32,0,32,5.2],[3.1,5.43,0.34,3.2],[3.21,......
  • 函数qsort的使用与冒泡排序模拟实现qsort
    目录一.qsort函数的使用示例二.使用冒泡排序模拟实现qsort函数二.1.冒泡排序 二.2.模拟实现qsort函数一.qsort函数的使用1.1.qsort函数是用来排序任意数据类型的数组,对其中的元素进行一定规则的排列2.qsort不返回任何值3.qsort的第一个参数是一个void*指针,指向......
  • 【Rust光年纪】文本分析利器:探索Rust语言的多功能文本处理库
    从情感分析到关键词提取:Rust语言文本分析库详解前言随着自然语言处理技术的不断发展,对各种文本数据进行分析和处理的需求也在不断增加。本文将介绍一些用于Rust语言的文本分析和处理库,包括情感分析、自然语言处理、中文转换、语言检查和关键词提取等方面的工具和资源。......
  • 判断与循环——循环结构
    for,while一、for循环1.格式:for(a.初始化语句;b.条件判断语句;c.条件控制语句){    d.循环体语句;}2.a.循环开始条件(只执行一次) b.循环结束条件(为true 循环继续)c.变量i如何变化d.要重复执行的代码intsum=0;for(inti=1;i<=5;i++){        sum+=i......
  • Python从0到100(五十三):决策树及决策树分类器
    决策树是⼀种常⽤的监督学习算法,⽤于解决分类和回归问题。它的基本原理是根据数据的特征来构建⼀颗树状结构,树的每个节点代表⼀个特征,每个分⽀代表⼀个特征的取值,叶节点代表输出类别或数值。决策树的⽬标是通过分裂特征,将数据集划分为纯度更⾼的⼦集,以最⼩化误差或不纯度......
  • Python从0到100(五十四):K近邻算法及⼿写数字识别数据集分类
    K最近邻(K-NearestNeighbors,简称KNN)是⼀种常⽤的监督学习算法,主要⽤于分类和回归问题。KNN的基本原理是基于特征空间中样本点的距离来进⾏预测或分类。对于分类问题,KNN找到与待分类样本在特征空间中最近的K个训练样本,并基于它们的类别标签进⾏投票决策。对于回归问题,KNN找......
  • 【有源码】基于python的国内地震数据可视化分析与预测系统hadoop项目hive计算机程序设
    注意:该项目只展示部分功能,如需了解,文末咨询即可。本文目录1.开发环境2系统设计2.1设计背景2.2设计内容3系统展示3.1功能展示视频3.2页面页面4更多推荐5部分功能代码1.开发环境开发语言:Python采用技术:K-means算法数据库:MySQL开发环境:PyCharm2系统......
  • C语⾔内存函数
    文章目录1.memcpy使用和模拟实现memcpy的使用:memcpy的模拟实现:2.memmove使用和模拟实现memmove的使用:memmove的模拟实现:3.memset函数的使⽤4.memcmp函数的使用1.memcpy使用和模拟实现void*memcpy(void*destination,constvoid*source,size_tnum);......