排序,是许多编程语言中经常出现的问题。同样的,在Python中,如何是实现排序呢?(以下排序都是基于列表来实现) 一、使用Python内置函数进行排序Python中拥有内置函数实现排序,可以直接调用它们实现排序功能 Python 列表有一个内置的 1.sort()函数:list.sort(cmp=None, key=None, reverse=False) 其中参数的含义是:
默认输入列表就可以排序,例如: list=[1,2,4,5,3] 2.sorted()函数:sorted(iterable, cmp=None, key=None, reverse=False) 其中:
同样的,使用sorted()函数可以对列表进行排序,例如: list=[1,2,4,5,3]
print(sorted(list))
>>>[1,2,3,4,5]
sort()和sorted()虽然相似,都可以实现排序功能,但是它们有很大的不同: sort ()与sorted()区别: sort() 是应用在 list 上的方法,sorted() 可以对所有可迭代的对象进行排序操作。 list 的 sort() 方法返回的是对已经存在的列表进行操作,无返回值,而内建函数 sorted() 方法返回的是一个新的 list,而不是在原来的基础上进行的操作。 二、使用常用的排序算法进行排序同其他高级函数一样,Python也可以使用算法,利用一般语句进行排序。 1.冒泡排序冒泡排序是最常见到的排序算法,也是很基础的一种排序算法。它的实现思想是:相邻的两个元素进行比较,然后把较大的元素放到后面(正向排序),在一轮比较完后最大的元素就放在了最后一个位置,像鱼儿在水中吐的气泡在上升的过程中不断变大, def bubble_sort(list): count = len(list) for i in range(count): for j in range(i + 1, count): if list[i] > list[j]: list[i], list[j] = list[j], list[i] return list 2.选择排序选择排序的思路是:第一轮的时候,所有的元素都和第一个元素进行比较,如果比第一个元素大,就和第一个元素进行交换,在这轮比较完后,就找到了最小的元素;第二轮的时候所有的元素都和第二个元素进行比较找出第二个位置的元素,以此类推。 def selection_sort(list): length = len(list) for i in range(length - 1, 0, -1): for j in range(i): if list[j] > list[i]: list[j], list[i] = list[i], list[j] return list 3.插入排序插入排序的思想是将一个数据插入到已经排好序的有序数据中,从而得到一个新的、个数加一的有序数据,算法适用于少量数据的排序,时间复杂度为O(n^2)。 是稳定的排序方法。插入算法把要排序的数组分成两部分:第一部分包含了这个数组的所有元素,但将最后一个元素除外(让数组多一个空间才有插入的位置), 而第二部分就只包含这一个元素(即待插入元素)。在第一部分排序完成后,再将这个最后元素插入到已排好序的第一部分中 def insert_sort(list): count = len(list) for i in range(1, count): key = list[i] j = i - 1 while j >= 0: if list[j] > key: list[j + 1] = list[j] list[j] = key j -= 1 return list 4.快速排序快速排序的思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小, 然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。 def quick_sort(list, left, right): if left >= right: return list key = lists[left] low = left high = right while left < right: while left < right and list[right] >= key: right -= 1 lists[left] = lists[right] while left < right and list[left] <= key: left += 1 list[right] = list[left] list[right] = key quick_sort(list, low, left - 1) quick_sort(list, left + 1, high) return list lst1 = raw_input().split() #调用函数 lst = [int(i) for i in lst1] #lst = input() quick_sort(lst,0,len(lst)-1) for i in range(len(lst)): print lst[i], 5.希尔排序希尔排序是插入排序的一种。也称缩小增量排序,是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。 该方法因DL.Shell于1959年提出而得名。 希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少, 每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止。 |
|