首页
学习
活动
专区
圈层
工具
发布
  • 您找到你想要的搜索结果了吗?
    是的
    没有找到

    排序——选择排序

    选择排序 --- 简单选择排序 基本思想 每一趟在后面 n-i +1个中选出关键码最小的对象, 作为有序序列的第 i 个记录 算法实现 void SelectSort(SqList &L){ // 对记录序列...L.length]作简单选择排序 for(i = 1; i <= L.length; i++){ // 选择第 i 小的记录,并交换到位 k = i; for(j = i + 1; j <...算法分析 含有n个叶子节点的完全二叉树的深度为log2 n+1,则选择排序的每一趟都需作log2n次比较,排序的时间复杂度O(nlog2n)。...改进:简单选择排序没有利用上次选择的结果,是造成速度满的重要原因。如果,能够加以改进,将会提高排序的速度。...--- 堆排序 堆:把待排序的数据元素存放在数组中r1…n,把r看成是一棵完全二叉树,每个结点表示一个记录。ri结点的左孩子是r2i,右孩子是r2i+1。

    1.5K125

    选择排序(简单选择排序、堆排序)

    选择排序 选择排序的基本思想是:每一趟在待排序元素中选取关键字最小(或最大)的元素加入有序子序列。...简单选择排序 概念 假设排序表为L[1…N],,第i趟排序即从L[1…N]中选择关键字最小的元素与L(i)交换,每一趟排序可以确定一个元素的最终位置,这样经过n-1趟排序就可以使得整个排序表有序...= i) swap(A[i],A[min]); } } 堆排序 概念 堆排序要结合顺序存储的完全二叉树的特性进行学习。...当且仅当 L(i) >=L(2i) 且 L(i)>=L(2i+1) 可以将该一维数组视为一棵完全二叉树,满足此条件的堆称之为大根堆。...堆排序的思路很简单:首先将存放在L[1…N]中的N个元素建成初始堆,由于堆本身的特点(以大根堆为例),堆顶元素就是最大值。

    1.1K10

    选择排序(直接选择排序和堆排序)

    一、直接选择排序 1.基本思想 每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完。...2.动图展示 3.思路讲解 ①在元素集合array[i]—array[n-1]中选择关键码最大(小)的数据元素。...mini]); if (begin == maxi) maxi = mini; Swap(&a[end], &a[maxi]); ++begin; --end; } } 5.直接选择排序特性总结...①直接选择排序思考非常好理解,但是效率不是很好,实际中很少使用。...二、堆排序 《二叉树》(二)讲解堆 1.基本思想 堆排序(Heapsort)是指利用堆积树(堆)这种数据结构所设计的一种排序算法,它是选择排序的一种。它是通过堆来进行选择数据。

    53210

    【排序算法】——选择排序

    本篇文章讲述的是排序算法中的选择排序,其中包含了两种排序算法,分别是直接选择排序和堆排序,下面将会一一为大家详细介绍。...1.直接选择排序 下面我们首先来看一看直接选择排序算法的动图演示: 看了上图我们可以得知,直接选择排序算法是首先从第1个位置开始对全部元素进行选择,选出全部元素中最小的给该位置...2.堆排序 直接选择排序是选择排序的一种,但是其时间复杂度很高,在实际应用中效率非常低下,那有没有其他的效率高的选择排序呢?...代码如下: void Select_sort(vector& a) { int n = a.size(); //数组大小为奇数,最后会处于left == right;当数组大小为偶数时...,大家可以自己用一个倒序数组亲自体验一下,以便有更深刻的体会。

    52010

    排序算法-选择排序

    算法简介 选择排序就是找到数组中最小元素将其和数组第一个元素交换位置,然后在剩下的元素中找到最小元素并将其与数组第二个元素进行交换,以此类推,直至整个数组排序结束。...算法描述 找到数组中最小元素并将其和数组第一个元素交换位置 在剩下的元素中找到最小元素并将其与数组第二个元素交换,直至整个数组排序 ?...代码实现 /** * 选择 * * @param array */ private static void selectionSort(int[]...由于每次都是选取未排序序列R中的最小元素 a 与 R 中的第一个元素交换,很可能破坏了元素间的相对位置,因此选择排序是不稳定的。...排序算法 平均时间复杂度 最好情况 最坏情况 空间复杂度 稳定性 选择排序 \(O(n^2)\) \(O(n^2)\) \(O(n^2)\) \(O(1)\) 不稳定

    2.3K40

    排序算法---选择排序

    排序是我们学习算法过程中重要且基础的一环,例如对下面的排序问题,我们应该怎么做呢?...选择排序思想和实现思路 提到排序问题,很容易想到的思路就是找出来所有数据中最大(或最小)的元素,放在一个新列表的第一位,然后再在剩下的元素中找出最大(或最小)的元素,放在新列表的第二位,以此类推......这就是选择排序(selection sort)的算法思想。 上图就是选择排序算法思想,但一个算法的实现往往不能通过一个简单的思想就搞定(这就是思想与现实的距离,哈哈~)。...& os, Student& s) { os << s.name << " " << s.score << endl; return os; } }; // 选择排序...auto student : students) { cout.width(8); // 设置数据宽度 cout << student; } // 选择排序

    1.3K10

    【排序算法】选择排序

    1.基本介绍 选择排序基本思想:它首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。...2.数据演示 第0次排序:8 5 2 7 3 4 第1次排序:2 5 8 7 3 4 第2次排序:2 3 8 7 5 4 第3次排序:2 3 4 7 5...重置最小值 minindex=i;//重置最小值的下标 } } //所以交换两个数组中的元素...重置最小值 minindex=i;//重置最小值的下标 } } //所以交换两个数组中的元素...,在100000个随机数据中只用了3秒,比小编上期的冒泡排序少了很多(冒泡排序http://t.csdnimg.cn/9mqj4) 7.总结 选择排序的时间复杂度为On(n^2) ,空间复杂度为O(1)

    1.3K10

    数组排序——冒泡排序

    基本思想 冒泡排序的基本思想是:将数组中相邻元素从前往后依次进⾏⽐较,如果前⼀个元素⽐后⼀个元素⼤,则交换,⼀趟下来后,最⼤元素就在数组的末尾这个过程重复进行,直到没有再需要交换的元素为止。...代码逻辑 我们以数组降序排列为例,演示冒泡排序的实现过程。...int[] arr = {11,22,6,4,34,1}; //我们以这个数组为例,进行降序排序 我们要进行排序,我们首先想到的就是循环,我们知道具体的循环次数,所以我们这里采用 for-循环,我们要进行排序...,一层循环不足以支撑排序,我们用双循环去进行排序,我们要进行两两比较,外层循环一躺可以确定一个数的位置,经过比较并交换位置,将想要的最小值换到数组的最后的位置,这样最大的元素会像气泡一样"浮"到数组末尾...我们要想把数组的所以数都进行排序,也就是需要arrays.length - 1 才可以确保所以元素就位。

    74710
    领券