排序算法(四)--快速排序

devtools/2024/11/23 12:06:27/

文章目录

  • 引言
  • 快速排序的基本原理
  • C语言实现快速排序
  • 代码解析

快速排序 C语言实例

引言

快速排序(Quicksort)作为一种高效的算法>排序算法,以其平均时间复杂度为O(n log n)而著称。

快速排序的基本原理

快速排序的核心思想是分治法(Divide and Conquer)。它的基本步骤如下:
选择基准(Pivot):从待排序数组中选取一个元素作为基准。
分区(Partition):重新排列数组,使得所有比基准小的元素都在基准前面,所有比基准大的元素都在基准后面。基准元素在其最后的排序数组中的位置就已经被确定。
递归排序(Recursively Sort):递归地将小于基准值元素的子数组和大于基准值元素的子数组排序。

C语言实现快速排序

以下是一个用C语言实现的快速排序实例:
#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++) {
// 如果当前元素小于或等于基准
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是分区索引,arr[pi]已经排好序
int pi = partition(arr, low, high);
// 分别对左右子数组进行排序
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
// 打印数组
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++) {
printf(“%d “, arr[i]);
}
printf(”\n”);
}
// 主函数
int main() {
int arr[] = {10, 7, 8, 9, 1, 5};
int n = sizeof(arr) / sizeof(arr[0]);
printf(“未排序数组: \n”);
printArray(arr, n);
quickSort(arr, 0, n - 1);
printf(“排序后数组: \n”);
printArray(arr, n);
return 0;
}

代码解析

swap函数:用于交换数组中的两个元素。
partition函数:选择最右边的元素作为基准,通过遍历数组,将所有小于或等于基准的元素移动到基准的左边,所有大于基准的元素移动到基准的右边。最后返回基准元素的正确位置。
quickSort函数:递归地对分区后的子数组进行排序。
printArray函数:用于打印数组元素。
main函数:定义了一个待排序数组,调用快速排序函数并打印排序前后的数组。


http://www.ppmy.cn/devtools/136284.html

相关文章

直播服务器多设备同显方案

在直播行业中&#xff0c;服务器多设备同显方案已成为一种创新且高效的技术应用。这一技术不仅能够满足大规模同步直播的需求&#xff0c;还能显著提升观众的观看体验和参与度。本文将深入探讨直播服务器多设备同显方案的技术细节、实施步骤以及在不同场景下的应用价值。 直播服…

基于无线传感器网络的无线温湿度采集系统(附详细使用教程+完整代码+原理图+完整课设报告)

&#x1f38a;项目专栏&#xff1a;【Zigbee课程设计系列文章】&#xff08;附详细使用教程完整代码原理图完整课设报告&#xff09; 前言 &#x1f451;由于无线传感器网络&#xff08;也即是Zigbee&#xff09;作为&#x1f310;物联网工程的一门必修专业课&#xff0c;具有…

LRU缓存

什么是LRU缓存? LRU&#xff08;Least Recently Used&#xff09;是最近最少使用算法&#xff0c;是操作系统中用于分页置换的算法&#xff0c;如果要向内存中添加分页&#xff0c;并且内存分页已满的情况下&#xff0c;就选出最近一段时间最不常用的分页进行置换&#xff08;…

七次课掌握 Photoshop:绘画与修饰

Photoshop 提供了丰富的绘画和修饰工具&#xff0c;帮助我们在数字图像中进行创作和润色。熟练掌握这些工具和方法&#xff0c;可以提升我们的图像处理和设计水平。 一、绘画类工具 1、画笔工具 快捷键&#xff1a;B 画笔工具 Brush Tool是 Photoshop 中最基本的绘画工具&#…

全新三网话费余额查询API系统源码 Thinkphp全开源 附教程

全新三网话费余额查询API系统源码 thinkphp全开源 附教程 本套系统是用thinkphp6.0框架开发的,PHP版本需8.1以上,可查询手机号话费余额、归属地和运营商等信息,系统支持用户中心在线查询和通过API接口对接发起查询,用户余额充值是对接usdt接口或者通过后台生成卡密,源码全…

利用 GitHub 和 Hexo 搭建个人博客【保姆教程】

利用 GitHub 和 Hexo 搭建个人博客 利用 GitHub 和 Hexo 搭建个人博客一、前言二、准备工作&#xff08;一&#xff09;安装 Node.js 和 Git&#xff08;二&#xff09;注册 GitHub 账号 三、安装 Hexo&#xff08;一&#xff09;创建博客目录&#xff08;二&#xff09;安装 H…

【Linux】详解shell代码实现(上)

&#x1fa90;&#x1fa90;&#x1fa90;欢迎来到程序员餐厅&#x1f4ab;&#x1f4ab;&#x1f4ab; 主厨&#xff1a;邪王真眼 主厨的主页&#xff1a;Chef‘s blog 所属专栏&#xff1a;青果大战linux 总有光环在陨落&#xff0c;总有新星在闪烁 学校开始搞蓝桥的校选…

【数据结构】树——链式存储二叉树的基础

写在前面 书接上文&#xff1a;【数据结构】树——顺序存储二叉树 本篇笔记主要讲解链式存储二叉树的主要思想、如何访问每个结点、结点之间的关联、如何递归查找每个结点&#xff0c;为后续更高级的树形结构打下基础。不了解树的小伙伴可以查看上文 文章目录 写在前面 一、链…