精华内容
下载资源
问答
  • 选择排序算法

    千次阅读 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

      选择排序算法的详细过程如下图所示。

    在这里插入图片描述
      时间复杂度: 对于长度为nn的数组,代码执行的时间都花费在内层for循环中的比较语句和外层for循环里的交换语句了。外层for循环执行 n1n-1次,那么交换(swap)就执行n1n-1次,时间复杂度为O(n)O(n);内层for循环中的比较语句执行次数为(n1)+(n2)++2+1=n(n1)2=12n212n(n-1) + (n-2) +…+2+1=\frac{n(n-1)}{2}=\frac{1}{2}n^{2}-\frac{1}{2}n,时间复杂度为O(n2)O(n^2)。所以,选择排序算法的时间复杂度为O(n2)O(n^2)

      空间复杂度: O(1)O(1)

      稳定性: 由于选择元素之后会发生交换操作,有可能把前面的元素交换到后面,所以选择排序不是稳定的排序,如下图所示。

    在这里插入图片描述

    展开全文
  • 冒泡排序算法和选择排序算法比较

    千次阅读 2021-05-09 11:55:39
      选择排序算法内容详情→选择排序算法。   冒泡排序算法和选择排序算法的区别: 冒泡排序是比较相邻位置的两个数;而选择排序是按顺序比较,找出最大值或者最小值。 冒泡排序扫描一遍数组,位置不对需要不停地...

      冒泡排序算法详细内容见→冒泡排序算法
      选择排序算法详细内容见→选择排序算法

      冒泡排序算法和选择排序算法的区别

    1. 冒泡排序是比较相邻位置的两个数;而选择排序是按顺序比较,找出最大值或者最小值。
    2. 冒泡排序扫描一遍数组,位置不对需要不停地互换位置;而选择排序扫描一遍数组,只需要换一次位置,所以一般来说选择排序比冒泡排序效率高。
    3. 冒泡排序是通过数去找位置;而选择排序是给定位置去找数。

      冒泡排序算法的优缺点:
        优点:比较简单,空间复杂度较低,是稳定的;
        缺点:时间复杂度太高,效率慢。

      选择排序算法的优缺点:
        优点:一轮比较只需要换一次位置;
        缺点:效率慢,不稳定(例如对于数组{5,8,5,2,9},第一遍选择第一个元素5会和2交换,那么原序列中两个5的相对位置前后顺序就破坏了)。

    展开全文
  • 简单选择排序算法选择排序算法中的一种,另外一种选择排序就是堆排序了,这种简单的选择排序算法的复杂度其实和冒泡排序算法一样,并且最差情况,平均情况和最好的情况复杂度都是一样的,是一种不稳定的排序算法,...

    引言

    简单选择排序算法是选择排序算法中的一种,另外一种选择排序就是堆排序了,这种简单的选择排序算法的复杂度其实和冒泡排序算法一样,并且最差情况,平均情况和最好的情况复杂度都是一样的,是一种不稳定的排序算法,主要思路和实现原理也都很简单,就是把一个无序数列中的数找出一个最小的数(从小到大排序的情况,从大到小则找出最大的数)然后与序列的最前面的数进行交换,然后循环依次放置即可。

    具体思路

    其实实现思路和直接插入排序有点像,都是把数组分成两个部分,一个是有序的部分,一个是无序的部分,但是直接插入排序是要不断插入在有序部分,需要在有序部分中找到一个合适的位置插入,但简单选择排序则不一样,只需要把最小的找出来放到最前面,之后只需遍历无序部分,然后把最小的找出来依次与前面有序部分的末尾的后一位(也就是无序部分的第一个数)进行交换就可以了。假设现在有一个数列为a,其中元素为5,11,43,6,2,9,7,16 每次查找的步骤如下

          (有序部分)2,11,43,6,5,9,7,16(无序部分)//找出无序部分中最小的数2,这里2就是第一位,无需交换
    i=0   2(有序部分),11,43,6,5,9,7,16(无序部分)//找出无序部分中最小的数5,然后与无序部分第一位11进行交换
    i=1   2,5(有序部分),43,6,11,9,7,16(无序部分)//找出无序部分中最小的数6,然后与无序部分第一位43进行交换
    i=2   2,5,6(有序部分),43,11,9,7,16(无序部分)
    i=3   2,5,6,7(有序部分),11,9,43,16(无序部分)
    i=4   2,5,6,7,9(有序部分),11,43,16(无序部分)
    i=5   2,5,6,7,9,11(有序部分),43,16(无序部分)
    i=6   2,5,6,7,9,11,16(有序部分),43(无序部分)
    i=7   2,5,6,7,9,11,16,43(有序部分)(无序部分)
    

    代码实现

    #include<iostream>
    using namespace std;
    int selectionSort(int *a,int n)
    {
    	int min,index; 
    	for(int i=0;i<n;i++)
    	{
    		min=a[i];//设置最小初始值,一般设置为无序部分第一位数 
    		index=i;//保存最小那个数的index 
    		for(int j=i+1;j<n;j++)//从无序部分第二位开始找最小值 
    		{
    			if(min>a[j])
    			{
    				min=a[j];//找到最小值更新min值 
    				index=j;//保存最小值的下标 
    			}
    		}
    		swap(a[i],a[index]);//无序部分第一位数和最小值进行交换 
    	}
    }
    int main()
    {
    	int n;
    	cin>>n;
    	int *a=new int[n]; 
    	for(int i=0;i<n;i++)
    		cin>>a[i];
    	selectionSort(a,n);
    	for(int i=0;i<n;i++)
    		cout<<a[i]<<" ";
    	cout<<endl;
    	delete []a;
    	return 0;	
    } 
    

    所以以上排序的复杂度是O(n^2),空间复杂度是O(1),并且这是一个不稳定的排序算法,因为当无序数列中出现两个相同的数时,如果相同的其中一个数在第一位,那么与最小的一个数(最小的一个数如果在另一个相同的数的后面)交换后这两个相同的数前后顺序就破坏了,所以这是一种不稳定的排序。

    展开全文
  • 排序算法系列:选择排序算法

    千次阅读 2016-05-24 17:20:39
    选择排序算法也需要将一个完整的序列切分成两个部分,一个部分有序,一个部分无序。这一点它和插入排序是一致的。在前面我们说插入排序是将第 [i + 1] 个元素插入到第一部分的有序序列中,如果你还有印象的话。那么...

    概述

    这是一个相对简单的排序算法。为什么这么说呢?因为不需要什么思考,你就可以掌握并使用它。


    版权说明

    著作权归作者所有。
    商业转载请联系作者获得授权,非商业转载请注明出处。
    本文作者:Q-WHai
    发表日期: 2016年5月24日
    本文链接:https://qwhai.blog.csdn.net/article/details/51491810
    来源:CSDN
    更多内容:分类 >> 算法与数学


    目录

    算法原理

    选择排序算法也需要将一个完整的序列切分成两个部分,一个部分有序,一个部分无序。这一点它和插入排序是一致的。在前面我们说插入排序是将第 [i + 1] 个元素插入到第一部分的有序序列中,如果你还有印象的话。那么在选择排序中则是第 j 个元素(i < j <= n),插入到第 i 个位置。
    下面这幅图可以帮助你更好地理解这一点(当然你可以完全不需要图解的帮助)。

    这里写图片描述


    算法步骤

    1. 序列会被人为抽象地分成两个部分,分别定义成序列 T1 和序列 T2(原始序列为 T0)。
    2. 默认 T1 序列中的第 0 个元素是有序的(因为只有一个元素 a[0] 嘛,自然是有序的);
    3. 从 i = 0 开始,每次从 T2 中选出一个最小的元素 a[minIndex],将 a[minIndex] 与 a[i] 进行交换;
    4. 重复过程 3,直到序列 T2 中的元素全部被填入到序列 T1

    算法实现

    /*
         * 排序算法的核心模块
         * 
         * @param array
         *      待排序数组
         */
        private void sortCore(int[] array) {
            int arraySize = array.length;
            
            for (int i = 0; i < arraySize; i++) {
                int minValue = Integer.MAX_VALUE;
                int minIndex = 0;
                for (int j = i; j < arraySize; j++) {
                    if (minValue > array[j]) {
                        minValue = array[j];
                        minIndex = j;
                    }
                }
                
                ArrayUtils.swap(array, minIndex, i);
            }
        }
    

    算法复杂度

    排序方法 时间复杂度 空间复杂度 稳定性 复杂性
    平均情况 最坏情况 最好情况
    选择排序 O($n^{2}$) O($n^{2}$) O($n^{2}$) O(n) 稳定 简单

    Ref

    • 《大话数据结构》

    Github源码下载


    征集

    如果你也需要使用ProcessOn这款在线绘图工具,可以使用如下邀请链接进行注册:
    https://www.processon.com/i/56205c2ee4b0f6ed10838a6d

    展开全文
  • 链表选择排序算法功能实现演示

    万次阅读 2020-05-02 11:58:28
    算法: 狭义的算法是与数据的存数方式密切相关 广义的算法是与数据的存储方式无关 泛型: 利用某种技术达到的效果就是:不同的存数方式,执行的操作是一样的 #include <stdio.h> #include <malloc.h> #...
  • 简单选择排序算法介绍简单选择排序(Simple Selection Sort)就是通过n-1次关键字排序之间的比较,从n-i+1个记录中选择关键字最小的记录,并和第i(1&lt;=i&lt;=n)记录交换。这是一般书上的定义。实际上...
  • 一文搞定选择排序算法

    千次阅读 多人点赞 2020-06-03 16:31:22
    这次终于把选择排序算法给说清楚了
  • 直接选择排序算法

    热门讨论 2016-11-13 21:51:10
    直接选择排序算法
  • 选择排序算法(升序)

    2016-10-27 20:19:17
    选择排序算法
  • 大二学过一学期的数据结构,对一些数列排序算法有一些了解,但是每当遇到排序的时候就不由自主的拿起书来看,很明显还是掌握的不扎实,因此今天准备把这两个简单的排序算法进行一次彻底的分析,也当做复习了,小编先...
  • 选择排序算法的过程: 从所有序列中先找到最小的,然后放到第一个位置。之后再看剩余元素中最小的,放到第二个位置……以此类推,就可以完成整个的排序工作了。可以很清楚的发现,选择排序是固定位置,找元素。寻找...
  • 如何选择排序算法

    2018-09-04 21:59:33
    1.排序算法时间复杂度、空间复杂度、稳定性比较 https://blog.csdn.net/yushiyi6453/article/details/76407640 2.排序算法的分类及如何选择 ...3.如何选择排序算法 https://www.cnblogs.com/hustdc...
  • 简单选择排序算法

    千次阅读 2018-04-02 11:28:42
    简单选择排序算法 简单选择排序算法:即通过n-i次关键字间的比较,从n-i+1个记录中选出关键字最小的记录,并和第i个记录交换。 排序过程如下所示: 具体实现算法如下: void SimpleSelectionSort(int *array...
  • “深入理解”—选择排序算法

    万次阅读 热门讨论 2016-07-10 11:37:25
    选择排序算法有两种:直接选择排序和堆排序
  • 直接选择排序(Bubble Sort)是一种典型的选择排序算法,通过不断选择序列中最大(小)的元素。 一、算法基本思想 (1)基本思想 直接选择排序的基本思想就是:不断从未排序队列中选择最大(小)的元素放...
  •  简单选择排序算法基本操作:每一趟在n-i+1(i=1,2,…n-1)个记录中选取关键字最小的记录作为有序序列中第i个记录。时间复杂度:O(n^2)2. 树形选择排序算法树形选择排序又称为锦标赛排序,是一种按照锦标赛的思想...
  • 选择排序算法,与冒泡排序的优势就是减少了交换操作。代码如下: void selectSort(int A[], int n){ int min; for (int i = 0; i < n-1; i++) { min = i; for (int j = i + 1; j< n ; j++) { if (A[j] &....
  • 接下来我们学习第二种排序算法:选择排序选择排序算法通过选择和交换来排序,其排序流程如下: 1)首先从原始数组中选择最小的一个数据,将其和第一个位置的数据交换 2)接着从剩下的n-1个数据选择出最小的数据,...
  • 两种常用的选择排序算法--简单选择排序、堆排序
  • C++篇——C++实现冒泡排序和选择排序算法摘要冒泡法代码运行结果选择排序法代码运行结果 摘要 本文通过C++实现了两类基础且经典的排序算法(冒泡法和选择排序法)。 冒泡法 代码 #include <iostream> using ...
  • Python 实现选择排序算法

    千次阅读 2019-04-07 09:00:37
    选择排序算法如下: 首先在未排序序列中找到最小(大)元素, 存放到排序序列的起始位置 然后再从剩余未排序元素中继续寻找最小(大)元素,放到已排序列的末尾 以此类推 其时间复杂度: ​​​​​​​最优时间...
  • 选择排序算法(Selection Sort)

    千次阅读 2017-07-10 15:22:02
    选择排序算法的java实现。
  • 编程实现输入10个整数,并将其按降序排序并输出(可以使用选择排序算法或者冒泡排序算法)。 代码内容: /*编程实现输入10个整数, 并将其按降序排序并输出( 可以使用选择排序算法或者冒泡排序算法)。*/ #...
  • 字符串排序————选择排序算法 我们来处理一个按字母表顺序排序字符串的问题,主要用strcmp()函数来确定两个字符串的顺序,代码如下: /* * @Author: Your name * @Date: 2020-02-24 14:35:13 * @Last Modified...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 40,662
精华内容 16,264
关键字:

选择排序算法