当前位置:首页 > 编程教程 > Python技术文章 > Python 对输入的数字进行排序的方法

Python如何对输入的数字进行排序

  • 发布时间:
  • 作者:码农之家
  • 点击:138

这篇文章主要知识点是关于Python、数字排序、python常见排序算法基础教程 的内容,如果大家想对相关知识点有系统深入的学习,可以参阅以下电子书

Python编程之美:最佳实践指南
  • 类型:Python编程大小:29.3 MB格式:PDF作者:肯尼思·赖茨
立即下载

Python 对输入的数字进行排序的方法

要求,输入一串数字,并以列表的形式打印出来。

number = input('请输入一串数字:') 
print(number) 
print(type(number)) 

假设输入12345,得到结果如下:

请输入一串数字:12345 
12345 
<class 'str'> 

可以看出,变量number类型为字符串类型。

将其转换成列表,如下所示:

print(list(number)) 

得到:

['1', '2', '3', '4', '5'] 

显然,我们想得到是:[1,2,3,4,5],这种以数字形式排列的列表

可以采取如下形式:

print(list(map(int,list(number)))) 

得到:

[1,2,3,4,5] 

采用map函数,将字符串列表中的每一个字符转换成数字。

在得到数字列表后,采用sort()函数就可以对其进行排序了。

完成代码如下:

number = input('请输入一串数字:') 
number_list = list(map(int,list(number))) 
number_list.sort() 
print('排序后的数字列表为:%s' % number_list) 

得到结果如下:

请输入一串数字:2586417 
排序后的数字列表为:[1, 2, 4, 5, 6, 7, 8] 

以上这篇Python 对输入的数字进行排序的方法就是小编分享给大家的全部内容了,希望能给大家一个参考,也希望大家多多支持码农之家。

python常见排序算法基础教程

前言:前两天腾讯笔试受到1万点暴击,感觉浪费我两天时间去牛客网做题……这篇博客介绍几种简单/常见的排序算法,算是整理下。

时间复杂度

(1)时间频度一个算法执行所耗费的时间,从理论上是不能算出来的,必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试,只需知道哪个算法花费的时间多,哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例,哪个算法中语句执行次数多,它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。

(2)时间复杂度在刚才提到的时间频度中,n称为问题的规模,当n不断变化时,时间频度T(n)也会不断变化。但有时我们想知道它变化时呈现什么规律。为此,我们引入时间复杂度概念。 一般情况下,算法中基本操作重复执行的次数是问题规模n的某个函数,用T(n)表示,若有某个辅助函数f(n),使得当n趋近于无穷大时,T(n)/f(n)的极限值为不等于零的常数,则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n)),称O(f(n))为算法的渐进时间复杂度,简称时间复杂度。

指数时间

指的是一个问题求解所需要的计算时间m(n),依输入数据的大小而呈指数成长(即输入数据的数量依线性成长,所花的时间将会以指数成长)

for (i=1; i<=n; i++)
 x++;
for (i=1; i<=n; i++)
 for (j=1; j<=n; j++)
 x++;

第一个for循环的时间复杂度为Ο(n),第二个for循环的时间复杂度为Ο(n2),则整个算法的时间复杂度为Ο(n+n2)=Ο(n2)。

常数时间

若对于一个算法的上界与输入大小无关,则称其具有常数时间,记作时间。一个例子是访问数组中的单个元素,因为访问它只需要一条指令。但是,找到无序数组中的最小元素则不是,因为这需要遍历所有元素来找出最小值。这是一项线性时间的操作,或称时间。但如果预先知道元素的数量并假设数量保持不变,则该操作也可被称为具有常数时间。

对数时间

若算法的T(n) =O(logn),则称其具有对数时间

常见的具有对数时间的算法有二叉树的相关操作和二分搜索。

对数时间的算法是非常有效的,因为每增加一个输入,其所需要的额外计算时间会变小。
递归地将字符串砍半并且输出是这个类别函数的一个简单例子。它需要O(log n)的时间因为每次输出之前我们都将字符串砍半。 这意味着,如果我们想增加输出的次数,我们需要将字符串长度加倍。

线性时间

如果一个算法的时间复杂度为O(n),则称这个算法具有线性时间,或O(n)时间。非正式地说,这意味着对于足够大的输入,运行时间增加的大小与输入成线性关系。例如,一个计算列表所有元素的和的程序,需要的时间与列表的长度成正比。

一、冒泡算法

基本思想:

在要排序的一组数中,对当前还未排好序的范围内的全部数,自上而下对相邻的两个数依次进行比较和调整,让较大的数往下沉,较小的往上冒。即:每当两相邻的数比较后发现它们的排序与排序要求相反时,就将它们互换。

冒泡排序的示例:

