网站建设方案报价,网站开发需要哪些技能,徐州京都网架公司,公司起名字大全免费三个字选择排序 和 堆排序 一、选择排序选择排序的思路及其代码选择排序的弊端 二、堆排序三、速度对比同时排10000个数同时排100000个数同时拍500000个数堆排 1 亿个数 一、选择排序
选择排序的思路及其代码
选择排序思路很简单 就是经过将数组遍历选择最小值 将最小值位置的数与数… 选择排序 和 堆排序 一、选择排序选择排序的思路及其代码选择排序的弊端 二、堆排序三、速度对比同时排10000个数同时排100000个数同时拍500000个数堆排 1 亿个数 一、选择排序
选择排序的思路及其代码
选择排序思路很简单 就是经过将数组遍历选择最小值 将最小值位置的数与数组最前面位置的数进行交换 如此反复完成排序
为了提高效率我们在一次遍历过程中同时找最大和最小值 代码如下
//选择排序
void SelectSort(int* a, int n)
{int maxi n - 1;int mini 0;while (mini maxi){//找出最大最小值的下标int max maxi;int min mini;for (int i mini; i maxi; i){if (a[i] a[max]){max i;}if (a[i] a[min]){min i;}}//将最大最小值进行更新将最大最小值放到数组两边Swap(a[mini], a[min]);//若最大值在原最小值的位置将位置更新if (max mini){max min;}Swap(a[maxi], a[max]);maxi--;mini;}
}运行结果
选择排序的弊端
因为无论数组中原数组是如何排列 选择排序都要遍历数组 所以它的最好与最坏的情况下 时间复杂度都是 O(N ^ 2) 效率低下正常情况下是不会使用这个排序的
二、堆排序
以下的链接又对堆和堆排序的讲解 堆以及堆排序
下面我就直接把代码贴出来
//向下调整建大堆
void AdjustDown(int* a, int parent, int n)
{//左孩子int child parent * 2 1;while (child 1 n){//先找左右孩子中大的一个if (child 1 n a[child] a[child 1]){child;}//将父亲节点与孩子节点进行比较将大的移到父亲节点if (a[parent] a[child]){Swap(a[parent], a[child]);parent child;child parent * 2 1;}else{break;}}
}//堆排序
void HeapSort(int* a, int n)
{//向下调整建堆for (int i (n - 1 - 1) / 2; i 0; i--){AdjustDown(a, i, n);}//进行堆排序int size n - 1;while (size 0){//先将堆的第一个数与最后一个数交换Swap(a[0], a[size--]);//向下调整AdjustDown(a, 0, size);}
}运行结果 堆排序的时间复杂度为 O(N * logN)
三、速度对比
同时排10000个数 同时排100000个数 同时拍500000个数 排序到这里选择排序就已经非常慢了 我们笔记本是 i9 的 cpu 配置还算可以 跑的时候风扇已经呜呜转了
堆排 1 亿个数
