Python

以后就玩Python了。交流QQ群:250329766

算法排序之Python实现

排序是最经典的问题,基本上玩算法入门就是排序。 python本身有sorted函数。不过下面我们自己实现一下。


算法排序之Python实现

前言

排序是最经典的问题,基本上玩算法入门就是排序。
python本身有sorted函数。不过下面我们自己实现一下。
以下数据均是在我的同一台macbook上测试的。从结果也可以看出算法的重要性。

排序按模型分类有:

  1. 每次比较只有2个元素。包括插入排序,快速排序,堆排序,归并排序,冒泡排序。他们最好的效率只能到O(nlgn).可以通过画决策树证明。 一共有n!个节点。高度h的数最多有\(2^h\)个节点。所以有\(2^h \geq n!\)。通过斯特林公式\(n!=\sqrt{2πn}(\frac{n}{e})^n(1+\Theta(\frac{1}{n}))\) 可以得证。
  2. 对数据做些操作。譬如计数排序。

1.插入排序

这个算法和打牌很像,玩过牌的应该能很快理解。不多解释,看python的简单实现。
其最坏情况是\( \Theta(n^2) \)

#升序
def insert_sort(literal):
    if not literal or len(literal) == 1:
        return literal

    sorted = literal[:1]

    for i in range(1, len(literal)):
        v = literal[i]
        sorted.append(0)
        for j in range(i-1, -1, -1):
            if v < sorted[j]:
                sorted[j+1] = sorted[j]
            else:
                sorted[j+1] = v
                break

    return sorted

测试了一万条数据:

python insert_sort.py 6.66s user 0.45s system 98% cpu 7.192 total

2. 选择排序

选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完。

def select_sort(data):
    def swap(i, j):
        temp = data[i]
        data[i] = data[j]
        data[j] = temp

    for i in range(len(data)):
        min = data[i]
        index = i
        for j in range(i, len(data)):
            if data[j] < min:
                min = data[j]
                index = j
        swap(i, index)
    return data

3. 归并排序

归并排序描述起来好简单。就是把规模分成两组,一组都小于某个数n, 另一组都大于等于n。于是规模为n的问题,变成了2个n/2规模的问题。一次次这样划分下去,直到只剩下一个元素,一个元素当然是排好充的,然后再两两合并,直到得到原始问题的解。

其最坏情况是\( \Theta(nlgn) \)

这个思想是分治法

下面是python的实现:

#升序
def merge_sort(literal):

    def divide(literal):
        end = int(len(literal)/2)
        return (literal[:end], literal[end:])

    def conquer(literal):
        return merge_sort(literal)

    def merge(literal1, literal2):
        ret = []
        len1 = len(literal1)
        len2 = len(literal2)
        i1 = 0
        i2 = 0
        while len1 or len2:
            if not len1 and len2:
                ret.extend(literal2[i2:])
                return ret
            if not len2 and len1:
                ret.extend(literal1[i1:])
                return ret

            v1 = literal1[i1]
            v2 = literal2[i2]
            if v1 <= v2:
                ret.append(v1)
                len1 -= 1
                i1 += 1
            else:
                ret.append(v2)
                len2 -= 1
                i2 += 1
        return ret

    if not literal or len(literal) == 1:
        return literal

    literal1, literal2 = divide(literal)
    literal1 = conquer(literal1)
    literal2 = conquer(literal2)
    return  merge(literal1, literal2)

测试了一万条数据:

python merge_sort.py 0.22s user 0.02s system 84% cpu 0.283 total

之所以divide写的不那么好看,是为了一定要把问题分解。否则遇到 [1, 1 ,1]这样的数据就悲剧了。

4. 冒泡排序

它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。
这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端,故名。

#!/usr/bin/env python
import sys
import random
def bubble_sort(data):
    def swap(i, j):
        temp = data[i]
        data[i] = data[j]
        data[j] = temp

    exchanged = False
    for i in range(len(data)):
        for j in range(len(data)-1, i, -1):
            if data[j] < data[j-1]:
                swap(j, j-1)
                exchanged = True
        if not exchanged:
            return data
    return data

5. 堆排序

堆排序(Heapsort)是指利用堆积树(堆)这种数据结构所设计的一种排序算法,它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。堆分为大根堆和小根堆,是完全二叉树。大根堆的要求是每个节点的值都不大于其父节点的值,即A[PARENT[i]] >= A[i]。在数组的非降序排序中,需要使用的就是大根堆,因为根据大根堆的要求可知,最大的值一定在堆顶。

时间效率是\(O(n\lg{n})\),但实践中不如快速排序。不过用来实现优先级队列非常好。

#!/usr/bin/env python
import sys
import random