python常见排序算法基础教程

算法实现:

def bubble(array):
 for i in range(len(array)-1):
 for j in range(len(array)-1-i):
 if array[j] > array[j+1]: # 如果前一个大于后一个,则交换
 temp = array[j]
 array[j] = array[j+1]
 array[j+1] = temp


if __name__ == "__main__":
 array = [265, 494, 302, 160, 370, 219, 247, 287,
 354, 405, 469, 82, 345, 319, 83, 258, 497, 423, 291, 304]
 print("------->排序前<-------")
 print(array)
 bubble(array)
 print("------->排序后<-------")
 print(array)

输出:

------->排序前<-------
[265, 494, 302, 160, 370, 219, 247, 287, 354, 405, 469, 82, 345, 319, 83, 258, 497, 423, 291, 304]
------->排序后<-------
[82, 83, 160, 219, 247, 258, 265, 287, 291, 302, 304, 319, 345, 354, 370, 405, 423, 469, 494, 497]

讲解:

以随机产生的五个数为例: li=[354,405,469,82,345]
冒泡排序是怎么实现的?
首先先来个大循环,每次循环找出最大的数,放在列表的最后面。在上面的例子中,第一次找出最大数469,将469放在最后一个,此时我们知道
列表最后一个肯定是最大的,故还需要再比较前面4个数,找出4个数中最大的数405,放在列表倒数第二个......

5个数进行排序,需要多少次的大循环?? 当然是4次啦!同理,若有n个数,需n-1次大循环。

现在你会问我: 第一次找出最大数469,将469放在最后一个??怎么实现的??
嗯,(在大循环里)用一个小循环进行两数比较,首先354与405比较,若前者较大,需要交换数;反之不用交换。
当469与82比较时,需交换,故列表倒数第二个为469;469与345比较,需交换,此时最大数469位于列表最后一个啦!

难点来了,小循环需要多少次??

进行两数比较,从列表头比较至列表尾,此时需len(array)-1次!! 但是,嗯,举个例子吧: 当大循环i为3时,说明此时列表的最后3个数已经排好序了,不必进行两数比较,故小循环需len(array)-1-3. 即len(array)-1-i

冒泡排序复杂度:

时间复杂度: 最好情况O(n), 最坏情况O(n^2), 平均情况O(n^2)

空间复杂度: O(1)

稳定性: 稳定

简单选择排序的示例:

python常见排序算法基础教程

二、选择排序

The selection sort works as follows: you look through the entire array for the smallest element, once you find it you swap it (the smallest element) with the first element of the array. Then you look for the smallest element in the remaining array (an array without the first element) and swap it with the second element. Then you look for the smallest element in the remaining array (an array without first and second elements) and swap it with the third element, and so on. Here is an example

基本思想:

在要排序的一组数中,选出最小(或者最大)的一个数与第1个位置的数交换;然后在剩下的数当中再找最小(或者最大)的与第2个位置的数交换,依次类推,直到第n-1个元素(倒数第二个数)和第n个元素(最后一个数)比较为止。

简单选择排序的示例:

python常见排序算法基础教程

算法实现:

def select_sort(array):
 for i in range(len(array)-1): # 找出最小的数放与array[i]交换
 for j in range(i+1, len(array)):
 if array[i] > array[j]:
 temp = array[i]
 array[i] = array[j]
 array[j] = temp


if __name__ == "__main__":
 array = [265, 494, 302, 160, 370, 219, 247, 287,
 354, 405, 469, 82, 345, 319, 83, 258, 497, 423, 291, 304]
 print(array)
 select_sort(array)
 print(array)

选择排序复杂度:

时间复杂度: 最好情况O(n^2), 最坏情况O(n^2), 平均情况O(n^2)

空间复杂度: O(1)

稳定性: 不稳定

举个例子:序列5 8 5 2 9, 我们知道第一趟选择第1个元素5会与2进行交换,那么原序列中两个5的相对先后顺序也就被破坏了。

排序效果:

python常见排序算法基础教程

三、直接插入排序

插入排序(Insertion Sort)的基本思想是:将列表分为2部分,左边为排序好的部分,右边为未排序的部分,循环整个列表,每次将一个待排序的记录,按其关键字大小插入到前面已经排好序的子序列中的适当位置,直到全部记录插入完成为止。

python常见排序算法基础教程

插入排序非常类似于整扑克牌。

在开始摸牌时,左手是空的,牌面朝下放在桌上。接着,一次从桌上摸起一张牌,并将它插入到左手一把牌中的正确位置上。为了找到这张牌的正确位置,要将它与手中已有的牌从右到左地进行比较。无论什么时候,左手中的牌都是排好序的。

