首页 > 选择排序 算法

选择排序 算法

算法思路

  1. 维护一段有序数列,同时遍历待排序数列,找到最小的元素插入有序数列中
  2. 重复,直到待排序数列没有剩余元素

代码实现

void select_sort(vector<int> &arr) { for (int i = 0;i < arr.size(); ++i) { int temp = arr[i];int index = i;for (int j = i + 1; j < arr.size(); ++j) { //找到待排序数列的最小元素if(arr[j] < temp) { temp = arr[j];index = j;}}swap(arr[i],arr[index]);//置换}
}

算法分析

时间复杂度:无论最好情况还是最坏情况,都是O(n^2),因为每次选择最小元素都要遍历剩余的所有元素

空间复杂度:O(1),swap时的临时变量

更多相关:

  • 题目:最小的k个数 入整数数组 arr ,找出其中最小的 k 个数。例如,输入4、5、1、6、2、7、3、8这8个数字,则最小的4个数字是1、2、3、4。 示例 1: 输入:arr = [3,2,1], k = 2 输出:[1,2] 或者 [2,1] 示例 2: 输入:arr = [0,1,2,1], k = 1 输出:[0...

  • //自定义深度复制对象or数组的递归方法---------------------------------------- let copyObjOrArr = o => {let isArray = o instanceof Array;let isObject = o instanceof Object;if (!isObject)...

  • var array = {/* 数组求和*/sum: arr => eval(arr.join("+")),/* 判断一个数组(支持一个字符串)里面的是否有任何一个元素被包含在了某个字符串里面 */isStringContain(str, arr) {Array.isArray(arr) || (arr = [arr]);for (v...

  • 经过调研发现,对任意无序整数数组,快速排序有两种实现方法,这里简单阐述下思路: 思路一:随意选择一个基准元,一般选择数组的起始元或末尾元,Weiss这本书上特意搞了个算法来选择基准元,……,总之就是基准元的选择要尽量随机。选定基准元之后,比如选择数组起始元为基准元,从数组右边开始,向左边遍历,遇到比基准元大的跳过,直至遇到比基准元小...

  • 下面给出这段时间我苦心研究验证过的十种经典排序算法的C语言版本,即下面的排序算法: 插入排序,shell排序,冒泡排序,快速排序,选择排序,堆排序,归并排序,桶排序,基数排序和计数排序。整理出来以作备忘,不足之处,欢迎大家批评指正!其中计数排序分别给出了不稳定和稳定两种排序算法,测试时,使用随机生成大数组和随机手动输入的方法来测试。...

  • 栈stack:stack 后入先出(LIFO) q.top()获取栈顶元素(并不删除)q.pop()删除栈顶元素q.push(x)向栈中加入元素q.empty()判断栈是否为空 队列queue:先入先出(FIFO)   q.front()获取队首元素(并不删除)q.pop()删除队首元素q.push(x)向队列中加入元素q....

  • resize(),设置大小(size); reserve(),设置容量(capacity); size()是分配容器的内存大小,而capacity()只是设置容器容量大小,但并没有真正分配内存。 打个比方:正在建造的一辆公交车,车里面可以设置40个座椅(reserve(40);),这是它的容量,但并不是说它里面就有了40个座椅,只能说...

  • v-for="(index,$i) in total" :key="$i":style="{left:`${itemWidth*((index-1)%rowItemCount)}px`,top:`${itemHeight*(Math.ceil(index/rowItemCount)-1)}px`}" //total是显示总数量 //l...

  •   技巧一(推荐指数★★★★★) 采用top、right、bottom、left,可以不在乎父元素的宽度和高度,对GPU损耗低于技巧三,但是对浏览器内存的消耗高于技巧三 .子元素 {/*父元素需要position: relative|absolute;*/position: absolute;margin: auto;to...

  • 设计一个支持 push,pop,top 操作,并能在常数时间内检索到最小元素的栈。 push(x) – 将元素 x 推入栈中。pop() – 删除栈顶的元素。top() – 获取栈顶元素。getMin() – 检索栈中的最小元素。 示例: MinStack minStack = new MinStack(); minStack...

  •         Apache POI是一个开源的利用Java读写Excel,WORD等微软OLE2组件文档的项目。        我的需求是对Excel的数据进行导入或将数据以Excel的形式导出。先上简单的测试代码:package com.xing.studyTest.poi;import java.io.FileInputSt...

  • 要取得[a,b)的随机整数,使用(rand() % (b-a))+ a; 要取得[a,b]的随机整数,使用(rand() % (b-a+1))+ a; 要取得(a,b]的随机整数,使用(rand() % (b-a))+ a + 1; 通用公式:a + rand() % n;其中的a是起始值,n是整数的范围。 要取得a到b之间的...

  • 利用本征图像分解(Intrinsic Image Decomposition)算法,将图像分解为shading(illumination) image 和 reflectance(albedo) image,计算图像的reflectance image。 Reflectance Image 是指在变化的光照条件下能够维持不变的图像部分...

  • 题目:面试题39. 数组中出现次数超过一半的数字 数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。 你可以假设数组是非空的,并且给定的数组总是存在多数元素。 示例 1: 输入: [1, 2, 3, 2, 2, 2, 5, 4, 2] 输出: 2 限制: 1 <= 数组长度 <= 50000 解题: cl...

  • 题目:二叉搜索树的后序遍历序列 输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true,否则返回 false。假设输入的数组的任意两个数字都互不相同。 参考以下这颗二叉搜索树:      5     /    2   6   /  1   3示例 1: 输入: [1,6,3,2,5] 输出...