def heap_sort(data):
    datalength = len(data)
    data.insert(0, 0)

    def parent_index(i):
        return i >> 1

    def left_index(i):
        return i << 1

    def right_index(i):
        return left_index(i)+1

    def max_heapfy(heap_size, i):
        left = left_index(i)
        right = right_index(i)
        max = data[i]
        key = i
        if left <= heap_size and data[left] > max:
            max = data[left]
            key  = left

        if right <= heap_size and data[right] > max:
            max = data[right]
            key = right
        if key != i:
            swap(i, key)
            max_heapfy(heap_size, key)


    def build_heap():
        for i in range(int(datalength/2), 0, -1):
            max_heapfy(datalength, i)


    def swap(i, j):
        temp = data[i]
        data[i] = data[j]
        data[j] = temp

    build_heap()
    for i in range(datalength, 0, -1):
        swap(i, 1)
        max_heapfy(i-1, 1)


    return data[1:]

算法描述里索引是从1开始的,我这里取了个巧。补了个无用的0,来达到索引从1开始的目的。

6. 快速排序

快速排序和归并排序差不多。区别是归并排序只是把一个规模为n的问题划分成2个规模为n/2的子问题。
而快速排序划分的两个子问题,本身是有序的。即子问题A中的数都要小于等于子问题B中的数,这样在合并问题时更简单。

由于python的特性。做切片操作其实是做的复制工作。
我这里会提供二个快速排序的实现。供参考。

实现1

def quick_sort(literal):

    def divide(literal):
        v1 = literal[0]
        v2 = literal[1]
        v = max(v1, v2)
        literal1 = []
        literal2 = []
        if v1 == v2:
            literal1.append(v1)
            literal2.append(v2)
            for i in literal[2:]:
                if i < v:
                    literal1.append(i)
                else:
                    literal2.append(i)
        else:
            for i in literal:
                if i < v:
                    literal1.append(i)
                else:
                    literal2.append(i)

        return (literal1, literal2)

    def conquer(literal):
        return quick_sort(literal)

    def merge(literal1, literal2):
        ret = []
        ret.extend(literal1)
        ret.extend(literal2)
        return ret

    if not literal or len(literal) == 1:
        return literal

    literal1, literal2 = divide(literal)
    literal1 = conquer(literal1)
    literal2 = conquer(literal2)
    return  merge(literal1, literal2)

实现二的改进是原地排序

这种方式少了copy的代价,占用的空间更少,少了合并的步骤,效率也会更高。
我有个问题没有想清楚,这个程序和上面的程序差不多,都是递归实现,但是上面的程序可以排序100万个数都没问题,这个程序排序到2万个数就报堆栈溢出了。暂时放个问号????

#升序, 原地排序
def quick_sort(literal, start, end):
    def swap(i, j):
        temp = literal[i]
        literal[i] = literal[j]
        literal[j] = temp

    def divide(start, end):
        i = start
        key = literal[start]

        for j in range(start+1, end):
            if literal[j] <= key:
                swap(j,i+1)
                i += 1
        swap(i, start)
        return i+1


    if not literal or len(literal) <= 1:
        return
    if (end-start) <= 1:
        return
    index = divide(start, end)
    quick_sort(literal, start, index)
    quick_sort(literal, index, end)
    return literal

7. 计数排序

这个有个前提条件。必须是整数范围,同时最大的数不能太大。因为效率是O(n+k), 所以k不能太大。
远远小于n时,效率非常高,为线性排序。

参考实现:

def count_sort(alist, k):
    '''
    要求元素都比较小。时间效率是O(k+n),k为最大值。
    '''
    countList = [0 for _ in range(k+1)]
    for v in alist:
        countList[v] += 1
    retList = [0 for _ in range(len(countList))]
    for i, v in enumerate(countList):
        retList.extend([i for _ in range(v)])
    return retList

8. 基数排序

基数排序要用到计数排序。先对最后一位排序,再对前一位排序,直到排序完成。
同样要求是整数。好的是要求的数字大小范围没有计数排序那么小。

理论上这是最佳的排序算法,但是在实践中,最优秀的是快速排序
其时间复杂度为\(O(n\log_rm)\),其中r为所采取的基数,而m为堆数,在某些时候,基数排序法的效率高于其它的稳定性排序法。

上面实现的计数排序是偷懒的做法。因为是新生成的元素,而这里只是对某位排序,需要保留原数字,故要实现完整版的计数排序。

# -*- coding:utf-8 -*-
#!/usr/bin/env python
import sys
import random

def radix_sort(data, length):
    '''
    这个是简单版本,只实现了十进制的。
    '''
    def count_sort(alist, p):
        '''
        要求元素都比较小。时间效率是O(k+n),k为最大值。p为要排序的位置
        '''
        def get_position_value(v, p):
            for i in range(1, p+1):
                left = v % 10
                v = v/10
            return left
        countList = [0 for _ in range(10)]
        for v in alist:
            countList[get_position_value(v, p)] += 1
        sum = 0
        #calculate the position
        for i in range(10):
            sum += countList[i]
            countList[i] = sum

        retList = [0 for _ in range(len(alist))]
        for v in alist[::-1]:
            index = countList[get_position_value(v, p)]
            retList[index-1] = v
            countList[get_position_value(v, p)] -= 1
        return retList

    for i in range(1, length+1):
        data = count_sort(data, i)

    return data

9. 桶排序

博文最后更新时间:


评论

  • 暂无评论

发表评论