排序算法

插入排序

1
2
3
4
5
6
7
8

def insertion_sort(array):
    for i in range(1,len(array)):
        key=array[i]
        j=i-1
        while j>=0 and array[j]>key:
            array[j+1]=array[j]
            j-=1
        array[j+1]=key

插入排序只要记得就想扑克牌一样就好了，没什么大的问题。这里用了比较经典的思路，就是“移动”，而不是相邻间两两交换。

归并排序

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

def __merge(arr,low,mid,high):
    buff=arr[:]
    i=low
    j=mid+1
    for k in range(low,high+1):
        if i>mid:
            arr[k]=buff[j]
            j+=1
        elif j>high:
            arr[k]=buff[i]
            i+=1
        elif buff[i]<buff[j]:
            arr[k]=buff[i]
            i+=1
        elif buff[i]>=buff[j]:
            arr[k]=buff[j]
            j+=1
        else:
            print('神一般的错误')
            sys.exit(0)
def merge_sort(array,low,high):
    if low<high:
        mid=(low+high)//2
        merge_sort(array,low,mid)
        merge_sort(array,mid+1,high)
        __merge(array,low,mid,high)

作为分治算法的一种应用，主要大头在于合并而不在于分（区别于另一个分治算法快排）。合并时需要额外数组空间，可惜不是原地排序。

快速排序

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

def __partition(array,start,end):
    x=array[end]#末尾元素做主元
    i=start-1
    for j in range(start,end):
        if array[j]<x:
            i+=1
            array[i],array[j]=array[j],array[i]
    array[i+1],array[end]=array[end],array[i+1]
    return i+1

def _partition(a,low,high):
    #供quick_sort调用
    i=low+1
    j=high
    v=a[low]
    while True:
        while a[i]<v:
            i+=1
            if i>high:
                break
        while a[j]>v:
            j-=1
            if j<low:
                break
        if i>=j:
            break
        a[i],a[j]=a[j],a[i]
    a[low],a[j]=a[j],a[low]
    return j


def quick_sort(array,start,end):
    if start<end:
        mid=__partition(array,start,end)
        print(array)
        quick_sort(array,start,mid-1)
        quick_sort(array,mid+1,end)

应用最多的了，注意这里用了两种分法，一个是两边到中间，一个是从左到右（算法导论的新颖啊）。

堆排序&&优先级队列

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

class Priority_Queue(object):
    '''
        length从1到最后一个元素，0空出来没用
    '''
    def __init__(self):
        self.pq = [0] * 101
        self.length = 0  # 优先队列
        self.real_len = 0  # 堆排序
    def __init__(self, a):
        if isinstance(a, list):  # isinstance和java中instanceof一样，用type就对子类无效了
            self.pq = a[:]
            self.real_len = self.length = len(a)
            self.pq[self.length:] = [0]
            self.pq[1:] = self.pq[:]  # 空出第一个元素
            # for index,value in enumerate(self.pq):
            #     self.__swim(index)
            for i in range(1,self.length+1):
                self.__swim(i)
    def size(self):
        return self.length
    def isempty(self):
        return self.length == 0
    def insert(self, v):
        self.length += 1
        self.real_len += 1
        if self.length > 100:
            self.pq.extend([0] * 100)
        self.pq[self.length] = v
        self.__swim(self.length)  # 每当加入一个元素，都应该从它开始上浮到它该待的地方
    def __swim(self,k):
        ##大顶堆，大的上浮
        while k>1 and self.pq[k//2]<self.pq[k]:
            self.pq[k],self.pq[k//2]=self.pq[k//2],self.pq[k]
            k=k//2
    def __sink(self,k):
        #j是儿子，k是爹
        j=2*k
        while j<=self.length :
            #让j指向较大的儿子
            if j< self.length and self.pq[j]<self.pq[j+1]:
            # j<self.length一定要有，防止2*k是最后一个元素了
                j+=1
            #如果爹不比儿子们小，那就下沉结束了
            if not self.pq[k]<self.pq[j]:
                break
            self.pq[k],self.pq[j]=self.pq[j],self.pq[k]
            k=j
            j=2*k
    def delmax(self):
        #最大的放最后面了
        self.pq[1],self.pq[self.length]=self.pq[self.length],self.pq[1]
        self.length -= 1
        self.__sink(1)
        return self.pq[self.length+1]

    def show(self):
        print(self.pq[1:self.real_len+1])
        print('length==',self.length)
        print('real_length=',self.real_len)
        print('-'*100)
    def sort(self):
        for i in range(self.length,1,-1):
            self.delmax()

上浮和下沉中的k都是对应下标，插入时由于从末尾插入需要k为length，需要上浮。而删除最大元素后，下标1需要下沉。

计数排序

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

def count_sort(array):
    buff=array[:]
    c=[0]*(max(array)+1)
    #c数组对应下标记录等于该下标的元素个数
    for x in array:
        c[x]=c[x]+1
    #现在，c数组对应下标记录小于等于该下标的元素个数
    for i in range(1,len(c)):
        c[i]=c[i-1]+c[i]
    for x in array:
        buff[c[x]-1]=x
        c[x]=c[x]-1
    return buff

新奇的思路，需要用数组记录每个元素的“位置”。