【排序 - 快速排序】

快速排序(Quick Sort)是一种高效的排序算法,它基于分治(Divide and Conquer)的策略。这种排序算法的核心思想是选择一个基准元素,将数组分割成两部分,使得左边的元素都小于等于基准元素,右边的元素都大于等于基准元素,然后对这两部分分别递归地应用快速排序。

算法步骤:

  1. 选择基准元素:从数组中选择一个元素作为基准(pivot)。通常选择第一个元素、最后一个元素或者随机一个元素作为基准。

  2. 分区(Partition):重新排列数组,使得比基准元素小的元素都在基准元素的左边,比基准元素大的元素都在右边。同时,基准元素位于最终排序的位置。

  3. 递归排序:递归地对基准元素左右两边的子数组进行快速排序。
    在这里插入图片描述

实现步骤:

下面是用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;  // 初始化分区索引,比基准元素小的元素会放在左边

    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 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函数:实现快速排序的递归算法。在每次递归中,先使用partition函数将数组分区,然后递归地对分区后的两部分进行排序。
  • printArray函数:用于打印数组元素,方便查看排序结果。
  • main函数:测试快速排序的实现,打印排序前和排序后的数组。

时间复杂度:

快速排序的时间复杂度主要取决于分区操作的时间复杂度和递归调用的次数。在最坏情况下,快速排序的时间复杂度为 O(n^2),但在平均情况下为 O(n log n),这使得它成为一种高效的排序算法。

总结:

快速排序通过分治策略和分区操作,实现了高效的排序。它不需要额外的存储空间(除了递归调用时的栈空间),并且在平均情况下具有较好的性能表现。因此,快速排序是实际应用中常用的排序算法之一,尤其适合大数据集的排序任务。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/791102.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

实验-ENSP实现防火墙区域策略与用户管理

目录 实验拓扑 自己搭建拓扑 实验要求 实验步骤 整通总公司内网 sw3配置vlan 防火墙配置IP 配置安全策略&#xff08;DMZ区内的服务器&#xff0c;办公区仅能在办公时间内&#xff08;9: 00- 18:00)可以访问&#xff0c;生产区的设备全天可以访问&#xff09; 配置nat策…

(总结)编译ORB_SLAM2遇到的错误

目录 第一个错误error: ‘CV_BGR2GRAY’ was not declared in this scope 第二个错误error: ‘CV_GRAY2BGR’ was not declared in this scope 第三个错误是没有那个文件或目录 26 | #include 第四个错误是‘CV_LOAD_IMAGE_UNCHANGED’ was not declared in this scope 第…

Golang | Leetcode Golang题解之第228题汇总区间

题目&#xff1a; 题解&#xff1a; func summaryRanges(nums []int) (ans []string) {for i, n : 0, len(nums); i < n; {left : ifor i; i < n && nums[i-1]1 nums[i]; i {}s : strconv.Itoa(nums[left])if left < i-1 {s "->" strconv.It…

腾讯广告优量汇Android一面凉经(2024)

腾讯广告优量汇Android一面凉经(2024) 笔者作为一名双非二本毕业7年老Android, 最近面试了不少公司, 目前已告一段落, 整理一下各家的面试问题, 打算陆续发布出来, 供有缘人参考。今天给大家带来的是《腾讯广告优量汇Android一面凉经(2024)》。 面试职位: 腾讯广告优量汇-SDK客…

【算法】排序算法介绍 附带C#和Python实现代码

1. 冒泡排序(Bubble Sort) 2. 选择排序(Selection Sort) 3. 插入排序(Insertion Sort) 4. 归并排序(Merge Sort) 5. 快速排序(Quick Sort) 排序算法是计算机科学中的一个基础而重要的部分,用于将一组数据按照一定的顺序排列。下面介绍几种常见的排序算法,…

MVC分页

