排序算法的python实现

本文用python实现了插入排序、希尔排序、冒泡排序、快速排序、直接选择排序、堆排序、归并排序、基数排序。

1、插入排序

插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而的到一个新的、个数加一的有序数据，算法适用于少量的数据的排序，时间复杂度为O(n^2)，是稳定的排序方法。插入算法把要排序的数组分成两部分：第一部分包含了这个数组的所有元素，但将最后一个元素除外（让数组多一个空间才有插入的位置）而第二部分就只包含这一元素（即待插入元素）。在第一部分排序完成后，再将这个最后的元素插入到已排好序的第一部分中。

 1 def insert_sort(lists):
 2 #插入排序
 3 count=len(lists)
 4 for i in range(1,count):
 5 key=lists[i]
 6 j=i-1
 7 while j>=0:
 8 if list[j]>key:
 9 lists[j+1]=list[j]
10 lists[j]=key
11 j-=1
12 return lists

2、希尔排序

希尔排序是插入排序的一种。也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量的逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

3、冒泡排序

它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复的进行直到没有再需要交换，也就是说该数列已经排序完成。

1 def bubble_sort(lists):
2 #冒泡排序
3 count=len(lists)
4 for i in range(0,count):
5 for j in range(i+1,count):
6 if lists[i]>lists[j]:
7 lists[i],lists[j]=lists[j],lists[i]
8 return lists

4、快速排序

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，依次达到整个数据编程有序序列。

5、直接选择排序

基本思想：第一趟，在待排序记录r1~rn中选出最小的记录，将它与r1交换，第二趟，在待排序记录r2~r[n]中选出最小的记录，将它与r2交换；依次类推使有序序列不断增长直到全部排序完毕。

def select_sort(lists):
#选择排序
count =len(lists)
for i in range(0,count):
min=i
for j in range(i+1,count):
if lists[min]>lists[j]:
min=j
lists[min],lists[i]=lists[i],lists[min]
return lists