精华内容
下载资源
问答
  • 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 的相对位置发生了变化。所以选择排序是一种不稳定的排序算法。

     

     

    展开全文
  • python选择排序之简单选择排序

    千次阅读 2019-01-21 15:24:41
    python选择排序之简单选择排序

    python选择排序之简单选择排序

    简单选择排序

    简单选择排序:从无序数列中选取最小的元素和无序数列中的第一个元素交换,每轮都可以确定最小元素的位置。

    算法步骤

    1.循环取无序序列中的第一个元素
    2. 循环和后面的元素一一比较,直到选到一个最小的数,将它放在第一位

    python代码实现

    1. 将无序数列变有序
     # -*- coding:utf-8 -*-
    
    def simpleSelectSort(series):
    	for i in range(len(series)):
    		for j in range(i+1,len(series)):
    			if series[j] < series[i]:
    				series[j],series[i] = series[i],series[j]
    
    
    data = [5, 2, 8, 4, 7, 4, 3, 9, 2, 0,1,16]
    simpleSelectSort(data)
    print(data)
    
    展开全文
  • Python 选择排序

    万次阅读 2019-11-27 20:07:59
    Python 选择排序 基本原理: 从剩余待排序的数组中选择最小的数和待排序的数做对比。 时间复杂度为O(n^2),n为数组的个数。 空间复杂度为O(1)。 不稳定算法。 该图片来源于网络 选择排序 def select_sort(array): ...

    Python 选择排序

    基本原理:

    从剩余待排序的数组中选择最小的数和待排序的数做对比。

    时间复杂度为O(n^2),n为数组的个数。

    空间复杂度为O(1)。

    不稳定算法。
    选择排序算法
    该图片来源于网络

    选择排序

    def select_sort(array):
        """
        选择排序
    
        :param array: 数组
        :return: 已排序的数组
        """
        length = len(array)
        for i in range(length - 1):
            least = i
            for j in range(i + 1, length):
                if array[j] < array[least]:
                    # 更新least
                    least = j
            # 交换位置
            array[least], array[i] = array[i], array[least]
        return array
    展开全文
  • python实现选择排序算法

    千次阅读 2018-08-30 23:36:51
    前面我们讲解了选择排序算法,现在我们使用python代码来实现 #!/usr/bin/python # -*- coding: utf-8 -*- #选择排序 def select_sort(the_list): i = 0 while i &lt; len(the_list): j = i+1 while j &...

    前面我们讲解了选择排序算法,现在我们使用python代码来实现

    #!/usr/bin/python
    # -*- coding: utf-8 -*-
    #选择排序
    
    def select_sort(the_list):
        i = 0
        while i < len(the_list):
            j = i+1
            while j < len(the_list):
                if the_list[i] > the_list[j]:
                    the_list[i], the_list[j] = the_list[j], the_list[i]
                j = j+1
            i = i+1
        return the_list
    if __name__ == '__main__':
        the_list = [10, 1, 18, 30, 23, 12, 7, 5, 18, 17]
        print "排序前:" + str(the_list)
        print "排序后:" + str(select_sort(the_list))

    运行结果

    排序前:[10, 1, 18, 30, 23, 12, 7, 5, 18, 17]
    排序后:[1, 5, 7, 10, 12, 17, 18, 18, 23, 30]

     

    展开全文
  • 利用Python实现选择排序

    千次阅读 2016-07-21 17:27:33
    这里介绍排序算法思想,Python代码段和算法时间复杂度。选择排序算法思想对于一个无序的序列我们可以通过n-1趟排序得到排序结果。 我们定义一个无序序列list[R0…….RN] 1.初始状态:无序区为list 2.第一趟排序 ...
  • 选择排序 基本排序算法按时间复杂度分类 O(n^2) 冒泡排序 插入排序 选择排序 Q(n log n) 分而治之 快速排序 归并排序 冒泡排序 相邻的两个元素对比,大的数后推,遍历整个列表一次后,将...
  • Python选择排序算法

    千次阅读 2017-05-27 17:18:53
    Num01–>选择排序定义 选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)...
  • Python-冒泡排序选择排序

    千次阅读 2018-05-23 20:56:15
    冒泡排序def selectionSort(nb): for i in range(len(nb)): for j in range(i,len(nb)): if nb[i] &gt; nb[j]: nb[j],nb[i]=nb[i],nb[j] return nb选择排序def bubbleSort(nb):...
  • Python实现冒泡排序

    万次阅读 多人点赞 2020-07-06 23:22:30
    Python实现冒泡排序
  • # 冒泡排序:从小到大 # 第一轮:1 5 3 2 7 # 第二轮:1 3 2 5 7 ''' n = len(lt) # 外层循环控制比较多少轮 for i in range(n-1): # 内层循环控制元素的比较 #for j in range(n-1): for j in range(n-i-1)...
  • Python排序算法(一)冒泡排序、选择排序、插入排序

    千次阅读 多人点赞 2018-09-18 11:16:26
    今天总结一下Python中的排序算法。这篇文章有的排序算法是:冒泡排序选择排序、插入排序。 冒泡排序 先看一下代码。 ''' 冒泡排序 ''' def bubble_sort(aList): n = len(aList) for i in range(0, n - 1): ...
  • Python实现插入排序

    千次阅读 2020-07-08 23:51:35
    Python实现插入排序
  • Python 选择排序

    千次阅读 2019-05-15 19:00:49
    # 选择排序法 nums = [4, 1, 5, 10, -1, 9, 3, 2, 13, 7] count = len(nums) # count等于nums的长 for i in range(count-1): min = i for j in range(i+1, count): # 将剩下的进行遍历,遍历到count if nums[min...
  • def bubble_sort(list): for i in range(0, len(list)): is_sorted = True for j in range(0, len(list) - i - 1): if list[j] > list[j + 1]: list[j], list[j + 1] = list[j + 1], list[j] ...
  • Python实现指定排序函数进行排序

    千次阅读 2017-11-09 21:59:25
    利用冒泡排序、直接选择排序分别实现指定数组的升序、降序排列,并可以选择指定排序函数。 Python代码如下: #冒泡排序法实现升序排列 def bubble_sort(lists, sort = None): if not sort: count = len(lists) ...
  • # -*- coding: utf-8 -*- import locale ...cmp = locale.strcoll items = list('自挂东南枝'.decode('utf-8')) print 'before'.center(10, '=') print ''.join(items) items.sort(lambda x, y: cmp(x, y)) ...
  • Cormen等《算法导论》中的伪代码,用Python实现了冒泡排序选择排序、插入排序、快速排序、归并排序、二分法查找算法。 具体算法如下: 冒泡排序: def bubbleSort(alist): for passnum in range(0, len(a...
  • python list对象排序

    千次阅读 2018-10-13 22:17:56
    python list对象排序主要使用用sort函数。 list.sort(key=None,reverse=False) 由于list.sort()函数在排序时,使用的是小于号对比,所以自定义的对象类型需要override lt(小于)函数才能实现排序。 ...
  • Python3 list 排序函数详解

    万次阅读 多人点赞 2018-05-28 18:55:03
    Python3 list 排序函数详解 一、列表的sort排序函数 函数原型: list.sort(key=None,reverse=False) 函数功能: 对原列表进行排序,完成排序后,原列表变为有序列表。默认情况(不传入任何参数时)按字典顺序...
  • Pythonpython中sort排序使用

    千次阅读 2019-03-15 21:28:45
    本博客原文:【Pythonpython中你所忽视的一个列表sort排序功能 1.前言 昨天一学妹问我一个关于python的问题,当时在外忙碌,没时间细看。今天看一下,咋一看我还真的不知道这个问题,bookinfo.sort(reverse=True...
  • Python实现快速排序

    千次阅读 2014-06-22 19:50:52
    Python写了一个快速排序。简单练习一下
  • Python中冒泡排序

    千次阅读 2017-04-13 09:59:08
    Python中冒泡排序算法:

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 314,031
精华内容 125,612
关键字:

python写选择排序

python 订阅