几种常用排序算法的python实现

1：快速排序

思想：

任意选取一个数据（通常选用数组的第一个数）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序。

一趟快速排序的算法是：

1）设置两个变量i、j，排序开始的时候：i=0，j=N-1；

2）以第一个数组元素作为关键数据，赋值给key，即key=A[0]；

3）从j开始向前搜索，即由后开始向前搜索(j--)，找到第一个小于key的值A[j]，将A[j]赋给A[i]；

4）从i开始向后搜索，即由前开始向后搜索(i++)，找到第一个大于key的A[i]，将A[i]赋给A[j]；

5）重复第3、4步，直到i=j； (3,4步中，没找到符合条件的值，即3中A[j]不小于key,4中A[i]不大于key的时候改变j、i的值，使得j=j-1，i=i+1，直至找到为止。找到符合条件的值，进行交换的时候i， j指针位置不变。另外，i==j这一过程一定正好是i+或j-完成的时候，此时令循环结束）。

注意：快速排序不会直接得到最终结果，只会把比k大和比k小的数分到k的两边。（你可以想象一下i和j是两个机器人，数据就是大小不一的石头，先取走i前面的石头留出回旋的空间，然后他们轮流分别挑选比k大和比k小的石头扔给对面，最后在他们中间把取走的那块石头放回去，于是比这块石头大的全扔给了j那一边，小的全扔给了i那一边。只是这次运气好，扔完一次刚好排整齐。）为了得到最后结果，需要再次对下标2两边的数组分别执行此步骤，然后再分解数组，直到数组不能再分解为止（只有一个数据），才能得到正确结果。

python实现代码：

#*-* coding: utf-8 *-*
import random
# produce random numbers to be sorted
s = []
for i in range(0,100):
    s.append(random.randint(1,100))
    print(s[i]),
#
print("\nbegin")
def partition(inlist,start,end):
    i = start
    j = end
    k = inlist[i]
    while i<j:
        while i<j and inlist[j]>=k:
            j = j-1
        inlist[i]=inlist[j]
        while i<j and inlist[i]<=k:
            i = i+1
        inlist[j]=inlist[i]
    inlist[i]=k
    return i

def quickSort(inlist,start,end):
    if start>=end:
        return
    middle = partition(inlist,start,end)
    quickSort(inlist,start,middle-1)
    quickSort(inlist,middle+1,end)

quickSort(s,0,len(s)-1)
for i in s:
    print "%d " %i,
print("done")

2：直接插入排序

思想：

每次从无序表中取出第一个元素，把它插入到有序表的合适位置，使有序表仍然有序。

第一趟比较前两个数，然后把第二个数按大小插入到有序表中； 第二趟把第三个数据与前两个数从前向后扫描，把第三个数按大小插入到有序表中；依次进行下去，进行了(n-1)趟扫描以后就完成了整个排序过程。

python 代码：

#*-* coding: utf-8 *-*
import random
# produce random numbers to be sorted
s = []
for i in range(0,100):
    s.append(random.randint(1,100))
    print(s[i]),
#
print("\nbegin")

j=0
for i in range(1,len(s)):
    if s[i]<s[i-1]:
        temp = s[i]
        j=i-1
        while j>=0 and s[j]>temp:
            s[j+1]=s[j]
            s[j]=temp
            j=j-1
for i in s:
    print "%d " %i,
print("\ndone")

3：冒泡排序

思想：

1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
3. 针对所有的元素重复以上的步骤，除了最后一个。
4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

python 代码：

#*-* coding: utf-8 *-*
import random
# produce random numbers to be sorted
s = []
for i in range(0,100):
    s.append(random.randint(1,100))
    print(s[i]),
#
print("\nbegin")

i = len(s)-1
while i>0:
    j=0
    for j in range(0,i):
        if s[j+1]<s[j]:
            temp = s[j]
            s[j]=s[j+1]
            s[j+1]=temp
            j = j+1
    i = i-1
for i in s:
    print "%d " %i,
print("\ndone")

4：桶排序

思想：

假定：输入是由一个随机过程产生的[0, 1)区间上均匀分布的实数。将区间[0, 1)划分为n个大小相等的子区间（桶），每桶大小1/n：[0, 1/n)， [1/n, 2/n)， [2/n, 3/n)，…，[k/n, (k+1)/n )，…将n个输入元素分配到这些桶中，对桶中元素进行排序，然后依次连接桶输入0 ≤A[1..n] <1辅助数组B[0..n-1]是一指针数组，指向桶（链表）。

太难懂了，举个简单的例子：

一年的全国高考考生人数为500 万，分数使用标准分，最低100 ，最高900 ，没有小数，你把这500 万元素的数组排个序。

我们发现，这些数据都有特殊的条件： 100=<score<=900。那么我们就可以考虑桶排序这样一个“投机取巧”的办法、让其在毫秒级别就完成500万排序。

方法：创建801(900-100)个桶。将每个考生的分数丢进f(score)=score-100的桶中。这个过程从头到尾遍历一遍数据只需要500W次。然后根据桶号大小依次将桶中数值输出，即可以得到一个有序的序列。而且可以很容易的得到100分有***人，501分有***人。

python代码：

#*-* coding: utf-8 *-*
import random
# produce random numbers to be sorted
#10000 numbers,range in (0,100)
s = []
for i in range(0,10000):
    s.append(random.randint(0,100))
    #print(s[i]),
#
print("\nbegin")
r = {}
for i in range(0,101):
    r[i]=[]
for i in s:
    r[i].append(i)
f = file("r.txt","w")
for i in range(0,101):
    for j in r[i]:
        f.write(str(j)+',')
print("\ndone")

5：归并排序

思想：

归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个有序的子序列，再把有序的子序列合并为整体有序序列。

python代码：

#*-* coding: utf-8 *-*
import random
# produce random numbers to be sorted
s = []
for i in range(0,100):
    s.append(random.randint(1,100))
    print(s[i]),print("\nbegin")

def spli(inlist):
    if len(inlist)<=1:
        return inlist
    num = len(inlist)/2
    left = spli(inlist[0:num])
    right = spli(inlist[num:])
    return sor(left,right)
def sor(left,right):
    #print(left)
    #print(right)
    l = 0
    r = 0
    result =[]
    while l<len(left) and r <len(right):
        if left[l]<right[r]:
            result.append(left[l])
            l =l+1
        else:
            result.append(right[r])
            r = r+1
    result = result+right[r:]
    result = result+left[l:]
    return result
s=spli(s)
for i in s:
    print "%d " %i,
print("\ndone")

6：堆排序

思想：

1.什么是堆？

堆实际上是一棵完全二叉树，其任何一非叶节点满足性质：

Key[i]<=key[2i+1]&&Key[i]<=key[2i+2]或者Key[i]>=Key[2i+1]&&key>=key[2i+2]

即任何一非叶节点的关键字不大于或者不小于其左右孩子节点的关键字。

堆分为大顶堆和小顶堆，满足Key[i]>=Key[2i+1]&&key>=key[2i+2]称为大顶堆，满足 Key[i]<=key[2i+1]&&Key[i]<=key[2i+2]称为小顶堆。由上述性质可知大顶堆的堆顶的关键字肯定是所有关键字中最大的，小顶堆的堆顶的关键字是所有关键字中最小的。

2.堆排序的思想

利用大顶堆(小顶堆)堆顶记录的是最大关键字(最小关键字)这一特性，使得每次从无序中选择最大记录(最小记录)变得简单。

其基本思想为(大顶堆)：

1)将初始待排序关键字序列(R1,R2....Rn)构建成大顶堆，此堆为初始的无序区；

