冒泡排序、插入排序、选择排序

2024-01-17 08:22| 来源: 网络整理| 查看: 265

排序 1 冒泡排序1.1冒泡排序的流程及代码2 插入排序2.1插入排序的流程及代码3 选择排序3.1选择排序的流程及代码

1 冒泡排序

它是通过一系列的”交换“动作完成的。首先第一个关键字和第二个关键字比较，如果第一个大，则二者交换，否则不交换；然后第二个关键字和第三个关键字比较，如果第二个大，则二者交换，否则不交换…一直按这种方式进行下去，最终最大的那个关键字被交换到了最后，一趟起泡排序完成。经过多趟这样的排序，最终使整个序列有序。这个过程中，大的关键字像石头一样”沉底“，小的关键字像气泡一样逐渐向上”浮动“，冒泡排序的名字由此而来。

1.1冒泡排序的流程及代码

在这里插入图片描述至此一趟气泡排序结束，最大的97被交换到了最后，97到达了它最后的位置。接下来对序列38 49 65 76 13 27 49 按照同样的方法进行第二趟冒泡排序。经过若干趟冒泡排序后，最终序列有序。要注意的是，冒泡排序算法结束的条件是在一趟排序过程中没有发生关键字交换。冒泡排序的算法代码如下：

void BubbleSort(int R[], int n)//默认待排序关键字为整型 { int i,j,flag; int temp; for(i=n-1; i>=1; --i) { flag=0;//变量flag用来标记本趟排序是否发生了交换 for(j=1; j R[j]) { temp=R[j]; R[j]=R[j-1]; R[j-1]=temp; flag=1; } if(flag == 0) return; } }

时间复杂度和空间复杂度在这里插入图片描述

2 插入排序

每趟将一个待排序的关键字按照其值的大小插入到已经排好的部分有序序列的适当位置上，直到所有待排关键字都被插入到有序序列中为止

2.1插入排序的流程及代码

在这里插入图片描述以上是插入排序的全部过程，接下来我们来看直接插入排序的算法代码：

void InsertSort(int R[],int n)//待排关键字存储在R[]中，默认为整型，个数为n { int i,j; int temp; for(i=1; i R[j+1]=R[j]; --j; } R[j+1]=temp;//找到插入位置，将temp中暂存的待排关键字插入 } }

该算法的时间复杂度和空间复杂度：

算法稳定性排序方式时间复杂度最好时间空间复杂度插入稳定直接插入O(n2)O(n)O(1) 3 选择排序

选择类排序的主要动作是”选择“，简单选择排序采用最简单的选择方式，从头至尾扫描序列，找出最小的一个关键字，和第一个关键字交换，接着从剩下的关键字中继续这种选择和交换，最终使序列有序。

3.1选择排序的流程及代码

在这里插入图片描述根据上述的流程，我们就能写出简单排序的代码：

void SelectSort(int R[],int n) { int i,j,k; int temp; for(i=0; i if(R[k] > R[j]) { k=j; } /*下面3句完成最小关键字与无序序列第一个关键字的交换*/ temp=R[i]; R[i]=R[k]; R[k]=temp; } } }

该算法的时间复杂度和空间复杂度

算法稳定性排序方式时间复杂度最好时间空间复杂度选择不稳定直接选择O(n2)O(n)O(1)

本篇文章我们主要介绍了冒泡排序，插入排序和选择排序，为什么我要将它们三个放在一起讲，细心的已经发现了是因为它们的时间复杂度和空间复杂度是一样的。如下图在这里插入图片描述

【本文地址】

公司简介

联系我们