深入分析python 排序
排序是每个开发人员都需要掌握的技能。排序是对程序本身有一个全面的理解。不同的排序算法很好地展示了算法设计上如何强烈的影响程序的复杂度、运行速度和效率。今天的文章和谈谈大家都熟悉的各种排序使用 Python 如何实现，废话就不多说啦，开干！
选择排序
选择排序一般是将初始值设为初始值，再循环后面每个元素与第一个元素比较，最终筛选出一个最小或最大值，最后将有序的数值排在前面，每次选择当前序列的最小值，将其与当前序列的第一个元素交换位置，每迭代一次，当前序列长度减一。迭代结束，即可得到有序序列。 实现代码如下：
def select_s(data):
# 第一层循环：取出数组中的每个元素
for i in range(len(data)):
temp = i # 拿取一个元素用来比较
# 第二层循环：从第i后面的一个值开始循环，与data[i]进行比较
for j in range(i+1,len(data)):
if data[j] < data[temp]:
data[temp], data[j] = data[j], data[temp]
print(data)
调用运行结果：
if __name__ == '__main__': data = [14, 31, 14, 6, 18, 24, 2, 40] select_s(data)
输出结果：
[2, 6, 14, 14, 18, 24, 31, 40]
插入排序
插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为O(n^2)。是稳定的排序方法。
插入算法把要排序的数组分成两部分：第一部分包含了这个数组的所有元素，但将最后一个元素除外（让数组多一个空间才有插入的位置），而第二部分就只包含这一个元素（即待插入元素）。在第一部分排序完成后，再将这个最后元素插入到已排好序的第一部分中。
实现代码如下：
def insert_s(data):
# 第一层循环： 从第二个元素开始循环取出元素，取出的元素再与有序区元素进行比较
for i in range(1,len(data)):
temp = data[i]
j = i-1
while j>=0 and temp < data[j]:
data[j+1] = data[j]
j = j-1 # 在与前面一个元素进行比较，所以j 需要减1
# 当j = -1 就跳出循环，将temp值赋给第一个值，即data[0]
data[j+1] = temp
print(data)
调用运行结果：
if __name__ == '__main__': data = [12, 3, 13, 56, 10, 22, 2, 40] insert_s(data)
输出结果：
[2, 3, 10, 12, 13, 22, 40, 56]
冒泡排序
冒泡排序（顺序形式），从左向右，两两比较，如果左边元素大于右边，就交换两个元素的位置。
其中，每一轮排序，序列中最大的元素浮动到最右面。也就是说，每一轮排序，至少确保有一个元素在正确的位置。
这样接下来的循环，就不需要考虑已经排好序的元素了，每次内层循环次数都会减一。
其中，如果有一轮循环之后，次序并没有交换，这时我们就可以停止循环，得到我们想要的有序序列了。
def insert_s(data):
# 第一层循环： 从第二个元素开始循环取出元素，取出的元素再与有序区元素进行比较
for i in range(1,len(data)):
temp = data[i]
j = i-1
while j>=0 and temp < data[j]:
data[j+1] = data[j]
j = j-1 # 在与前面一个元素进行比较，所以j 需要减1
# 当j = -1 就跳出循环，将temp值赋给第一个值，即data[0]
data[j+1] = temp
print(data)
调用运行结果：
if __name__ == '__main__': data = [12, 3, 13, 56, 10, 22, 2, 40] insert_s(data)
输出结果：
[2, 3, 10, 12, 13, 22, 40, 56]
快速排序
首先要打乱序列顺序，以防算法陷入最坏时间复杂度。所以快速排序使用 “分而治之” 的方法。
对于一串序列，首先从中选取一个数，凡是小于这个数的值就被放在左边，凡是大于这个数的值就被放在右边。然后，继续对左右两摞进行快速排序。
直到进行快速排序的序列长度小于 2 （即序列中只有一个值或者空值）。
代码如下：
# 快速排序
def partition(data, left, right):
temp = data[left]
while left < right:
# 如果最右边的值大于中间值，则最右边值往后退一个位置，反之，就将值赋值给最左边位置
while left < right and data[right] >= temp:
right = right - 1
data[left] = data[right]
# 如果最左边的值小于中间值，则最左边值往前进一个位置，反之，就将值赋值给最右边位置
while left < right and data[left] <= temp:
left = left + 1
data[right] = data[left]
# 循环结束，即可定位到中间位置，将初始值，赋值到这个位置
data[left] = temp
return left
def quick_sort(data, left, right):
if left < right:
mid = partition(data, left, right)
quick_sort(data, left, mid)
quick_sort(data, mid + 1, right)
总结
今天的文章主要是使用 Python 实现各大排序程序，以及排序算法实现思路的梳理，自己学习的同时给大家整理思路！
示例代码Python 排序了解一下？
以上就是深入分析python 排序的详细内容，更多关于python 排序的资料请关注我们其它相关文章！
相关推荐
-
Python OrderedDict字典排序方法详解
很多人认为python中的字典是无序的,因为它是按照hash来存储的,但是python中有个模块collections(英文,收集.集合),里面自带了一个子类 OrderedDict,实现了对字典对象中元素的排序.请看下面的实例: import collections print "Regular dictionary" d={} d['a']='A' d['b']='B' d['c']='C' for k,v in d.items(): print k,v print "\
-
用python给csv里的数据排序的具体代码
1.使用argparse组件,获取命令行参数:使用re组件,获取需要查找的字符串所在行 2.使用pandas组件,对文件进行排序. 3.命令行执行数据获取及排序,写入文件: 以下是完整代码: #coding:utf-8 import re import argparse import pandas as pd parser = argparse.ArgumentParser(description='manual to this script') parser.add_argument('--i
-
Python要如何实现列表排序的几种方法
排序,是许多编程语言中经常出现的问题.同样的,在Python中,如何是实现排序呢?(以下排序都是基于列表来实现) 一.使用Python内置函数进行排序 Python中拥有内置函数实现排序,可以直接调用它们实现排序功能 Python 列表有一个内置的 list.sort() 方法可以直接修改列表.还有一个 sorted() 内置函数,它会从一个可迭代对象构建一个新的排序列表. 1.sort()函数: list.sort(cmp=None, key=None, reverse=False) 其中参数
-
python 实现多维数组(array)排序
关于多维数组如何复合排序 如数组: >>> import numpy as np >>> data = np.array([[2,2,5],[2,1,3],[1,2,3],[3,1,4]]) >>>> data array([[2, 2, 5], [2, 1, 3], [1, 2, 3], [3, 1, 4]]) 将数组先按照第一列升序,第二列升序,第三列升序的方式排序: >>> idex=np.lexsort([data[:,
-
Python中sorted()排序与字母大小写的问题
今天我在练习python时,对字典里的键用sorted排序时发现并没有按照预期排序 研究后发现字母大小写会影响排序 首先创建一个字典,键里面的首字母有大写有小写 favorite_digit = { 'john' : 4, 'Tom' : 5, 'Lisa' : 9, 'liu' : 5, 'alice' : 0, } for name in sorted(favorite_digit.keys()): print(name.title()) 运行后发现与预期不符合. Lisa Tom Alic
-
python对数组进行排序,并输出排序后对应的索引值方式
废话不多说,直接上代码吧! # -*- coding: cp936 -*- import numpy as np #一维数组排序 arr = [1, 3, 5, 2, 4, 6] arr = np.array(arr) print arr print np.sort(arr)#或print np.sort(arr,axis=None) print (np.argsort(arr)) # 正序输出索引,从小到大 print (np.argsort(-arr)) # 逆序输出索引,从大到小 输出结果
-
python 常见的排序算法实现汇总
排序分为两类,比较类排序和非比较类排序,比较类排序通过比较来决定元素间的相对次序,其时间复杂度不能突破O(nlogn):非比较类排序可以突破基于比较排序的时间下界,缺点就是一般只能用于整型相关的数据类型,需要辅助的额外空间. 要求能够手写时间复杂度位O(nlogn)的排序算法:快速排序.归并排序.堆排序 1.冒泡排序 思想:相邻的两个数字进行比较,大的向下沉,最后一个元素是最大的.列表右边先有序. 时间复杂度$O(n^2)$,原地排序,稳定的 def bubble_sort(li:list):
-
python通过对字典的排序,对json字段进行排序的实例
如下所示: dic = dict() dic['a'] = 1 dic['b'] = 2 dic['c'] = 3 print(dic.items()) import json jsons = json.dumps(dic) print(jsons) 结果: dic is: dict_items([('c', 3), ('b', 2), ('a', 1)]) jsons: {"c": 3, "b": 2, "a": 1} 通过使用collecio
-
Python sorted对list和dict排序
sorted语法 sorted(iterable, key=None, reverse=False) 参数说明: - iterable -- 可迭代对象. - key --主要是用来进行比较的元素,只有一个参数,具体的函数的参数就是取自于可迭代对象中,指定可迭代对象中的一个元素来进行排序. - reverse -- 排序规则,reverse = True 降序 , reverse = False 升序(默认). 返回: - 一个新list对象 sorted对字典dict排序 ①按键key排
-
深入分析python 排序
排序是每个开发人员都需要掌握的技能.排序是对程序本身有一个全面的理解.不同的排序算法很好地展示了算法设计上如何强烈的影响程序的复杂度.运行速度和效率.今天的文章和谈谈大家都熟悉的各种排序使用 Python 如何实现,废话就不多说啦,开干! 选择排序 选择排序一般是将初始值设为初始值,再循环后面每个元素与第一个元素比较,最终筛选出一个最小或最大值,最后将有序的数值排在前面,每次选择当前序列的最小值,将其与当前序列的第一个元素交换位置,每迭代一次,当前序列长度减一.迭代结束,即可得到有序序列. 实现
-
python排序方法实例分析
本文实例讲述了python排序方法.分享给大家供大家参考.具体如下: >>> def my_key1(x): ... return x % 10 ... >>> alist = [4, 5, 8, 1, 63, 8] >>> alist [4, 5, 8, 1, 63, 8] >>> alist.sort() # 默认升序排序 >>> alist [1, 4, 5, 8, 8, 63] >>> al
-
Python排序搜索基本算法之归并排序实例分析
本文实例讲述了Python排序搜索基本算法之归并排序.分享给大家供大家参考,具体如下: 归并排序最令人兴奋的特点是:不论输入是什么样的,它对N个元素的序列排序所用时间与NlogN成正比.代码如下: # coding:utf-8 def mergesort(seq): if len(seq)<=1: return seq mid=int(len(seq)/2) left=mergesort(seq[:mid]) right=mergesort(seq[mid:]) return merge(lef
-
Python排序搜索基本算法之堆排序实例详解
本文实例讲述了Python排序搜索基本算法之堆排序.分享给大家供大家参考,具体如下: 堆是一种完全二叉树,堆排序是一种树形选择排序,利用了大顶堆堆顶元素最大的特点,不断取出最大元素,并调整使剩下的元素还是大顶堆,依次取出最大元素就是排好序的列表.举例如下,把序列[26,5,77,1,61,11,59,15,48,19]排序,如下: 基于堆的优先队列算法代码如下: def fixUp(a): #在堆尾加入新元素,fixUp恢复堆的条件 k=len(a)-1 while k>1 and a[k//2
-
Python排序搜索基本算法之插入排序实例分析
本文实例讲述了Python排序搜索基本算法之插入排序.分享给大家供大家参考,具体如下: 插入排序生活中非常常见,打扑克的时候人的本能就在用插入排序:把抽到的一张插入到手上牌的正确位置上.有两种插入排序方法,一种基于比较,另一种基于交换.代码如下: 1.基于比较的插入排序: # coding:utf-8 def insertionSort(seq): length=len(seq) for i in range(1,length): tmp=seq[i] for j in range(i,0,-1
-
Python排序搜索基本算法之选择排序实例分析
本文实例讲述了Python排序搜索基本算法之选择排序.分享给大家供大家参考,具体如下: 选择排序就是第n次把序列中最小的元素排在第n的位置上,一旦排好就是该元素的绝对位置.代码如下: # coding:utf-8 def selectionSort(seq): length=len(seq) for i in range(length): mini=min(seq[i:]) if seq[i]>mini: j=seq.index(mini,i) seq[i],seq[j]=seq[j],seq[
-
Python排序搜索基本算法之冒泡排序实例分析
本文实例讲述了Python排序搜索基本算法之冒泡排序.分享给大家供大家参考,具体如下: 冒泡排序和选择排序类似,也是第n次把最小的元素排在第n的位置上,也是该元素的绝对位置,只是冒泡排序的过程中,其他的元素也逐渐向自己最终位置逼近.代码如下: def bubbleSort(seq): length=len(seq) for i in range(length): for j in range(length-1,i,-1): if seq[j-1]>seq[j]: seq[j-1],seq[j]=
-
Python排序搜索基本算法之希尔排序实例分析
本文实例讲述了Python排序搜索基本算法之希尔排序.分享给大家供大家参考,具体如下: 希尔排序是插入排序的扩展,通过允许非相邻的元素进行交换来提高执行效率.希尔排序最关键的是选择步长,本程序选用Knuth在1969年提出的步长序列:1 4 13 40 121 364 1093 3280 ...后一个元素是前一个元素*3+1,非常方便选取,而且效率还不错.代码如下: #-*- coding: UTF-8 -*- def shellSort(seq): length=len(seq) inc=0
-
Python排序算法之选择排序定义与用法示例
本文实例讲述了Python排序算法之选择排序定义与用法.分享给大家供大家参考,具体如下: 选择排序 选择排序比较好理解,好像是在一堆大小不一的球中进行选择(以从小到大,先选最小球为例): 1. 选择一个基准球 2. 将基准球和余下的球进行一一比较,如果比基准球小,则进行交换 3. 第一轮过后获得最小的球 4. 在挑一个基准球,执行相同的动作得到次小的球 5. 继续执行4,直到排序好 时间复杂度:O(n^2). 需要进行的比较次数为第一轮 n-1,n-2....1, 总的比较次数为 n*(n-1
-
Python排序函数的使用方法详解
Python排序函数完美体现了Python语言的简洁性,对于List对象,我们可以直接调用sort()函数(这里称为"方法"更合适)来进行排序,而对于其他可迭代对象(如set,dict),我们可以使用更灵活的sorted()函数. 一.List的sort()函数 Python源码builtins.py文件对sort()函数的定义如下 def sort(self, key=None, reverse=False): """ L.sort(key=None,