2)将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,......Rn-1)和新的有序区(Rn),且满足R[1,2...n-1]<=R[n];

3)由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,......Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2....Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。

操作过程如下：

1)初始化堆：将R[1..n]构造为堆；

2)将当前无序区的堆顶元素R[1]同该区间的最后一个记录交换，然后将新的无序区调整为新的堆。

python 代码：

#*-* coding: utf-8 *-*
import random
# produce random numbers to be sorted
s = []
count=0
for i in range(0,100):
    s.append(random.randint(1,100))
    print(s[i]),
#
print("\nbegin")
def heap_sort(inlist):
    for start in range((len(inlist)-2)/2,-1,-1):#1：初始化堆：从最底层开始建树，并且保证是堆
        sift_down(inlist,start,len(inlist)-1)
    for end in range(len(inlist)-1,0,-1):#2：将堆顶元素与最后一个元素交换，调整
        inlist[0],inlist[end]=inlist[end],inlist[0]
        sift_down(inlist,0,end-1)
    return inlist

def sift_down(inlist,start,end):
    """调整算法：从父节点、左孩子节点、右孩子节点三者中选择最大者跟父节点进行交换
        (交换之后可能造成被交换的孩子节点不满足堆的性质，
        因此每次交换之后要重新对被交换的孩子节点进行调整)"""
    root = start
    while True:
        global count
        count=count+1
        child = 2*root +1#左节点
        if child>end:
            break
        if child+1<=end and inlist[child]<inlist[child+1]:#左节点比右节点小
            child = child+1#保证child对应的是左右节点中最大的
        if inlist[root]<inlist[child]:#如果root不是最大，交换
            inlist[root],inlist[child]=inlist[child],inlist[root]
            root=child
        else:
            break
heap_sort(s)
for i in s:
    print (i),
print("\ndone")
print(count)

6种算法比较次数的比较

随机生成10000的数据

	快速排序	直接插入排序	冒泡排序	桶排序	归并排序	堆排序
比较次数	512689	24795124	24934964	10000	120275	128265
效率	NlogN	N*N	N*N	N	NlogN	NlogN

很容易可以看出：

1：桶排序是最快的，但使用范围有限，排序的标准和数据的属性是一致的

2：快速排序、归并排序和堆排序都是NlogN的，但具体还是差别的，随机数据来看，比较次数：归并《堆《快速

有序序列的影响：

快速排序：有序》》》》（远大于）无序

直接插入：有序《无序

冒泡：有序《无序

桶排序：无差别

归并：有序《无序

堆排序：有序》无序