public ActionResult Index(int ? page){IPagedList<EF.ACCOUNT> userPagedList;using (EF.eMISENT content new EF.eMISENT()){第几页int pageNumber page ?? 1;每页数据条数&#xff0c;这个可以放在配置文件中int pageSize 10;//var infoslist.C660List.OrderBy(…

算法通关:004_1选择排序

代码一定要自己手敲理解 public class _004 {//选择排序&#xff0c;冒泡排序&#xff0c;插入排序//交换public static void swap(int[] arr,int i ,int j){int temp arr[i];arr[i] arr[j];arr[j] temp;}//选择排序public static void selectSort(int[] arr){if(arr null…

PDF 分割拆分 API 数据接口

PDF 分割拆分 API 数据接口 文件处理&#xff0c;PDF 高效的 PDF 分割工具&#xff0c;高效处理&#xff0c;可永久存储。 1. 产品功能 高效处理大文件&#xff1b;支持多语言字符识别&#xff1b;支持 formdata 格式 PDF 文件流传参&#xff1b;支持设置每个 PDF 文件的页数…

【PTA天梯赛】L1-005 考试座位号(15分)

作者&#xff1a;指针不指南吗 专栏&#xff1a;算法刷题 &#x1f43e;或许会很慢&#xff0c;但是不可以停下来&#x1f43e; 文章目录 题目题解try1 编译错误正确题解 总结 题目 题目链接 题解 try1 编译错误 #include<bits/stdc.h> using namespace std;typedef…

nginx正向代理、反向代理、负载均衡

nginx.conf nginx首要处理静态页面 反向代理 动态请求 全局模块 work processes 1; 设置成服务器内核数的两倍&#xff08;一般不不超过8个超过8个反而会降低性能一般4个 1-2个也可以&#xff09; netstat -antp | grep 80 查端口号 *1、events块&#xff1a;* 配置影响ngi…

微软Win11 24H2七月更新补丁KB5040435发布!附下载

系统之家于7月10日发出最新报道&#xff0c;微软为Win11用户发布了24H2版本七月的最新更新补丁KB5040435。用户升级系统后&#xff0c;会发现版本号升至 26100.1150。此次更新针对远程身份验证拨入用户服务(RADIUS)协议与 MD5冲突等问题进行修复。接下来跟随小编看看此次更新的…

利用【Python】【线性规划】优化工厂生产:实现智能资源配置与利润最大化的现代解决方案

目录 1. 问题背景和描述 1.1 问题背景 1.2 问题描述 2. 数学模型的建立 2.1决策变量 2.2 目标函数 2.3 约束条件 2.4 数学模型总结 3. 使用Python解决线性规划问题 3.1 导入必要的库 3.2 定义目标函数系数 3.3 定义不等式约束矩阵和向量 3.4 定义变量的边界 非负…

【Pytorch】RNN for Image Classification

文章目录 1 RNN 的定义2 RNN 输入 input, h_03 RNN 输出 output, h_n4 多层5 小试牛刀 学习参考来自 pytorch中nn.RNN()总结RNN for Image Classification(RNN图片分类–MNIST数据集)pytorch使用-nn.RNN 1 RNN 的定义 nn.RNN(input_size, hidden_size, num_layers1, nonlinea…

游戏视频是后期配音好还是边录边配 游戏视频怎么剪辑制作才能火 视频剪辑免费软件

游戏视频后期配音是先配还是先剪&#xff1f;游戏视频后期配音没有统一的准则&#xff0c;可以先配&#xff0c;也可以后配&#xff0c;主要是根据内容而定。游戏视频剪辑在游戏玩家中十分流行&#xff0c;那么&#xff0c;游戏视频怎么剪辑制作&#xff1f;下面让我们以具体的…

apache python使用

修改httpd.conf文件。 AddHandler cgi-script .cgi .py 代码 #!自己的python.exe #-*- coding:UTF-8 -*- print ("Content-type:text/html") print () print (<html>) print (<head>) print (<meta charset"gb2312">) print (<tit…

现在国内的ddos攻击趋势怎么样?想了解现在ddos的情况该去哪看?

目前&#xff0c;国内的DDoS攻击趋势显示出以下几个特征&#xff1a; 攻击频次显著增加&#xff1a;根据《快快网络2024年DDoS攻击趋势白皮书》&#xff0c;2023年DDoS攻击活动有显著攀升&#xff0c;总攻击次数达到1246.61万次&#xff0c;比前一年增长了18.1%。 攻击强度和规…

Spring Expression表达式使用

Spring Expression 简介 Spring Expression Language&#xff08;简称 “SpEL”&#xff09;是一种功能强大的表达式语言&#xff0c;支持在运行时查询和操作对象图。其中最显著的是&#xff1a;方法调用和基本的字符串模板功能。 虽然SpEL是Spring产品组合中表达式评估的基础…

树莓派pico入坑笔记,ssd1306使用

目录 说明 后附进阶玩法&#xff1a;显示中文&#xff0c;外加简单库实现 官方模块使用 使用样例 方法说明 下面是绘图支持的方法 进阶玩法&#xff0c;显示中文 方法&#xff0c;对汉字取字模&#xff0c;然后按像素对字模进行显示 说明 circuitpython8.x使用iic接口驱…

链表 OJ(一)

移除链表元素 题目连接&#xff1a; https://leetcode.cn/problems/remove-linked-list-elements/description/ 使用双指针法&#xff0c;开始时&#xff0c;一个指针指向头节点&#xff0c;另一个指针指向头节点的下一个结点&#xff0c;然后开始遍历链表删除结点。 这里要注…

YOLOv10改进 | Conv篇 | CVPR2024最新DynamicConv替换下采样(解决低FLOPs陷阱)

一、本文介绍 本文给大家带来的改进机制是CVPR2024的最新改进机制DynamicConv其是CVPR2024的最新改进机制&#xff0c;这个论文中介绍了一个名为ParameterNet的新型设计原则&#xff0c;它旨在在大规模视觉预训练模型中增加参数数量&#xff0c;同时尽量不增加浮点运算&#x…