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

server/2024/12/22 20:18:05/

目录

快速排序算法-toc" style="margin-left:0px;">快速排序算法

例题

题目描述

具体代码:

代码分析

函数定义:

主函数:


快速排序算法">快速排序算法

快速排序(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++) {// 当前元素小于或等于pivotif (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进行排序。
    • 输出排序后的数组元素。

http://www.ppmy.cn/server/107872.html

相关文章

Vue学习--- vue3 集成遇到的部分问题与解决

构建异常 1. 问题&#xff1a;ESLint: Do not access Object.prototype method hasOwnProperty from target o 报错解释&#xff1a; ESLint 报错信息 "Do not access Object.prototype method hasOwnProperty from target object" 指的是不应该从目标对象访问 Ob…

轻量级冠军:NVIDIA 发布具有领先准确率的小语言模型

Mistral-NeMo-Minitron 8B 是最近发布的 Mistral NeMo 12B 模型的微型版本&#xff0c;具有高精度和高计算效率&#xff0c;可在 GPU 加速数据中心、云和工作站上运行模型。 生成式 AI 开发者通常需要在模型尺寸和准确性之间做出权衡。然而&#xff0c;NVIDIA 发布的一款新语言…

Android Studio Koala下载并安装,测试helloworld.

1、下载&#xff1a; 下载 Android Studio 和应用工具 - Android 开发者 | Android Developers 2、滚动条拉到近最后&#xff0c;各个系统的下载地址&#xff1a; 3、下载完成以后&#xff0c;我们双击运行安装&#xff1a; 如果有路径要修改&#xff0c;则修改下就可以了&a…

【机器学习】西瓜书第一章 绪论

参考资料&#xff1a;[1]周志华.机器学习[M].清华大学出版社,2016. 一、引言 我们生活中存在许多基于经验做出的判断&#xff0c;比如月明星稀&#xff0c;那第二天可能会是好天气&#xff1b;一个西瓜敲起来声音响&#xff0c;色泽也不错&#xff0c;大概率是一个好瓜。 我…

React Hook Form:指南与示例

表单是用户与网站和Web应用程序交互的重要组成部分。验证用户通过表单提交的数据是开发者的一项关键职责。 React Hook Form是一个帮助在React中验证表单的库。它是一个没有其他依赖项的精简库&#xff0c;性能优越&#xff0c;使用简单&#xff0c;开发者可以比使用其他表单库…

CTFHub SSRF靶场通关攻略

内网访问 首先进入环境 在url后面输入 http://127.0.0.1/flag.php访问&#xff0c;得出flag 伪协议读取文件 进入环境后再url后面拼接 file:///var/www/html/flag.php 访问后是&#xff1f;&#xff1f;&#xff1f;&#xff0c;那么我们F12检查源码得出flag 端口扫描 我们进行…

服务保护方案Sentinel

微服务雪崩问题 微服务调用链路中某个服务故障&#xff0c;导致tomcat资源耗尽&#xff0c;引起整个链路中的所有微服务都不可用&#xff0c;这就是微服务的雪崩。 解决方案 请求限流 线程隔离 服务熔断 Sentinel 认识Sentinel 下载jar包 可以下载jar包&#xff0c;wind…

Pytest项目搭建总结

以接口自动化项目为例 打开终端依次输入如下命令&#xff1a; mkdir PytestDemo cd PytestDemo #创建Python项目虚拟环境 python -m venv .env #激活虚拟环境 source .env/bin/activate #安装第三方库 pip install requests pip install pytest pip install pytest-html pip …