用 python 实现各种排序算法(2)

当前位置:

首页 > Python基础教程 >

用 python 实现各种排序算法(2)

稳定，时间复杂度 O(nlog n)

插入排序

代码如下：

						#!/usr/bin/python  

						import sys  

						def insert_sort(a):  

						    ''''' 插入排序 

						    有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数， 

						    但要求插入后此数据序列仍然有序。刚开始 一个元素显然有序，然后插入一 

						    个元素到适当位置，然后再插入第三个元素，依次类推 

						    '''  

						    a_len = len(a)  

						    if a_len = 0 and a[j] > key:  

						            a[j+1] = a[j]  

						            j-=1  

						        a[j+1] = key  

						    return a  

						if __name__ == '__main__':  

						    nums = [10,8,4,-1,2,6,7,3]  

						    print 'nums is:', nums  

						    insert_sort(nums)  

						    print 'insert sort:', nums

稳定，时间复杂度 O(n^2)

交换两个元素的值python中你可以这么写：a, b = b, a，其实这是因为赋值符号的左右两边都是元组

（这里需要强调的是，在python中，元组其实是由逗号“,”来界定的，而不是括号）。

选择排序

选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到

排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所

有元素均排序完毕。

						import sys  

						def select_sort(a):  

						    ''''' 选择排序  

						    每一趟从待排序的数据元素中选出最小（或最大）的一个元素， 

						    顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。 

						    选择排序是不稳定的排序方法。 

						    '''  

						    a_len=len(a)  

						    for i in range(a_len):#在0-n-1上依次选择相应大小的元素   

						        min_index = i#记录最小元素的下标   

						        for j in range(i+1, a_len):#查找最小值  

						            if(a[j]<a[min_index]):  

						                min_index=j  

						        if min_index != i:#找到最小元素进行交换  

						            a[i],a[min_index] = a[min_index],a[i]  

						if __name__ == '__main__':  

						    A = [10, -3, 5, 7, 1, 3, 7]    

						    print 'Before sort:',A    

						    select_sort(A)    

						    print 'After sort:',A

栏目列表