- 领 域
- 数据结构
- 特 点
- 不稳定
- 分 类
- 简单选择排序,树型选择排序
- 中文名
- 选择排序法
- 学 科
- 计算机科学
- 外文名
- Selection sort method
-
2021-05-09 11:55:39
冒泡排序算法详细内容见→冒泡排序算法。
选择排序算法详细内容见→选择排序算法。冒泡排序算法和选择排序算法的区别:
- 冒泡排序是比较相邻位置的两个数;而选择排序是按顺序比较,找出最大值或者最小值。
- 冒泡排序扫描一遍数组,位置不对需要不停地互换位置;而选择排序扫描一遍数组,只需要换一次位置,所以一般来说选择排序比冒泡排序效率高。
- 冒泡排序是通过数去找位置;而选择排序是给定位置去找数。
冒泡排序算法的优缺点:
优点:比较简单,空间复杂度较低,是稳定的;
缺点:时间复杂度太高,效率慢。选择排序算法的优缺点:
优点:一轮比较只需要换一次位置;
缺点:效率慢,不稳定(例如对于数组{5,8,5,2,9},第一遍选择第一个元素5会和2交换,那么原序列中两个5的相对位置前后顺序就破坏了)。更多相关内容 -
选择排序算法
2021-05-09 10:10:00选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理是:第一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,然后再从剩余的未排序元素中寻找到最小(大)元素,...选择排序(Selection Sort)是一种简单直观的排序算法。它的工作原理是:第一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,然后再从剩余的未排序元素中寻找到最小(大)元素,然后放到已排序的序列的末尾。以此类推,直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法。
选择排序就是从当前未排序的整数中找一个最小的整数,将它放在已排序的整数列表的最后。
如何找出最小的一个元素呢? 先随便选一个元素假设它为最小的元素(默认为序列的第一个元素),然后让这个元素与序列中的每一个元素进行比较,如果遇到比自己小的元素,那更新最小值下标,直到把序列中的元素遍历完,那最后的最小值就是序列中的最小值。
例如: 使用选择排序算法将数组 { 4,2,8,0,5,7,1,3,6,9 } 进行升序排序。
步骤:1. 在一个长度为n的无序数组中,第一次遍历n-1个数找到最小的和第一个数交换。
2. 第二次从下一个数开始遍历n-2个数,找到最小的数和第二个数交换。
3. 重复以上操作直到第n-1次遍历最小的数和第n-1个数交换,排序完成。
实现代码如下所示。#include<iostream> using namespace std; void SelectSort(int *list, const int n) { for (int i = 0; i < n - 1; i++) { int min = i; //min为最小值索引 for (int j = i + 1; j < n; j++) { if (list[j] < list[min]) { min = j; } } std::swap(list[i], list[min]); } } int main() { int a[] = { 4,2,8,0,5,7,1,3,6,9 }; cout << "排序前:" << endl; for (int i = 0; i < 10; i++) { cout << a[i] << " "; } cout << endl; SelectSort(a, 10); cout << "排序后:" << endl; for (int i = 0; i < 10; i++) { cout << a[i] << " "; } cout << endl; system("pause"); return 0; }
排序前:
4 2 8 0 5 7 1 3 6 9
排序后:
0 1 2 3 4 5 6 7 8 9选择排序算法的详细过程如下图所示。
时间复杂度: 对于长度为 n n n的数组,代码执行的时间都花费在内层for循环中的比较语句和外层for循环里的交换语句了。外层for循环执行 n − 1 n-1 n−1次,那么交换(swap)就执行 n − 1 n-1 n−1次,时间复杂度为 O ( n ) O(n) O(n);内层for循环中的比较语句执行次数为 ( n − 1 ) + ( n − 2 ) + … + 2 + 1 = n ( n − 1 ) 2 = 1 2 n 2 − 1 2 n (n-1) + (n-2) +…+2+1=\frac{n(n-1)}{2}=\frac{1}{2}n^{2}-\frac{1}{2}n (n−1)+(n−2)+…+2+1=2n(n−1)=21n2−21n,时间复杂度为 O ( n 2 ) O(n^2) O(n2)。所以,选择排序算法的时间复杂度为 O ( n 2 ) O(n^2) O(n2)。空间复杂度: O ( 1 ) O(1) O(1)。
稳定性: 由于选择元素之后会发生交换操作,有可能把前面的元素交换到后面,所以选择排序不是稳定的排序,如下图所示。
-
Python实现的选择排序算法示例
2020-09-21 00:50:25主要介绍了Python实现的选择排序算法,结合实例形式分析了Python选择排序的概念、原理及简单实现技巧,需要的朋友可以参考下 -
直接插入排序法、冒泡排序法、直接选择排序法算法
2018-06-28 21:15:48C语言代码 直接插入法排序算法fun1,冒泡法排序排列算法fun2,直接选择法排序算法fun3。 -
C语言选择排序算法及实例代码
2020-09-02 00:17:10本篇文章主要介绍了 C语言选择排序算法,这里提供代码实例以便大家理解,通过本文,更好的理解排序算法 -
Java实现选择排序算法的实例教程
2020-09-02 10:28:58主要介绍了Java实现选择排序算法的实例教程,选择排序的时间复杂度为О(n²),需要的朋友可以参考下 -
C语言 选择排序算法详解及实现代码
2020-09-01 18:44:57本文主要介绍C语言 选择排序算法,这里对排序算法做了详细说明,并附代码示例,有需要的小伙伴可以参考下 -
Python实现的插入排序,冒泡排序,快速排序,选择排序算法示例
2020-12-25 20:02:03本文实例讲述了Python实现的插入排序,冒泡排序,快速排序,选择排序算法。分享给大家供大家参考,具体如下: #!/usr/bin/python # coding:utf-8 #直接插入排序 def insert_sort(list): for i in range(len(list))... -
C语言之选择排序算法
2021-03-29 20:51:36对于选择排序,咱们首先理解排序的思想。给定一个数组,这种思想首先假定数组的首元素为最大或者最小的。此时就要利用3个变量表示元素的下标。一个表示当前,一个表示找到的最大或者最小的下标,一个用于存放每次...C语言学习交流群:648422161。志同道合的小伙伴可以进群交流哦!
对于选择排序,咱们首先理解排序的思想。给定一个数组,这种思想首先假定数组的首元素为最大或者最小的。此时就要利用3个变量表示元素的下标。一个表示当前,一个表示找到的最大或者最小的下标,一个用于存放每次循环中最大值的下标。在掌握了程序的基本思想之后,再进行排序。找到最大的下标后赋给每次除非的那个最大的下标。找到之后判断所假设的当前值是否为此次循环的最大值,如果不是,就交换最大 与当前的值,从而将数组以一定的顺序排放。其实 简而言之就是每次找到最大的或者最小的放在前面,当然了排过的位置就不用多次排了初始的一组数
45 10 5 60 9
找到最小的 5,交换位置 5 10 45 60 9
除去排好的位置接着往后 5 9 45 60 10
以此类推直到排好。
下面贴出代码void selectSort(int data[],int length){ for (int i = 0; i < length; i++) { int k=i;//指向当前下标i //找最小值的坐标 for (int j = i+1; j < length; j++) { //如果当前值大于后一个值则k指向新下标 if (data[k]>data[j]) { k=j; } } //如果不等于当前下标i,交换位置 if (k!=i) { //交换位置 swap(&data[k],&data[i]); } } }
排序方法 平均时间 最坏情况 辅助存储 是否稳定
选择排序 O(n^2) O(n^2) O(1) 不稳定 -
选择排序算法与示例详解(c语言)
2020-12-14 16:01:57选择排序是排序算法的一种,思想就是,每一轮寻找数组中最大的值或者最小的值,放在头部或者放入一个新的数组。这样经历一轮遍历,数组或者新数组就是排好序的,他的目的很明确,每次找最大值或者最小值。 这个...选择排序是排序算法的一种,思想就是,每一轮寻找数组中最大的值或者最小的值,放在头部或者放入一个新的数组。这样经历一轮遍历,数组或者新数组就是排好序的,他的目的很明确,每次找最大值或者最小值。
这个放在头部,其实头部不是固定不变的,每次都会往后移动一位,因为前面的数据都是排好序的。这种借助当前数组做排序的算法,是为了节省空间,也是一种提高效率的办法。
以最大值为例,如何找最大值?比较嘛,默认选择第一个元素作为最大值,依次与数组中的元素比较,有比它大的,就交换,遍历完成,就找到了最大值。
#include <stdio.h> int main() { int arr[] = {6,5,4,3,2,1,7,8,9,0}; int max = arr[0]; for(int i=1;i<10;i++) { if(max<arr[i]) max = arr[i]; } printf("max=%d\n",max); return 0; }
这个找最大值,就是每次比较之后,如果满足条件都需要进行数组元素交换。也有一种做法,记录下标,如果换为交换下标,这样,最后遍历完成,我们取出下标对应的元素即可。
我们来看看选择排序:
#include <stdio.h> void selectSort(int arr[],int n) { int i,j,maxIndex,tmp; for(i=0;i<n-1;i++) { maxIndex = i; for(j=i+1;j<n;j++) { if(arr[maxIndex]<arr[j]) maxIndex = j; } tmp = arr[i]; arr[i] = arr[maxIndex]; arr[maxIndex] = tmp; } } int main() { int arr[] = {6,5,4,3,2,1,7,8,9,0}; selectSort(arr,10); for(int i=0;i<10;i++) printf("%d ",arr[i]); printf("\n"); return 0; }
这种排序,我们需要额外申请一个变量来记录maxIndex或者minIndex,如果不用这个变量,我们就回到了前面提到的,每次交换数组元素。
void selectSort(int arr[], int n) { int i, j, tmp; for (i = 0; i < n - 1; i++) { for (int j = i + 1; j < n; j++) { if (arr[i] < arr[j]) { tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } } } }
这种排序,看起来,很像冒泡排序,不同的是,冒泡排序,每次比较的是相邻元素,选择排序比较的是固定位置的元素和集合中剩余的元素。
我们通过示例,来直观感受一下两者的区别:
冒泡排序:
选择排序:
冒泡排序算法:
void bubbleSort(int arr[], int n) { int i, j, tmp; for (i = 0; i < n; i++) { for (j = 0; j < n - 1 - i; j++) { if (arr[j] < arr[j + 1]) { tmp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = tmp; } } } }
代码直观比较:
从算法的结果和特点来看,选择排序,前面的元素是排好序的,而冒泡排序,末尾的元素的排好序的。所以在冒泡排序第二层循环里面,不用每次都遍历整个数组,而是到n-1-i的位置。他们共同特点是算法复杂度是相同的,都是O(n*n)。
这里交换元素,我们也用了一个别的变量,其实也有取巧的算法,连别的变量也不需要的,直接交换两个元素的值:
if (arr[i] < arr[j]) { arr[i] = arr[i] ^ arr[j]; arr[j] = arr[i] ^ arr[j]; arr[i] = arr[i] ^ arr[j]; }
这种办法是一种很巧妙的算法,是有计算依据的,大家可以看看如下的计算过程:
有人可能马上觉着,这也太low了,这不就是:
//a=2,b=3 a = a + b;// a = 5 b = a - b;// b = 2 a = a - b; // a = 3
乍一看,没毛病,这没什么好说的,但是你可能忽略的一个问题,就是计算机的整数是有范围的,在边界以内,这么来搞没问题,如果两个数字,都在边界Integer.max附近,相加就超出范围了,并不能达到预期的结果,所以说“异或”才是最安全的做法。
其实,这个算法的巧妙之处在于他没有借助第三个变量就交换了两个变量的值,这个算法经常在面试题中会出现,当你知道了,就会觉着很简单。
上面介绍了选择排序的完整实现,以及各种取巧的办法。貌似很完美了,但是有个问题,就是这种排序,理论上只支持一种排序,要么升序,要么降序。如果要改变排序规则,我们需要修改交换的判断条件,需要硬编码。在c语言中,我们可以借助一个回调函数来作为判断的依据,我们在给排序算法传递参数的时候,将回调函数传进去,然后我们只需要修改回调函数的规则即可。
#include <stdio.h> int compare(int a, int b) { return a < b?1:0; } void selectSort(int arr[], int n, int (*pf)(int, int)) { for (int i = 0; i < n - 1; i++) { for (int j = i + 1; j < n; j++) { if (pf(arr[i], arr[j])) { arr[i] = arr[i] ^ arr[j]; arr[j] = arr[i] ^ arr[j]; arr[i] = arr[i] ^ arr[j]; } } } } int main() { int arr[] = { 6,5,4,3,2,1,7,8,9,0 }; selectSort(arr, 10, compare); for (int i = 0; i < 10; i++) printf("%d ", arr[i]); printf("\n"); return 0; }
其实这个算法就很接近c语言库提供的qsort算法了,看看算法的表示:
void qsort(void *base, size_t nitems, size_t size, int (*compar)(const void *, const void*))
其中参数base是数组,nitems表示数组元素个数,size表示元素的长度,也就是该类型的长度,整型是4,比较函数两个参数都是const void *,表示任意类型,并不局限于int。
利用qsort排序示例:
#include <stdio.h> #include <stdlib.h> #include <string.h> int compare(const void *a, const void *b) { int* ia = (int*)a; int* ib = (int*)b; return *ia > *ib ? 1 : 0; } int main() { int arr[] = { 6,5,4,3,2,1,7,8,9,0 }; qsort(arr, 10, 4, compare); for (int i = 0; i < 10; i++) { printf("%d ", arr[i]); } return 0; }
区别在于可以对各种类型的数据进行排序,不仅局限于整型。他可以对int,char,double进行排序。
我们需要注意的是这里对于字符串数组的排序,字符串可以表示为char *,字符串数组就是char **了。我们在设置回调函数作为判断条件的时候,需要对回调函数做正确的参数设置,void*这时候需要转为char**才是表示的字符串地址。
#include <stdio.h> #include <stdlib.h> #include <string.h> int compare(const void* a, const void* b) { return strcmp(*(char**)a, *(char**)b)>0?1:-1; } int main() { const char * fruit[] = {"banana","apple","orange","grapefruit","strawberry"}; int size = sizeof(fruit) / sizeof(fruit[0]); qsort(fruit, size , sizeof(char*), compare); for (int i = 0; i < size; i++) { printf("%s\n", fruit[i]); } return 0; }
以上是对选择排序的理解和整理,示例也通过vs2019编译通过。我这里遇到了一个问题,就是sizeof(char*)在64位机器下是8。
-
Python实现选择排序算法
2021-11-15 23:13:13第1关:选择排序 本关任务:首先给定一个长度大于1而且是乱序的列表,列表元素类型为整型,让后利用选择排序对列表元素进行排序,并输出每一次循环之后的结果。 # 选择排序 arraystr = input() array = list(map... -
Java选择排序算法源码
2013-12-31 21:53:36Java语言实现的选择排序算法,代码里头有详细注释,注释皆为简单英文,因为这个算法比较简单,欢迎新手下载学习使用,欢迎后期的学习交流! -
Python排序算法之选择排序定义与用法示例
2020-09-20 13:27:55主要介绍了Python排序算法之选择排序定义与用法,简单描述了选择排序的功能、原理,并结合实例形式分析了Python定义与使用选择排序的相关操作技巧,需要的朋友可以参考下 -
C语言-选择排序算法
2020-06-26 22:28:37n≤10),再输入n个整数,用选择排序法将它们从小到大排序后输出。 算法步骤 第一步:在未排序的 n 个数(a[0] ~ a[n - 1])中找到最小数,将它与 a[0] 交换; 第二步:在剩下未排序的 n - 1 个数(a[1] ~ a[n - 1]... -
浅谈排序算法:冒泡排序法和选择排序法的区别
2019-05-22 19:04:27之前学习了冒泡排序法和选择排序法,最近被老师问某个道题用的是什么排序法。自己居然答不出来,才发现自己没有真正弄懂,这两个算法的原理和区别,所以····· 1冒泡排序法 1.1什么是冒泡排序法? ... -
C语言 选择排序法
2020-12-21 22:16:09从键盘上输入10个数,用选择排序法按照从小到大的顺序输出 首先,分析一下什么叫做选择排序法。假设有十个元素a[0]~a[10],第一次将a[0]和a[1]—a[9]比较,如果其中有比a[0]小的数那么就互换值,此时a[0]一定是最小... -
C++ 数据结构 使用直接插入排序法、冒泡排序法和简单选择排序法这三种方法对顺序表进行排序
2021-12-22 16:57:451.设计一个程序,用于演示直接插入排序法、冒泡排序法或简单选择排序法,要求采用菜单的形式进行选择。 2.测试数据:265,301,751,129,937,863,742,694,76,438 3.测试:分别用上面的数据测试直接插入排序法... -
Lua中写排序算法实例(选择排序算法)
2020-09-22 04:41:48主要介绍了Lua中写排序算法实例,本文用一个选择排序算法为例讲解如何在Lua中写一个排序算法,需要的朋友可以参考下 -
单链表选择排序算法
2012-10-01 19:44:28单链表选择排序算法,包括带头结点和不带头结点的算法,对大家帮助很大。 -
C++实现选择排序算法
2019-04-22 20:00:31选择排序算法的基本思想:每一轮找到最小(升序)的元素放在当前序列的最前面。 特点:先找到最小元素,记录下标,最后交换。 时间复杂度:O(n^2)。以下为实现代码: #include <iostream> using ... -
C语言 简单选择排序算法(附源代码)
2019-05-06 22:45:57选择排序思路:将乱序序列先变成局部有序,再逐渐变成完全有序 例如: 数组有10个数 6,2,4,7,5,8,9,10,3,1 我先找到这10个里最小的数 1 然后和第一个数交换变成 1,2,4,7,5,8,9,10,3,6 再找数组下标1-9中最小的... -
三种排序方法:选择排序法、冒泡排序法、插入排序法
2022-03-19 17:29:36三种排序方法:选择、冒泡、插入排序法简单介绍概括 -
Java实现的各种排序算法(插入排序、选择排序算法、冒泡排序算法)
2020-09-01 20:41:17本文是小编给大家带来的java各种排序算法知识,包括插入排序、选择排序算法、冒泡排序算法,代码简单易懂,需要的朋友可以参考下 -
总结c语言基础算法——冒泡排序法和选择排序法
2022-03-16 12:51:04而在C语言中可以有很多排序的方法,这里着重介绍的是常用的较为基础和重要的算法——冒泡排序法和选择排序法。 下面将举一个例子进行讲解: 要求:从键盘输出10个整数,要求对它们按照从小到大的顺序排列。 ... -
C语言 简单选择排序法
2021-01-27 11:40:08简单选择排序是指一种排序算法,在简单选择排序过程中,所需移动记录的次数比较少。最好情况下,即待排序记录初始状态就已经是正序排列了,则不需要移动记录。 一、基本思想 在要排序的一组数中,选出最小的一个数与... -
数组排序的选择排序法(算法)
2020-11-25 06:06:52这是一个数组排序的选择排序法的类SelectionSort,通过选择对换最小值打到排序目的。 package algorithm; public class SelectionSort { public static void selectionSort(double[] list){ for(int i=0;i<... -
【算法】选择排序法
2018-08-22 09:24:311.选择排序法是将序列分为两段,有序前列和无序后列,每次查找无序后列中最大元素,将其插入到有序前列的最末尾处,直至无序后列最后一个元素,最终排序后的序列为降序序列 2.适用于包括数组和向量在内的序列 3.... -
java实现选择排序算法
2020-09-03 19:56:56本篇文章介绍直接选择排序算法的JAVA实现。直接选择排序算法的基本思想是:n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果