精华内容
下载资源
问答
  • Python实现选择排序

    2020-07-12 17:58:28
    Python实现选择排序

    Python实现选择排序

    一、选择排序简介

    选择排序(Selection sort)是一种简单直观的排序算法。

    选择排序首先从待排序列表中找到最小(大)的元素,存放到元素列表的起始位置(与起始位置进行交换),作为已排序序列,第一轮排序完成。然后,继续从未排序序列中找到最小(大)的元素,存放到已排序序列的末尾。直到所有元素都存放到了已排序序列中,列表排序完成。

    选择排序每次都是去找最小(大)的元素,隐含了一种挑选的过程,所以被称为选择排序。

    二、选择排序原理

    选择排序的原理如下:

    1. 从待排序列表中找到最小的元素(升序排列,降序排列则找最大的元素),存放到列表的起始位置,作为已排序的序列。

    2. 继续从未排序序列中找到最小的元素,存放到已排序序列的末尾(同时也是未排序序列的起始位置)。

    3. 重复第2步,直到所有元素都已经存放到了已排序序列,则列表排序完成。

    以列表 [10, 17, 50, 7, 30, 24, 27, 45, 15, 5, 36, 21] 进行升序排列为例。列表的初始状态如下图。

    要进行升序排列,则每轮排序都要找到最小的元素。

    1. 找到元素列表中最小的元素,与列表起始位置的元素进行对比,如果最小的元素小于起始位置的元素,则交换位置。

    2. 5小于10,交换位置,将最小的元素存放到列表的起始位置。

    3. 将最小的元素作为已排序序列,后面的元素为未排序序列。

    4. 继续找到未排序序列中的最小元素,与未排序序列的第一个元素(已排序序列的末尾)比较,如果最小的元素更小则交换位置。

    5. 7小于17,交换位置。将最小的元素存放在已排序序列的末尾。

    6. 第二轮排序完成后,已排序序列的长度变成二,未排序序列的长度减一。

    7. 继续重复上面的4,5步骤,找到未排序序列中的最小元素,存放到已排序序列的末尾。每进行一轮排序,已排序序列的长度加一,未排序序列的长度减一,直到未排序序列的长度为1,列表排序完成。排序结果如下图。

    三、Python实现选择排序

    # coding=utf-8
    def selection_sort(array):
        for i in range(len(array)-1):
            min_index = i
            for j in range(i+1, len(array)):
                if array[j] < array[min_index]:
                    min_index = j
            if min_index != i:
                array[i], array[min_index] = array[min_index], array[i]
        return array
    
    
    if __name__ == '__main__':
        array = [10, 17, 50, 7, 30, 24, 27, 45, 15, 5, 36, 21]
        print(selection_sort(array))

    运行结果:

    [5, 7, 10, 15, 17, 21, 24, 27, 30, 36, 45, 50]

    代码中,i 表示第几轮排序,j 表示走访未排序序列中元素的索引,将走访到的每一个元素与未排序序列的第一个元素进行比较。min_index 用于标记当前这一轮排序中最小元素的索引,如果走访到 j 索引的元素比 min_index 索引的元素小,则将 j 赋值给 min_index,j 继续走访。走访完所有元素后,将 min_index 索引的元素交换到 i 索引的位置(未排序序列的起始位置)。

    四、选择排序的时间复杂度和稳定性

    1. 时间复杂度

    在选择排序中,不管待排序列表的初始状态如何,都不影响排序的时间复杂度。选择排序需要进行 n-1 轮排序,每一轮排序需要进行 n-i 次比较,i 的平均值是 n/2 ,时间复杂度为 T(n)=n(n-1)/2 ,再乘每次操作的步骤数(常数,不影响大O记法),所以选择排序的时间复杂度为 O(n^2) 。

    2. 稳定性

    在选择排序中,每次都是选择未排序序列中的最小元素,交换到未排序序列的起始位置。存在相等的元素时,如果最小的元素都比它们靠后,最小的元素与相对位置靠前的元素进行交换,则它们的相对位置就发生了变化。如 [10, 10, 5],进行选择排序后两个 10 的相对位置发生了变化。所以选择排序是一种不稳定的排序算法。

     

     

    展开全文
  • Java实现选择排序

    2017-12-04 19:42:24
    Java实现选择排序版权声明:转载前请留言获得作者许可,转载后标明作者 QiuYuHaOo 和原文出处。原创不易,感谢您的支持 选择排序原理 Selection Sort使用实例 选择排序的优化 1.选择排序原理选择排序(Selection ...

    Java实现选择排序

    版权声明:转载前请留言获得作者许可,转载后标明作者 QiuYuHaOo 和原文出处。原创不易,感谢您的支持

    • 选择排序原理

    • Selection Sort使用实例

    • 选择排序的优化


    1.选择排序原理

    选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完。

    2.Selection Sort使用实例

    import java.util.Scanner;
    
    public class Test {
        public static void main(String[] args) {
            System.out.println("请输入数字个数:");
            Scanner scanner = new Scanner(System.in);
            int n = scanner.nextInt();
    
            int[] a = new int[n];
            for(int i = 0; i < a.length; i++) {
                a[i] = scanner.nextInt();
            }
            scanner.close();
            print(a);
            selectionSort(a);
            print(a);
        }
        public static void print(int[] a) {
            for(int i = 0; i < a.length; i++) {
                System.out.print(a[i] + " ");
            }
            System.out.println();
        }
        public static void selectionSort(int[] a) {
            for(int i = 0;i < a.length; i++) {
                for(int j = i+1;j < a.length;j++) {
                //当后者比前者小时,交换
                    if(a[j]<a[i]){
                        int temp = a[i];
                        a[i] = a[j];
                        a[j] = temp;                    
                    }
                }
            }
        }
    }
    

    3.选择排序的优化

    public static void selectionSort(int[] a){
            int temp, k;
            for(int i=0; i<a.length; i++) {
                k=i;
                for(int j=k+1; j<a.length; j++) {
                    if(a[j] < a[k]){
                        k = j;              
                    }
                }
                if(k != i) {
                    temp = a[i];
                    a[i] = a[k];
                    a[k] = temp;
                }
            }
        }

    各个排序算法的时间复杂度

    展开全文
  • shell 实现 选择排序

    2015-05-22 15:41:02
    shell 实现选择排序
    #!/bin/bash


    a=(9 8 7 6 5 4 3 2 1 0)




    for(( i=0; i<9; i++ ))
    do
            k=$i
            for(( j=$i+1; j<10; j++ ))
            do
                    if [ ${a[$k]} -gt ${a[$j]} ]
                    then
                            k=$j
                    fi
            done


            if [ $i -ne $k ]
            then
                    temp=${a[$i]}
                    a[$i]=${a[$k]}
                    a[$k]=$temp
            fi
    done


    for i in ${a[@]}
    do
            echo -n "$i "
    done
    echo ""
    展开全文
  • C语言实现选择排序

    2015-02-14 15:23:13
    C语言实现选择排序

    自己用C语言实现的选择排序:)

    # include <stdio.h>
    
    
    void selection_sort(int a[], int n) {
        int min, k;
        for (int i=0; i<n; i++){
            min = a[i];
            k = i;
            for (int j=i+1; j<n; j++) {
                if (a[j] < min) {
                    min = a[j];
                    k = j;
                }
            }
            int temp = a[k];
            a[k] = a[i];
            a[i] = temp;
        }
    }
    
    void main() {
        int a[5] = {20, 10, 40, 30, -50};
        selection_sort(a, 5);
        for (int i=0; i<5; i++) {
            printf("%d\t", a[i]);
        }
    }
    展开全文
  • java实现选择排序

    2016-05-13 11:06:50
    java实现选择排序,欢迎讨论
  • **选择排序**python实现 选择排序算法新的开始python 代码实现小结 python实现 选择排序算法 新的开始 最近又重新翻看了算法的书,本科的时候学习算法完全是为了应付考试,当时书上的算法都是伪代码,有的是用C写的...
  • C++ 实现选择排序算法

    2020-01-05 12:04:34
    C++ 实现选择排序算法 思路 选择排序 选择排序(升序) 就是 从一组数字 选出 一个最小的元素 放在 第一个位置 之后在 剩下 的 元素中, 在选择一个 最小 的 位置 放入 第二位置 最后只剩下 一个元素, 整个排序过程...
  • Python3 实现选择排序和插入排序一、选择排序的实现原理思路代码实现小结二、插入排序实现原理思路代码实现小结 一、选择排序的实现 原理思路 对给定的一组数据,经过第一轮依次比较,找到最小的那个数,然后把最小...
  • 用java实现选择排序SelectSort 用java实现选择排序SelectSort 用java实现选择排序SelectSort
  • 实现选择排序算法

    2016-05-25 14:44:20
    /*** 实现选择排序算法* 程序算法排序* 实现选则排序算法** 选择排序算法的原理:* 先将数据列表中的第一个数与后面的每一个数进行比较,把小的数放在第一个数中,* 从而找出最小的,然后在用第二个数与后面的每一个...
  • C语言实现简单选择排序 文章目录C语言实现简单选择排序简单选择排序算法1.交换操作2.简单选择排序算法实现项目完整代码运行效果图 简单选择排序算法 1.交换操作 //交换实现 void swap(int &a, int &b) { ...
  • 优先级队列应用之实现选择排序、插入排序和堆排序。
  • python实现选择排序算法一、选择排序算法实现原理基本思想具体步骤二、图解选择排序三、py代码实现选择排序算法 一、选择排序算法实现原理 基本思想 首先在未排序序列中找到最小(大)元素,存放到排序序列的起始...
  • ARM_汇编程序实现选择排序,很好的介绍了排序的过程
  • C语言单链表实现选择排序

    千次阅读 2019-03-12 12:00:27
    链表实现选择排序有两种方法,一种是交换节点内的数据,比较简单。我这里使用的是第二种方法,交换节点。 #include&lt;stdio.h&gt; #include&lt;stdlib.h&gt; #include&lt;string.h&gt; #...
  • js实现选择排序

    千次阅读 2020-12-22 10:24:47
    选择排序:第一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,然后再从剩余的未排序元素中寻找到最小(大)元素,然后放到已排序的序列的末尾。以此类推,直到全部待排序的数据元素的...
  • java实现选择排序算法

    2016-10-11 09:55:40
    选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小(大)元素,存放到排序序列...下面是java实现选择排序的代码片段: public void selectionSort(int data[],int n)
  • 今天用Python 3版本实现选择排序和冒泡排序。 选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序...
  • 选择类:简单选择排序、堆排序 归并类:二路归并排序 基数类:多关键字排序 九种算法的时间复杂度、空间复杂度和稳定性小结如下: 本文放出选择算法的两种排序算法代码。 简单选择排序 void SelectSort(int R[], ...
  • 用php实现选择排序(简单排序)算法选择排序算法的原理其实很简单,就是从头开始选定一个位置,令该位置上的数与其他位置上的数进行比对,将该位置上的与更小位置上的数进行交换,从而实现排序。 /** * Created by ...
  • C# 实现选择排序

    2020-12-13 15:54:14
    选择排序 选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放...
  • Java实现选择排序和冒泡排序

    万次阅读 多人点赞 2019-07-20 21:23:47
    选择排序开始的时候,我们从第一个元素开始扫描整个列表,找到它的最小元素,然后和第一个元素交换,将最小元素和第一个元素交换位置;然后,我们从第二个元素开始扫描剩下的n-1个元素,找到这n-1个元素中的最小元素...
  • MIPS汇编语言实现选择排序算法

    千次阅读 2018-04-15 16:17:14
    MIPS汇编语言实现选择排序算法 1.流程图 2.C代码 3.MIPS代码(附注释) MIPS汇编语言实现选择排序算法 1.流程图 2.C代码 #include &lt;stdio.h&gt; #include &lt;stdlib.h&gt; #...
  • C++实现选择排序

    千次阅读 2019-11-03 18:10:25
    选择排序 选择排序(SelectSort)是一种简单直观的排序算法。 算法原理:第一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,然后再从剩余的未排序元素中寻找到最小(大)元素,然后放...
  • python实现选择排序

    2020-10-24 14:06:59
    题目要求: 编写函数,对列表元素用选择法排序。编写主程序, 输入列表元素,调用函数排序,显示列表...选择排序法是一种不稳定的排序算法。 它的工作原理是每一次从待排序的数据元素中选出最小(或最大)的一个元素,
  • c#实现选择排序算法

    2011-05-26 09:20:00
    c#实现选择排序算法
  • 递归实现选择排序

    千次阅读 2012-05-12 23:14:52
    Q:递归实现选择排序 A: PS: 递归三要素: 1.可以把要解决的问题转化为一个新问题,而这个新的问题的解决方法仍与原来的解决方法相同,只是所处理的对象有规律地递增或递减。2、可以应用这个转化过程使问题得到...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 21,084
精华内容 8,433
关键字:

实现选择排序