宁波网站排名优化公司,软件开发公司简介模板,网站备案查询背景布,网站建设价格最低多少钱目录 1. 排序的概念#xff1a;
2.选择排序的基本思想
3.直接选择排序
4.堆排序 1. 排序的概念#xff1a;
排序#xff1a;所谓排序#xff0c;就是使一串记录#xff0c;按照其中的某个或某些关键字的大小#xff0c;递增或递减的排列起来的操作。
稳定性#xf…目录 1. 排序的概念
2.选择排序的基本思想
3.直接选择排序
4.堆排序 1. 排序的概念
排序所谓排序就是使一串记录按照其中的某个或某些关键字的大小递增或递减的排列起来的操作。
稳定性假定在待排序的记录序列中存在多个具有相同的关键字的记录若经过排序这些记录的相对次序保持不变即在原序列中r[i]r[j]且r[i]在r[j]之前而在排序后的序列中r[i]仍在r[j]之前则称这种排序算法是稳定的;否则称为不稳定。
内部排序数据元素全部放在内存中的排序。
外部排序数据元素太多不能同时放在内存中根据排序过程的要求不能在内外存之间移动数据的排序。
2.选择排序的基本思想
每一次从待排序的数据元素中选出最小或最大的一个元素存放在序列的起始位置直到全部待排序的数据元素排完。
3.直接选择排序
在元素集合array[i]--array[n-1]中选择关键码最大(小)的数据元素若它不是这组元素中的最后一个(第一个)元素则将它与这组元素中的最后一个(第一个元素交换。在剩余的array[i]--array[n-2] array[i1]--array[n-1]集合中重复上述步骤直到集合剩余1个元素
选择排序图解这张动图是选择后面最小的数与前面做交换
当让我们还可以优化如果是升序每一次遍历分别选出最小的元素和最大的元素分别与前面和后面数据做交换。
代码实现
//交换函数
void Swap(int* p1, int* p2)
{int t *p1;*p1 *p2;*p2 t;
}// 选择排序 升序
void SelectSort(int* arr, int n)
{int begin 0;int end n - 1;while (begin end){int maxi begin;int mini begin;for (int i begin; i end; i){if (arr[i] arr[maxi]){maxi i;}if (arr[i] arr[mini]){mini i;}}Swap(arr[mini], arr[begin]);if (begin maxi){maxi mini;}Swap(arr[maxi], arr[end]);begin;end--;}
}直接选择排序的特性总结:
直接选择排序思考非常好理解但是效率不是很好。实际中很少使用时间复杂度:O(N^2)空间复杂度:O(1)稳定性:不稳定
4.堆排序
我们这里需要先了解堆的结构如果不了解可以看我之前的文章【数据结构】这堆是什么。
当我们了解完堆的结构后我们就可以开始学习堆排序了。
堆排序(Heapsort)是指利用堆积树堆这种数据结构所设计的一种排序算法它是选择排序的 种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆排降序建小堆。
首先要构建一个堆然后让堆顶元素与最后一个元素交换把最后一个位置元素当作不在堆内。然后通过向下调整法调整堆。循环就可以排序
图解 建堆可以使用向上调整法建堆和向下调整法建堆这两种方法在【数据结构】这堆是什么 中有详细讲解。向上调整法建堆时间复杂度为O(N*logN)但是向下调整法时间复杂度低为O(N)。所以我们这里使用向下调整法建堆。
代码实现
//向下调整法
void AdjustDown(int* arr, int n, int parent)
{int child parent * 2 1;while (child n){if (child 1 n arr[child 1] arr[child]){child;}if (arr[parent] arr[child]){Swap(arr[parent], arr[child]);parent child;child parent * 2 1;}else{break;}}
}
//堆排序
void HeapSort(int* arr, int n)
{//建堆for (int i (n - 1 - 1) / 2; i 0; i--){AdjustDown(arr, n, i);}//排序int end n - 1;while (end 0){Swap(arr[end], arr[0]);AdjustDown(arr, end, 0);end--;}
}
堆排序的特性总结:
堆排序使用堆来选数效率就高了很多。时间复杂度:O(N*logN)空间复杂度:O(1)稳定性:不稳定
本篇文章结束我们下一篇文章来学习一下【交换排序】冒泡排序与快速排序。
