【交换排序简单选择排序堆排序归并排序】

文章目录 交换排序简单选择排序堆排序归并排序

交换排序

冒泡排序的算法分析：

冒泡排序最好的时间复杂度是O（n）冒泡排序最好的时间复杂度是O（n平方）冒泡排序平均时间复杂度为O（n的平方）冒泡排序算法中增加一个辅助空间temp，辅助空间为S（n）=O（1）。冒泡排序是稳定的。 void bubble_sort(int arr[],int n); void printArr(int arr[]); #define MAXSIZE 20 //设记录的值不超过20个 #define KeyType int//设关键字为整型量 #define InfoType int //定义InfoType的其他数据项 typedef struct { KeyType key;//定义每个记录(数据元素)的结构 InfoType otherinfo;//其他数据项 }RedType; typedef struct SqList { RedType r[MAXSIZE + 1];//存储顺序表的结构 //r[0]一般做哨兵或者缓冲区 int length;//顺序表的长度 }SqList; //void bubble_sort(SqList& L) { // //使用flag作为是否有交换的标记 // int i,n,i,j; // int flag = 1; // RedType x; // for (i = 1; i <= n - 1 && flag == 1; i++) { // flag = 0; // for (j = 1; j <= i; j++) { // if (arr[] > L.r[j + 1][]) { // //发生逆序 // flag = 1;//发生交换，flag置为1，若本趟没发生交换，flag保持为0. // x = arr; // arr = L.r[j + 1]; // L.r[j + 1] = x; // } // } // } //} void bubble_sort(int arr[],int n) { //使用flag作为是否有交换的标记 int i, j; int flag = 1; int x; for (i = 1; i <= n - 1 && flag == 1; i++) { flag = 0; for (j = 1; j <= i; j++) { if (arr[j] > arr[j + 1]) { //发生逆序 flag = 1;//发生交换，flag置为1，若本趟没发生交换，flag保持为0. x = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = x; } printf("第%d趟 ", i); } } } 简单选择排序

选择最小的值，进行排序。

堆排序

堆的定义： 若n个元素的序列{a1，a2…an}满足 则该序列分为小根堆和大根堆。 从堆的定义可以看出，堆实质是满足如下性质的完全二叉树，二叉树中任一非叶子节点均小于（大于）他的孩子结点。 堆排序： 若在输出堆顶的最小值（最大值）后，使得剩余n-1个元素的序列重新又建成一个堆，则得到n个元素的次小值（次大值）…如此反复，则有能得到一个有序序列，这个过程称之为堆排序。

实现堆排序需解决的两个问题：

如何由一个无序序列建成一个堆？ 单结点的二叉树是堆； 在完全二叉树中所有以叶子结点（序号为i>n/2）为根的子树是堆。 由于堆实质上是一个线性表，那么我们可以顺序存储一个堆。 步骤： 从最后一个非叶子结点开始向前调整： ①调整从第n/2个元素开始，将以该元素为根的二叉树调整为堆。 ②将以序号n/2-1的结点为根的二叉树调整为堆； ③将以序号n/2-2的结点为根的二叉树调整为堆； ④将以序号n/2-3的结点为根的二叉树调整为堆；

如何输出堆顶元素后，调整剩余元素为一个新的堆？ 小根堆： 1.输出堆顶元素之后，以堆中最后一个元素替代之。

2.然后将根结点值与左右子树的根结点值进行比较，并与其中小者进行交换。

3.重复上述操作，直至叶子结点，将得到新的堆，称这个从堆顶至叶子的调整过程为“筛选”。 下一次再输出堆顶元素27，再将最后一个元素97向上调整。再选左，右子树较小的那一个就是38，再将38调上去，再比较左右子树的大小。

算法性能分析：

归并排序

基本思想：将两个或两个以上的有序子序列“归并”成一个。 例：二路归并，归并树。 ![

[ ]

在这里插入图片描述

]( img-blog.csdnimg /direct/14c3d5b0f8d24c278f889998ec61ac28.png)