常见的五类排序算法图解和实现(交换类:冒泡排序,递归的快速排序)

简介:

冒泡排序算法:

总的来说就是两两交换,反复直到有序,第一个记录和第二个记录,若逆序则交换,然后比较第二个和第三个记录,以此类推,直到第 n 个记录和第 n-1个记录比较完毕为止,第一趟排序,结果关键字最大的记录被安排在最后一个位置。对前 n-1个记录继续冒泡排序,使得关键字次大的记录安排在第 n-1个位置。如此重复,直到没有需要交换的记录为止(仅仅是第一个和第二个交换过为止)。整个一趟趟的选出最值的过程,仿佛是那水里的气泡,咕嘟咕嘟的往上翻的过程。

递增冒泡排序过程图解:

一般先比较第一个元素和第二个元素,49大于38,则交换之,且需要提前取出元素49到临时存放处

            

移动元素,实现两个数的交换

  

继续两两比较,49小于65,无需交换,65小于97,无需交换,比较97和76,交换,97和13比较交换,97和27比较交换,97和49比较交换。

第一趟排序完毕,把最大的97元素冒泡到了最后。接下来继续第二趟排序,每次都是如此往复。每次都得到本趟次排序的最值。

代码如下;

复制代码
 1 //递增冒泡排序算法实现
 2 void bubbleSort(int list[], int len)
 3 {
 4     int i = len;
 5     int j = 0;
 6     int k = 0;
 7     //排序终止的条件
 8     while (i > 1) {
 9         //每趟排序的过程
10         for (j = 0; j < i; j++) {
11             //核心交换算法
12             if (list[j] > list[j + 1]) {
13                 list[j] = list[j] + list[j + 1];
14                 list[j + 1] = list[j] - list[j + 1];
15                 list[j] = list[j] - list[j + 1];
16                 //交换完毕,最值移动到了末位,需要记录下最新的位置
17                 k = j;
18             }//end of if
19         }//end of for
20         //更新每趟排序过程中的 i 值
21         i = k;
22     }//end of while
23 }
24 
25 int main(void)
26 {
27     int source[8] = {49, 38, 65, 97, 76, 13, 27, 49};
28     
29     bubbleSort(source, 8);
30     
31     for (int i = 0; i < 8; i++) {
32         printf(" %d ", source[i]);
33     }
34     
35     return 0;
36 }
复制代码

13  27  38  49  49  65  76  97 Program ended with exit code: 0

一般情况下每经过一趟“起泡”,“ i 减 1”,但并不是每趟都如此。

冒泡排序算法的时间复杂度: 
最好情况(正序), 比较次数:n -1        移动次数:0        T(n) = O(n) 
最坏情况(逆序), 比较次数:       移动次数:

平均时间复杂度:T(n) = O(n2) 

空间复杂度:
S(n) = O(1) 

冒泡排序的稳定性:
稳定排序 

 

 

快速排序算法

基本思想:任选一个记录,以它的关键字作为“枢轴”,凡关键字小于枢轴的记录均移至枢轴之前,凡关键字大于枢轴的记录均移至枢轴之后。(整个过程是交替扫描和交换的过程),这个记录开始选取的时候,一般选取第一个记录作为枢轴。做法是附设两个指针 low 和 high,从 high 所指位置起向前搜索找到第一个关键字小于枢轴的关键字的记录与枢轴记录交换,然后从 low  所指位置起向后搜索找到第一个关键字大于枢轴的关键字的记录与枢轴记录交换,重复这两步直至 low = high 为止。 

递增排序的图解如下:

初始状态,第一趟排序,一般第一个记录为枢轴,这里是52

因为是递增排序,high 往前扫描,找第一个和52比较,小于52的记录,即23

把枢轴52临时存储在 temp 处,把23交换到枢轴之前

high 扫描交换之后,马上换到 low,low 从前面开始扫描,找到第一个和52比较,大于52的记录,即80。

交换

转到 high,扫描,交换14

到 low,扫描,没有发现比52大的,直到 low 和 high 重合

最后把 temp 里的枢轴记录,存放到重合的位置即可

这样就完成了一趟快速排序,注意是一趟而已。

一趟快速排序代码如下:

复制代码
 1 //一次划分的快速排序算法
 2 int partitionSort(int l[], int low, int high)
 3 {
 4     //第一次快速排序,一般把第一个记录看成是枢轴记录,临时存放
 5     int temp = l[low];
 6     //设置枢轴记录
 7     int pivot = l[low];
 8     //扫描和比较终止的条件low=high
 9     while (low < high) {
10         //先从 high 开始向前扫描第一个比枢轴记录小的记录,交换
11         while (low < high && l[high] > pivot) {
12             //找不到就继续扫描
13             high--;
14         }
15         //找到了,把比枢轴记录小的,交换到低端
16         l[low] = l[high];
17         //循环交替扫描,从 low 开始向后扫描找第一个比枢轴大的记录,交换
18         while (low < high && l[low] <= pivot) {
19             //找不到就继续扫描
20             low++;
21         }
22         //找到了,把比枢轴记录大的,交换到高端
23         l[high] = l[low];
24     }//end of while
25     //一次排序终止,把枢轴记录放到终止位置
26     l[low] = temp;
27     //返回枢轴所在位置
28     return low;//返回high也可以
29 }
30 
31 int main(void)
32 {
33     int source[10] = {52, 49, 80, 36, 14, 58, 61, 97, 23, 75};
34     
35     partitionSort(source, 0, 9);
36     
37     for (int i = 0; i < 10; i++) {
38         printf(" %d ", source[i]);
39     }
40     
41     return 0;
42 }
复制代码

23  49  14  36  52  58  61  97  80  75 Program ended with exit code: 0

 

继续探究快速排序算法

首先对无序的记录序列进行“一次划分”,之后分别对分割所得两个子序列“递归”进行一趟快速排序。序列越是无序,快速排序的效果越好。

这里显然有递归的思想在里面,完整代码如下

复制代码
 1 //一次划分的快速排序算法
 2 int partitionSort(int l[], int low, int high)
 3 {
 4     //第一次快速排序,一般把第一个记录看成是枢轴记录,临时存放
 5     int temp = l[low];
 6     //设置枢轴记录
 7     int pivot = l[low];
 8     //扫描和比较终止的条件low=high
 9     while (low < high) {
10         //先从 high 开始向前扫描第一个比枢轴记录小的记录,交换
11         while (low < high && l[high] > pivot) {
12             //找不到就继续扫描
13             high--;
14         }
15         //找到了,把比枢轴记录小的,交换到低端
16         l[low] = l[high];
17         //循环交替扫描,从 low 开始向后扫描找第一个比枢轴大的记录,交换
18         while (low < high && l[low] <= pivot) {
19             //找不到就继续扫描
20             low++;
21         }
22         //找到了,把比枢轴记录大的,交换到高端
23         l[high] = l[low];
24     }//end of while
25     //一次排序终止,把枢轴记录放到终止位置
26     l[low] = temp;
27     //返回枢轴所在位置
28     return low;//返回high也可以
29 }
30 
31 //递归的思想完成完整的快速排序算法
32 void quickSort(int l[], int low, int high)
33 {
34     //对长度大于1的顺序表进行快速排序,先进行一次分割的划分
35     if (low < high) {
36         int pivot = partitionSort(l, low, high);
37         //递归的分别对子序列进行一次划分快速排序的过程
38         quickSort(l, low, pivot - 1);
39         quickSort(l, pivot + 1, high);
40     }
41 }
42 
43 int main(void)
44 {
45     int source[10] = {52, 49, 80, 36, 14, 58, 61, 97, 23, 75};
46     
47     quickSort(source, 0, 9);
48     
49     for (int i = 0; i < 10; i++) {
50         printf(" %d ", source[i]);
51     }
52     
53     return 0;
54 }
复制代码

注意:第一次调用函数 quickSort时,待排序记录序列的上、下界分别为 1 和 L.length。

 

快速排序算法时间复杂度分析

假设一次划分所得枢轴位置 i=k,则对 n 个记录进行快排所需时间:

T(n) = Tpass(n) + T(k-1) + T(n-k),其中 Tpass(n) 为对 n 个记录进行一次划分所需时间。

若待排序列中记录的关键字是随机分布的,则 k 取 1 至 n 中任一值的可能性相同。由此可得快速排序所需时间的平均值为:

设 Tavg(1)≤b,则可得结果:

快速排序时间复杂度结论:

快速排序的时间复杂度为 O(n log2(n))。注意:快速排序的一次划分所需时间和表长成正比,到目前为止快速排序是平均速度最大的一种排序方法。排序趟数和初试序列有关。

快速排序的空间复杂度

O(log2(n))

快速排序的蜕化特点:

