图解快速排序
C语言题库
共 2723字,需浏览 6分钟
· 2021-09-17
01
—
快速排序原理
快速排序用到了分治的思想,主要分为三步分治过程:
数组A[p..r]被划分为两个子数组A[p..q-1]和A[q+1..r],使得A[p..q-1]中的每一个元素都小于A[q],而A[q+1..r]的每一个元素大于等于A[q],计算分割点q也是过程的一部分。
递归对A[p..q-1]进行划分直到无法划分为止,则A[p..q-1]处于有序状态,且每一个元素小于A[q]。同样的递归对A[q+1..r]进行划分直到无法划分为止,则A[q+1..r]处于有序状态,且每一个元素大于等于A[q]。
—
快速排序实现
经过一轮分割得到q位置作为分割点,A[p..q-1]序列小于A[q]而A[q+1..r]大于等于A[q]。后面不断分别对A[p..q-1]和A[q+1..r]进行递归划分则得到一个有序序列A[p..r]。
快速排序操作函数声明如下:
typedef int data_type_t;
extern void quick_sort(data_type_t *A, int p, int r);
static void swap(data_type_t *x, data_type_t *y){
if(x == NULL || y == NULL){
return;
}
data_type_t temp = *x;
*x = *y;
*y = temp;
}
static int partision(data_type_t *A, int p, int r){
data_type_t x = A[r]; //以最后一个元素作为主元
int i = p - 1;
int j = p;
while(j < r){
if(A[j] < x){
i++;
swap(&A[j], &A[i]); //比主元大的数放右边,小的数放在数组左边。
}
j++;
}
swap(&A[++i], &A[r]); //主元作为分割点
return i; //返回当前分割点位置
}
快速排序实现代码如下:
void quick_sort(data_type_t *A, int p, int r){
if(p >= r){
return;
}
int q = partision(A, p, r);
quick_sort(A, p, q - 1);
quick_sort(A, q + 1, r);
}
—
算法验证
下面我们写一个小程序验证算法的正确性。
#include <stdio.h>
#include "quick_sort.h"
int main() {
int arr[10] = {8, 3, 5, 9, 1, 2, 78, 32, 6, 8};
quick_sort(arr, 0, 9);
int i = 0;
for(i = 0; i < 10; i++){
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
编译输出结果如下:
1 2 3 5 6 8 8 9 32 78
算法完全正确。
评论
图解 transformer 中的自注意力机制
↓推荐关注↓本文将将介绍注意力的概念从何而来,它是如何工作的以及它的简单的实现。注意力机制在整个注意力过程中,模型会学习了三个权重:查询、键和值。查询、键和值的思想来源于信息检索系统。所以我们先理解数据库查询的思想。假设有一个数据库,里面有所有一些作家和他们的书籍信息。现在我想读一些Rabindra
Python学习与数据挖掘
0
Spring Boot + flowable 快速实现工作流
关注我们,设为星标,每天7:40不见不散,架构路上与您共享回复架构师获取资源大家好,我是你们的朋友架构君,一个会写代码吟诗的架构师。来源:blog.csdn.net/zhan107876/article/details/120815560总览一、flowable-ui部署运行二、绘制流程图绘图细节:
Java架构师社区
0
图解操作系统、网络、计算机组成PDF下载!
我去年去面试的时候发现字节跳动、腾讯这类大厂非常非常重视计算机基础,像计算机网络、操作系统都是它们的重点。我当时因为计算机基础知识准备的还可以才拿到了这些大厂的 Offer!今天就给大家分享一下我之前面试经常看的一些关于计算机基础的 PDF 资料!图解计算机系统《图解系统》主要是操作系统的内容比较多
java1234
0
2025年有望破万亿,AIoT助力下,物流行业正在迎来快速发展
作者:王飞鹏物联网智库 原创3月底,正在赶赴港股上市的菜鸟网络被阿里总部召回,上市进程按下了暂停键。在阿里去年定下“大拆分”战略后,菜鸟本是最有希望率先独立IPO的企业,但是在临门一脚之际,阿里却做出了不上市的决策。这一举动引发了外界热议。分析人士普遍认为,阿里之所以做出这一决策,很重要的一个原因是
物联网智库
0
图解 SQL 执行顺序,通俗易懂!
来源:blog.csdn.net/weixin_44141495/article/details/108744720/数据的关联过程from&join&wheregroup byhaving&whereselectorder bylimit这是一条标准的查询语句:图片这是我们
Java专栏
10
Linux服务器大量log日志,如何正确看日志快速定位错误?
针对大量log日志快速定位错误地方动态查看日志tail -f catalina.ou从头打开日志文件cat catalina.ou可以使用 >nanjiangtest.txt 输出某个新日志去查看[root@yesky logs]# cat&n
Java专栏
10
Gin 框架介绍与快速入门
目录Gin 框架介绍与快速入门1.gin.Engine2.gin.Context1.安装2.导入3.第一个Gin 应用1. 快速和轻量级2. 路由和中间件3. JSON解析4. 支持插件5. Gin相关文档一、Gin框架介绍二、基本使用三、应用举例四、Gin 入门核心...
马哥Linux运维
0
《认知觉醒》想要快速成为一个行业的高手,最好的办法就是和行业专...
《认知觉醒》中说:“想要快速成为一个行业的高手,最好的办法就是和行业专家交流,直接向他们请教。 未来学家凯文 凯利的一位朋友想进入一个全新的领域,但是他没有任何经验。于是他就参加该领域内的各种行业会议,...
胖琪的升级之路
0