文档章节

[C语言] 交换排序之快速排序的特性及实现

o
 osc_4nmshwhm
发布于 2018/08/06 21:40
字数 527
阅读 19
收藏 0

精选30+云产品,助力企业轻松上云!>>>

[C语言] 交换排序之快速排序的特性及实现

 

1、算法特性

  快速排序是对冒泡排序的一种改进,是一种不稳定的交换排序方法。当数据量庞大且随机无序时,快排是当前最快的排序方式;但当数据量较小、数据基本有序时,快排甚至会退化成冒泡排序。

  其时间复杂度最好、平均情况为O(nlog(2)n)、最差为O(n²),空间复杂度为O(nlog(2)n)。

 

2、算法思路

  以升序排序为例,首先选取一个元素作为基准(通常选取数组两端的元素),通过算法将数组分割成所有元素均小于基准与所有元素均大于等于基准两个部分,这时基准元素处于二者之间,便完成一轮排序。然后再按照以上流程对两个部分分别进行新一轮的排序,通过递归使得整个数组有序。

 

 

 

3、实现代码

 1 #include <stdio.h>
 2 
 3 // 快速排序的基础:每一个数据都应该有一个合适的位置 使左边的数小于或等于这个数,右边的数大于或等于这个数
 4 void _quick_sort(int arr[],int left,int rigth)
 5 {
 6     int key = arr[left];
 7     int i=left;
 8     int j=rigth;
 9     while(j > i)
10     {
11         for(; j>i && arr[j]>=key; j--);// 没有循环体
12         if(j > i)
13             arr[i] = arr[j];
14 
15         for(; j>i && arr[i]<=key; i++);
16         if(j > i)
17             arr[j] = arr[i];    
18     }
19     arr[i] = key;
20     if(i-1 > left)
21         _quick_sort(arr,left,i-1);
22     if(i+1 < rigth)
23         _quick_sort(arr,i+1,rigth);
24 }
25 
26 void quick_sort(int arr[],int len)
27 {
28     _quick_sort(arr,0,len-1);    
29 }
30 
31 void travel(int arr[],int len)
32 {
33     for(int i=0;i<len;i++)
34     {
35         printf("%d ",arr[i]);    
36     }    
37     printf("\n");
38 }
39 
40 int main()
41 {
42     int arr[] = {53,82,9,233,43,14,55,9,4,67};
43     int len = sizeof(arr)/sizeof(arr[0]);
44 
45 /*    travel(arr,len);
46     bubble_sort(arr,len);
47     travel(arr,len);*/
48 
49     travel(arr,len);
50     quick_sort(arr,len);
51     travel(arr,len);
52 
53     return 0;
54 }

 

4、测试结果

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
屌丝的常用排序-----one

排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。 我们这里说说八大排序就是内部排...

技术小胖子
2017/10/30
0
0
数据结构之排序算法(C语言)

一.冒泡排序 冒泡排序是最简单的排序之一了,其大体思想就是通过与相邻元素的比较和交换来把小的数交换到最前面。这个过程类似于水泡向上升一样,因此而得名。举个栗子,对5,3,8,6,4这个无序...

osc_pnw2apz4
2018/03/07
1
0
排序(C语言实现)

读数据结构与算法分析 插入排序 核心:利用的是从位置0到位置P都是已排序的 所以从位置1开始排序,如果当前位置不对,则和前面元素反复交换重新排序 <font color=#FF8247>实现</font> </br>...

osc_xk1o4tx1
2018/09/08
1
0
快速排序你真的会了吗?

原文地址:快速排序优化详解 正如它的名字所体现,快速排序是在实践中最快的已知排序算法,平均运行时间为O(NlogN),最坏的运行时间为O(N^2)。算法的基本思想很简单,然而想要写出一个高效的...

osc_foo7glsg
2019/02/22
5
0
C 实现快速排序

###一、快速排序快速排序可以理解为是对冒泡排序的一种改进,把一组数,按照初始选定的标杆(参照数),分别从两端开始排序,左端'i'只要小于标杆(参照数)的数,右端'j'只要大于标杆(参照...

osc_n86o8vc0
2018/07/31
2
0

没有更多内容

加载失败,请刷新页面

加载更多

MySQL原理 - InnoDB引擎 - 行记录存储 - Redundant行格式

本文基于 MySQL 8 在上一篇:MySQL原理 - InnoDB引擎 - 行记录存储 - Compact格式 中,我们介绍了什么是 InnoDB 行记录存储以及 Compact 行格式,在这一篇中,我们继续介绍其他三种行格式。 ...

zhxhash
23分钟前
11
0
leetcode面试题 17.13(恢复空格)--Java语言实现

求: 哦,不!你不小心把一个长篇文章中的空格、标点都删掉了,并且大写也弄成了小写。像句子"I reset the computer. It still didn’t boot!"已经变成了"iresetthecomputeritstilldidntboo...

拓拔北海
31分钟前
11
0
B站跨年晚会究竟做对了什么?

燃财经(ID:rancaijing)原创 作者 | 赵磊 编辑 | 周昶帆 “补课”是《bilibili晚会 二零一九最美的夜》这个视频中,观众在前两分钟刷得最多的弹幕,寓意着观众是在元旦之后回来补看跨年晚会...

子乾建建_Jeff
01/07
45
0
关于Scrapy爬虫项目运行和调试的小技巧(上篇)

点击上方“Python爬虫与数据挖掘”,进行关注 回复“书籍”即可获赠Python从入门到进阶共10本电子书 今 日 鸡 汤 迟日江山丽,春风花草香。泥融飞燕子,沙暖睡鸳鸯。 扫除运行Scrapy爬虫程序...

yuhan336
04/02
26
0
Top50ggplot2Visualizations_第2幅:面积图

第一部分 公众号里有朋友提问——在散点图添加拟合曲线的图中如何添加一条虚线对角线? image.png 就是由图A变成图B;应该有很多方法可以实现,这里我使用geom_segment()函数 geom_segment()...

pome24
2019/12/20
9
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部