在最坏的情况,即待排序序列已经按关键字“正序”排列的情况下,每次划分只得到一个比上一次少一个对象的子序列。这样,必须经过 n-1 趟才能把所有对象定位,而且第 i 趟需要经过 n-i 次关键码比较才能找到第 i 个对象的安放位置,快速排序将蜕化为起泡排序,其最坏的时间复杂度为 O(n2),所以快速排序适用于原始记录排列杂乱无章的情况。

快速排序退化的例子

用第一个对象作为基准对象     

改进方法:

为避免出现快速排序蜕化为冒泡排序的情况,需在进行一次划分之前,进行“预处理”

即:先对 L(s),  L(t) 和 L[(s+t)/2],其中开始的时候,s=0,t=length,进行相互比较,然后取关键字的大小为中间的记录为枢轴记录。

 
快速排序的稳定性:
不稳定的排序,在递归调用时需要占据一定的存储空间( 递归栈)用来保存每一层递归调用时的必要信息。 对于 n 较大的平均情况而言,快速排序是“快速”的,但是当 n 很小时,这种排序方法往往比其它简单排序方法还要慢。

 

辛苦的劳动,转载请注明出处,谢谢……
http://www.cnblogs.com/kubixuesheng/p/4353616.html
相关文章
|
23天前
|
存储 算法 程序员
数据结构与算法===递归
数据结构与算法===递归
|
2天前
|
算法 搜索推荐 编译器
算法高手养成记:Python快速排序的深度优化与实战案例分析
【7月更文挑战第11天】快速排序是编程基础,以O(n log n)时间复杂度和原址排序著称。其核心是“分而治之”,通过选择基准元素分割数组并递归排序两部分。优化包括:选择中位数作基准、尾递归优化、小数组用简单排序。以下是一个考虑优化的Python实现片段,展示了随机基准选择。通过实践和优化,能提升算法技能。**
8 3
|
11天前
|
算法 PHP
【php经典算法】冒泡排序,冒泡排序原理,冒泡排序执行逻辑,执行过程,执行结果 代码
【php经典算法】冒泡排序,冒泡排序原理,冒泡排序执行逻辑,执行过程,执行结果 代码
9 1
|
15天前
|
数据采集 算法 安全
CVPR 2024:给NeRF开透视眼!稀疏视角下用X光进行三维重建,9类算法工具包全开源
【6月更文挑战第28天】CVPR 2024亮点:SAX-NeRF框架开源!融合X光与NeRF,提升3D重建效果。X3D数据集验证,Lineformer+MLG策略揭示物体内部结构,增强几何理解。虽有计算成本及泛化挑战,但为计算机视觉和医学影像开辟新路径。[论文链接](https://arxiv.org/abs/2311.10959)**
33 5
|
22天前
|
搜索推荐 算法 Java
Java中的快速排序、归并排序和堆排序是常见的排序算法。
【6月更文挑战第21天】Java中的快速排序、归并排序和堆排序是常见的排序算法。快速排序采用分治,以基准元素划分数组并递归排序;归并排序同样分治,先分割再合并有序子数组;堆排序通过构建堆来排序,保持堆性质并交换堆顶元素。每种算法各有优劣:快排平均高效,最坏O(n²);归并稳定O(n log n)但需额外空间;堆排序O(n log n)且原地排序,但不稳定。
22 3
|
22天前
|
机器学习/深度学习 算法 搜索推荐
数据结构算法--2 冒泡排序,选择排序,插入排序
**基础排序算法包括冒泡排序、选择排序和插入排序。冒泡排序通过相邻元素比较交换,逐步将最大值“冒”到末尾,平均时间复杂度为O(n^2)。选择排序每次找到剩余部分的最小值与未排序部分的第一个元素交换,同样具有O(n^2)的时间复杂度。插入排序则类似玩牌,将新元素插入到已排序部分的正确位置,也是O(n^2)复杂度。这些算法适用于小规模或部分有序的数据。**
|
26天前
|
算法 搜索推荐 JavaScript
算法学习:快速排序
算法学习:快速排序
16 1
|
11天前
|
算法 搜索推荐 C#
|
18天前
|
搜索推荐 算法 大数据
​【数据结构与算法】冒泡排序:简单易懂的排序算法解析
​【数据结构与算法】冒泡排序:简单易懂的排序算法解析
|
19天前
|
搜索推荐 C语言
【C/排序算法】:快速排序和归并排序的非递归实现
【C/排序算法】:快速排序和归并排序的非递归实现
12 0