也许你没有意识到,但其实你的思考过程是这样的:现在抓到一张7,把它和手里的牌从右到左依次比较,7比10小,应该再往左插,7比5大,好,就插这里。为什么比较了10和5就可以确定7的位置?为什么不用再比较左边的4和2呢?因为这里有一个重要的前提:手里的牌已经是排好序的。现在我插了7之后,手里的牌仍然是排好序的,下次再抓到的牌还可以用这个方法插入。编程对一个数组进行插入排序也是同样道理,但和插入扑克牌有一点不同,不可能在两个相邻的存储单元之间再插入一个单元,因此要将插入点之后的数据依次往后移动一个单元。

python常见排序算法基础教程

设监视哨是我大一在书上有看过,大家忽视上图的监视哨。

算法实现:

import time


def insertion_sort(array):
 for i in range(1, len(array)): # 对第i个元素进行插入,i前面是已经排序好的元素
 position = i # 要插入数的下标
 current_val = array[position] # 把当前值存下来
 # 如果前一个数大于要插入数,则将前一个数往后移,比如5,8,12,7;要将7插入,先把7保存下来,比较12与7,将12往后移
 while position > 0 and current_val < array[position-1]:
 array[position] = array[position-1]
 position -= 1
 else: # 当position为0或前一个数比待插入还小时
 array[position] = current_val




if __name__ == "__main__":
 array = [92, 77, 67, 8, 6, 84, 55, 85, 43, 67]
 print(array)
 time_start = time.time()
 insertion_sort(array)
 time_end = time.time()
 print("time: %s" % (time_end-time_start))
 print(array)

输出:

[92, 77, 67, 8, 6, 84, 55, 85, 43, 67]
time: 0.0
[6, 8, 43, 55, 67, 67, 77, 84, 85, 92]

如果碰见一个和插入元素相等的,那么插入元素把想插入的元素放在相等元素的后面。所以,相等元素的前后顺序没有改变,从原无序序列出去的顺序就是排好序后的顺序,所以插入排序是稳定的。

直接插入排序复杂度:

时间复杂度: 最好情况O(n), 最坏情况O(n^2), 平均情况O(n^2)

空间复杂度: O(1)

稳定性: 稳定

个人感觉直接插入排序算法难度是选择/冒泡算法是两倍……

四、快速排序

python常见排序算法基础教程

快速排序示例:

python常见排序算法基础教程

python常见排序算法基础教程

算法实现:

def quick_sort(array, left, right):
 '''
 :param array:
 :param left: 列表的第一个索引
 :param right: 列表最后一个元素的索引
 :return:
 '''
 if left >= right:
 return

 low = left
 high = right
 key = array[low] # 第一个值,即基准元素

 while low < high: # 只要左右未遇见
 while low < high and array[high] > key: # 找到列表右边比key大的值 为止
 high -= 1
 # 此时直接 把key跟 比它大的array[high]进行交换
 array[low] = array[high]
 array[high] = key

 while low < high and array[low] <= key: # 找到key左边比key大的值,这里为何是<=而不是<呢?你要思考。。。
 low += 1
 # 找到了左边比k大的值 ,把array[high](此时应该刚存成了key) 跟这个比key大的array[low]进行调换
 array[high] = array[low]
 array[low] = key

 quick_sort(array, left, low-1) # 最后用同样的方式对分出来的左边的小组进行同上的做法
 quick_sort(array,low+1, right) # 用同样的方式对分出来的右边的小组进行同上的做法


if __name__ == '__main__':
 array = [8,4,1, 14, 6, 2, 3, 9,5, 13, 7,1, 8,10, 12]
 print("-------排序前-------")
 print(array)
 quick_sort(array, 0, len(array)-1)
 print("-------排序后-------")
 print(array)

输出:

-------排序前-------
[8, 4, 1, 14, 6, 2, 3, 9, 5, 13, 7, 1, 8, 10, 12]
-------排序后-------
[1, 1, 2, 3, 4, 5, 6, 7, 8, 8, 9, 10, 12, 13, 14]

22行那里如果不加=号,当排序64,77,64是会死循环,此时key=64, 最后的64与开始的64交换,开始的64与本最后的64交换…… 无穷无尽

直接插入排序复杂度:

时间复杂度: 最好情况O(nlogn), 最坏情况O(n^2), 平均情况O(nlogn)

下面空间复杂度是看别人博客的,我也不大懂了……改天再研究下。

最优的情况下空间复杂度为:O(logn);每一次都平分数组的情况

最差的情况下空间复杂度为:O( n );退化为冒泡排序的情况

稳定性:不稳定

快速排序效果:

python常见排序算法基础教程

参考:

Python常用算法学习基础教程

视觉直观感受若干常用排序算法

c++中八大排序算法

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持码农之家。

以上就是本次给大家分享的关于java的全部知识点内容总结,大家还可以在下方相关文章里找到相关文章进一步学习,感谢大家的阅读和支持。

Python 相关电子书
学习笔记
网友NO.966672

浅谈numpy数组的几种排序方式_python

这篇文章主要介绍了浅谈numpy数组的几种排序方式,涉及对numpy的简单介绍和创建数组的方式,具有一定借鉴价值,对numpy感兴趣的朋友可以参考下。 简单介绍 NumPy系统是Python的一种开源的数组计算扩展。这种工具可用来存储和处理大型矩阵,比Python自身的嵌套列表(nested list structure)结构要高效的多(该结构也可以用来表示矩阵(matrix))。 创建数组 创建1维数组: data = np.array([1,3,4,8]) 查看数组维度 data.shape 查看数组类型 data.dtype 通过索引获取或修改数组元素 data[1] 获取元素 data[1] = 'a' 修改元素 创建二维数组 data = np.array([[1,2,3],[4,5,6]]) 两个元素均为列表br2.data = np.arange(10) 与python的range一样,range返回列表,arange返回array类型的一个数组br3.data2 = data.reshape(2,5) 返回一个2*5的数组,他不是拷贝数组是引用,只是返回数组的不同视图,data改变data2也会改变……

网友NO.922203

python中字典按键或键值排序的实现代码

字典排序 在程序中使用字典进行数据信息统计时,由于字典是无序的所以打印字典时内容也是无序的。因此,为了使统计得到的结果更方便查看需要进行排序。Python中字典的排序分为按“键”排序和按“值”排序。 按“值”排序 按“值”排序就是根据字典的值进行排序,可以使用内置的sorted()函数。 sorted(iterable[, cmp[, key[, reverse]]]) iterable:是可迭代类型类型; cmp:用于比较的函数,比较什么由key决定,有默认值,迭代集合中的一项; key:用列表元素的某个属性和函数进行作为关键字,有默认值,迭代集合中的一项; reverse:排序规则. reverse = True 或者 reverse = False,有默认值,默认为升序排列(False)。 返回值:是一个经过排序的可迭代类型,与iterable一样。一般来说,cmp和key可以使用lambda表达式。 如果对字典进行排序,常用的形式如下: sorted(dict.ite……

网友NO.776841

python中排序操作和heapq模块的实例用法

本篇文章给大家带来的内容是关于python中的排序操作和heapq模块的介绍(代码示例),有一定的参考价值,有需要的朋友可以参考一下,希望对你有所帮助。 说到排序,很多人可能第一想到的就是sorted,但是你可能不知道python中其实还有还就中方法哟,并且好多种场景下效率都会比sorted高。那么接下来我就依次来介绍我所知道的排序操作。 sorted(iterable, *, key=None, reverse=False) list1=[1,6,4,3,9,5]list2=[12,a6,4,c34,b9,5]print(sorted(list1)) #[1, 3, 4, 5, 6, 9]print(sorted(list2)) #[12, 4, 5, a6, b9, c34]#总结上面两种排序:字符串排序根据元素首字符的ASCII比较进行排序,#数字类型按照大小排序,数字不能混合排序list3=[ {name:jim,age:23,price:500}, {name:mase,age:23,price:600}, {name:tom,age:25,price:2000}, {name:alice,age:22,price:300}, {name:rose,age:21,price:2400},]print(sorted(list3,key=lambda s:(s[age],s[price])))#[{name: rose, age……

网友NO.729096

Python编程对列表中字典元素进行排序的方法详解

本文实例讲述了Python编程对列表中字典元素进行排序的方法。分享给大家供大家参考,具体如下: 内容目录: 1. 问题起源 2. 对列表中的字典元素排序 3. 对json进行比较(忽略列表中字典的顺序) 一、问题起源 json对象a,b a = '{"ROAD": [{"id": 123}, {"name": "no1"}]}'b = '{"ROAD": [{"name": "no1"}, {"id": 123}]}' 特点:a,b对应的Python的对象中键对应的键值——列表中包含着相同的字典元素,但是唯一不同的是顺序不同。如果忽略顺序,如何判断两个json是否相等。因为字典本身是自己按键排序的,列表是按加入的顺序排序的,如果对列表中的字典元素进行排序就可以轻松地排序了。如果列表中是普通的元素(不是字典),通过list(set())组合可以读列表进行排序,而列表中如果是字典元素不能使用list(set())组合,看提示: a = [{'a':1, 'b':2}, {'c':3}] a[{'a': 1, 'b': 2}, {'c': 3}] b = set(a)……

<
1
>

Copyright 2018-2020 www.xz577.com 码农之家

版权投诉 / 书籍推广 / 赞助:520161757@qq.com