足球盘口软件
当前位置: 足球盘口软件 > 前端 >
Python实现常用的排序算法的示例,Python对两个有序列表进行合并和排序的例子

假设有2个有序列表l1、l2,如何效率比较高的将2个list合并并保持有序状态,这里默认排序是正序。

1 台阶问题/斐波纳挈

一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

Python

fib = lambda n: n if n <= 2 else fib(n - 1) + fib(n - 2)

1
fib = lambda n: n if n <= 2 else fib(n - 1) + fib(n - 2)

第二种记忆方法

Python

def memo(func): cache = {} def wrap(*args): if args not in cache: cache[args] = func(*args) return cache[args] return wrap @ memo def fib(i): if i < 2: return 1 return fib(i-1) + fib(i-2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def memo(func):
    cache = {}
    def wrap(*args):
        if args not in cache:
            cache[args] = func(*args)
        return cache[args]
    return wrap
 
 
@ memo
def fib(i):
    if i < 2:
        return 1
    return fib(i-1) + fib(i-2)

第三种方法

Python

def fib(n): a, b = 0, 1 for _ in xrange(n): a, b = b, a + b return b

1
2
3
4
5
def fib(n):
    a, b = 0, 1
    for _ in xrange(n):
        a, b = b, a + b
    return b

为了防止误导读者,本文所有概念性内容均截取自对应Wiki

复制代码 代码如下:

思路是比较简单的,无非是依次比较l1和l2头部第一个元素,将比较小的放在一个新的列表中,以此类推,直到所有的元素都被放到新的列表中。

2 变态台阶问题

一只青蛙一次可以跳上1级台阶,也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

Python

fib = lambda n: n if n < 2 else 2 * fib(n - 1)

1
fib = lambda n: n if n < 2 else 2 * fib(n - 1)

冒泡排序

# -*- coding: utf-8 -*-
# 测试各种排序算法
# link:www.jb51.net
# date:2013/2/2

考虑2个列表l1 = [2], l2 = [1],如何将他们合并呢?(注意:下面实现会改变l1和l2本来的值)

3 矩形覆盖

我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形,总共有多少种方法?

2*n个矩形的覆盖方法等于第2*(n-1)加上第2*(n-2)的方法。

Python

f = lambda n: 1 if n < 2 else f(n - 1) + f(n - 2)

1
f = lambda n: 1 if n < 2 else f(n - 1) + f(n - 2)

原理

#选择排序
def select_sort(sort_array):
    for i, elem in enumerate(sort_array):
        for j, elem in enumerate(sort_array[i:]):
            if sort_array[i] > sort_array[j + i]:
                #交换
                sort_array[i], sort_array[j + i] = sort_array[j

复制代码 代码如下:

4 杨氏矩阵查找

在一个m行n列二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。

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

  • i], sort_array[i]

def signle_merge_sort(l1, l2):
    tmp = []
    if l1[0] < l2[0]:
        tmp.append(l1[0])
        tmp.extend(l2)
        del l2[0]
    else:
        tmp.append(l2[0])
        tmp.extend(l1)
        del l1[0]
    return tmp

5 去除列表中的重复元素

用集合

Python

list(set(l))

1
list(set(l))

用字典

Python

l1 = ['b','c','d','b','c','a','a'] l2 = {}.fromkeys(l1).keys() print l2

1
2
3
l1 = ['b','c','d','b','c','a','a']
l2 = {}.fromkeys(l1).keys()
print l2

用字典并保持顺序

Python

l1 = ['b','c','d','b','c','a','a'] l2 = list(set(l1)) l2.sort(key=l1.index) print l2

1
2
3
4
l1 = ['b','c','d','b','c','a','a']
l2 = list(set(l1))
l2.sort(key=l1.index)
print l2

列表推导式

Python

l1 = ['b','c','d','b','c','a','a'] l2 = [] [l2.append(i) for i in l1 if not i in l2]

1
2
3
l1 = ['b','c','d','b','c','a','a']
l2 = []
[l2.append(i) for i in l1 if not i in l2]

面试官提到的,先排序然后删除.

步骤

#冒泡排序
def bubble_sort(sort_array):
    for i, elem in enumerate(sort_array):
        for j, elem in enumerate(sort_array[:len(sort_array) - i - 1]):
            if sort_array[j] > sort_array[j + 1]:
                sort_array[j], sort_array[j + 1] = sort_array[j

这真的只能处理一个元素的情形,还不能解决问题,不过好歹我们有一个大概的思路了。如果有列表中2个元素,上面的方法就不行了。我们需要解决边界判断问题,即当l1或者l2有一个为空的时,将剩下的一个list加到排序结果的尾部。然后确保函数每次调用只处理一个元素,通过递归来解决问题。

6 链表成对调换

1->2->3->4转换成2->1->4->3.

Python

class ListNode: def __init__(self, x): self.val = x self.next = None class Solution: # @param a ListNode # @return a ListNode def swapPairs(self, head): if head != None and head.next != None: next = head.next head.next = self.swapPairs(next.next) next.next = head return next return head

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
 
class Solution:
    # @param a ListNode
    # @return a ListNode
    def swapPairs(self, head):
        if head != None and head.next != None:
            next = head.next
            head.next = self.swapPairs(next.next)
            next.next = head
            return next
        return head

冒泡排序算法的运作如下:

  • 1], sort_array[j]

复制代码 代码如下:

7 创建字典的方法

比较相邻的元素。如果第一个比第二个大,就交换他们两个。

#插入排序
def insert_sort(sort_array):
    for i, elem in enumerate(sort_array):
        for j, elem in enumerate(sort_array[:i]):
            if sort_array[j] > sort_array[i]:
                sort_array.insert(j, sort_array[i])
                del sort_array[i + 1]
#归并排序
def merge_sort_wrapper(sort_array):
    merge_sort(sort_array, 0, len(sort_array) - 1)

def recursion_merge_sort1(l1, l2):
    tmp = []
    if len(l1) == 0:
        tmp.extend(l2)
        return tmp
    elif len(l2) == 0:
        tmp.extend(l1)
        return tmp
    else:
        if l1[0] < l2[0]:
            tmp.append(l1[0])
            del l1[0]
        else:
            tmp.append(l2[0])
            del l2[0]
        tmp += recursion_merge_sort1(l1, l2)
    return tmp

1 直接创建

Python

dict = {'name':'earth', 'port':'80'}

1
dict = {'name':'earth', 'port':'80'}

对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。

def merge_sort(sort_array, left = 0, right = 0):
    if left < right:
        center = (left + right) / 2
        merge_sort(sort_array, left, center)
        merge_sort(sort_array, center + 1, right)
        merge(sort_array, left, right, center)

上面的程序有2个问题:if判断太多;每次都要初始化tmp,对内存使用似乎不太友好。考虑到程序在l1或者l2有一个为空的时候就终止,可以稍微改写一下:

2 工厂方法

Python

items=[('name','earth'),('port','80')] dict2=dict(items) dict1=dict((['name','earth'],['port','80']))

1
2
3
items=[('name','earth'),('port','80')]
dict2=dict(items)
dict1=dict((['name','earth'],['port','80']))

针对所有的元素重复以上的步骤,除了最后一个。

def merge(sort_array, left, right, center):
    result = []
    arrayA = sort_array[left:center + 1]
    arrayB = sort_array[center + 1:right + 1]
    while((len(arrayA) > 0) and (len(arrayB) > 0)):
        if(arrayA[0] > arrayB[0]):
            result.append(arrayB.pop(0))
        else:
            result.append(arrayA.pop(0))

复制代码 代码如下:

3 fromkeys()方法

Python

dict1={}.fromkeys(('x','y'),-1) dict={'x':-1,'y':-1} dict2={}.fromkeys(('x','y')) dict2={'x':None, 'y':None}

1
2
3
4
dict1={}.fromkeys(('x','y'),-1)
dict={'x':-1,'y':-1}
dict2={}.fromkeys(('x','y'))
dict2={'x':None, 'y':None}

持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

    if(len(arrayA) > 0):
        result.extend(arrayA)
    if(len(arrayB) > 0):
        result.extend(arrayB)  
    sort_array[left:right + 1] = result

def _recursion_merge_sort2(l1, l2, tmp):
    if len(l1) == 0 or len(l2) == 0:
        tmp.extend(l1)
        tmp.extend(l2)
        return tmp
    else:
        if l1[0] < l2[0]:
            tmp.append(l1[0])
            del l1[0]
        else:
            tmp.append(l2[0])
            del l2[0]
        return _recursion_merge_sort2(l1, l2, tmp)

8 合并两个有序列表

知乎远程面试要求编程

尾递归

Python

def _recursion_merge_sort2(l1, l2, tmp): if len(l1) == 0 or len(l2) == 0: tmp.extend(l1) tmp.extend(l2) return tmp else: if l1[0] < l2[0]: tmp.append(l1[0]) del l1[0] else: tmp.append(l2[0]) del l2[0] return _recursion_merge_sort2(l1, l2, tmp) def recursion_merge_sort2(l1, l2): return _recursion_merge_sort2(l1, l2, [])

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def _recursion_merge_sort2(l1, l2, tmp):
    if len(l1) == 0 or len(l2) == 0:
        tmp.extend(l1)
        tmp.extend(l2)
        return tmp
    else:
        if l1[0] < l2[0]:
            tmp.append(l1[0])
            del l1[0]
        else:
            tmp.append(l2[0])
            del l2[0]
        return _recursion_merge_sort2(l1, l2, tmp)
 
def recursion_merge_sort2(l1, l2):
    return _recursion_merge_sort2(l1, l2, [])

循环算法

Python

def loop_merge_sort(l1, l2): tmp = [] while len(l1) > 0 and len(l2) > 0: if l1[0] < l2[0]: tmp.append(l1[0]) del l1[0] else: tmp.append(l2[0]) del l2[0] tmp.extend(l1) tmp.extend(l2) return tmp

1
2
3
4
5
6
7
8
9
10
11
12
def loop_merge_sort(l1, l2):
    tmp = []
    while len(l1) > 0 and len(l2) > 0:
        if l1[0] < l2[0]:
            tmp.append(l1[0])
            del l1[0]
        else:
            tmp.append(l2[0])
            del l2[0]
    tmp.extend(l1)
    tmp.extend(l2)
    return tmp

代码

#快排   
def quick_sort(sort_array):
    if(len(sort_array) < 2):
        return

def recursion_merge_sort2(l1, l2):
    return _recursion_merge_sort2(l1, l2, [])

9 交叉链表求交点

去哪儿的面试,没做出来.

Python

class ListNode: def __init__(self, x): self.val = x self.next = None def node(l1, l2): length1, lenth2 = 0, 0 # 求两个链表长度 while l1.next: l1 = l1.next length1 += 1 while l2.next: l2 = l2.next length2 += 1 # 长的链表先走 if length1 > lenth2: for _ in range(length1 - length2): l1 = l1.next else: for _ in range(length2 - length1): l2 = l2.next while l1 and l2: if l1.next == l2.next: return l1.next else: l1 = l1.next l2 = l2.next

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
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
def node(l1, l2):
    length1, lenth2 = 0, 0
    # 求两个链表长度
    while l1.next:
        l1 = l1.next
        length1 += 1
    while l2.next:
        l2 = l2.next
        length2 += 1
    # 长的链表先走
    if length1 > lenth2:
        for _ in range(length1 - length2):
            l1 = l1.next
    else:
        for _ in range(length2 - length1):
            l2 = l2.next
    while l1 and l2:
        if l1.next == l2.next:
            return l1.next
        else:
            l1 = l1.next
            l2 = l2.next

def bubble_sort(list):
    length = len(list)
    # 第一级遍历
    for index in range(length):
        # 第二级遍历
        for j in range(1, length - index):
            if list[j - 1] > list[j]:
                # 交换两者数据,这里没用temp是因为python 特性元组。
                list[j - 1], list[j] = list[j], list[j - 1]
    return list
这种排序其实还可以稍微优化一下,添加一个标记,在排序已完成时,停止排序。

    left = [x for x in sort_array[1:] if x < sort_array[0]]
    right = [x for x in sort_array[1:] if x >= sort_array[0]]
    quick_sort(left)
    quick_sort(right)
    sort_array[:] = left + [sort_array[0]] + right

但是对于Python而言,即使是尾递归,效率也不是那么高,为了避免爆栈,通常还是会用循环来做,再稍微改写一下:

10 二分查找

Python

def binarySearch(l, t): low, high = 0, len(l) - 1 while low < high: print low, high mid = (low + high) / 2 if l[mid] > t: high = mid elif l[mid] < t: low = mid + 1 else: return mid return low if l[low] == t else False if __name__ == '__main__': l = [1, 4, 12, 45, 66, 99, 120, 444] print binarySearch(l, 12) print binarySearch(l, 1) print binarySearch(l, 13) print binarySearch(l, 444)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def binarySearch(l, t):
    low, high = 0, len(l) - 1
    while low < high:
        print low, high
        mid = (low + high) / 2
        if l[mid] > t:
            high = mid
        elif l[mid] < t:
            low = mid + 1
        else:
            return mid
    return low if l[low] == t else False
 
if __name__ == '__main__':
    l = [1, 4, 12, 45, 66, 99, 120, 444]
    print binarySearch(l, 12)
    print binarySearch(l, 1)
    print binarySearch(l, 13)
    print binarySearch(l, 444)

def bubble_sort_flag(list):
    length = len(list)
    for index in range(length):
        # 标志位
        flag = True
        for j in range(1, length - index):
            if list[j - 1] > list[j]:
                list[j - 1], list[j] = list[j], list[j - 1]
                flag = False
        if flag:
            # 没有发生交换,直接返回list
            return list
    return list

#shell排序
def shell_sort(sort_array):
    dist=len(sort_array)/2 
    while dist > 0: 
        for i in range(dist,len(sort_array)): 
            tmp=sort_array[i] 
            j = i 
            while j >= dist and tmp < sort_array[j - dist]: 
                sort_array[j] = sort_array[j - dist] 
                j -= dist 
            sort_array[j] = tmp 
        dist /= 2 

复制代码 代码如下:

11 快排

Python

def qsort(seq): if seq==[]: return [] else: pivot=seq[0] lesser=qsort([x for x in seq[1:] if x<pivot]) greater=qsort([x for x in seq[1:] if x>=pivot]) return lesser+[pivot]+greater if __name__=='__main__': seq=[5,6,78,9,0,-1,2,3,-65,12] print(qsort(seq))

1
2
3
4
5
6
7
8
9
10
11
12
def qsort(seq):
    if seq==[]:
        return []
    else:
        pivot=seq[0]
        lesser=qsort([x for x in seq[1:] if x<pivot])
        greater=qsort([x for x in seq[1:] if x>=pivot])
        return lesser+[pivot]+greater
 
if __name__=='__main__':
    seq=[5,6,78,9,0,-1,2,3,-65,12]
    print(qsort(seq))

选择排序

#基数排序,均为整数,不支持负数和重复
def radix_sort(sort_array):
    max_elem = max(sort_array)
    bucket_list = []
    for i in range(max_elem):
        bucket_list.insert(i, 0)

def loop_merge_sort(l1, l2):
    tmp = []
    while len(l1) > 0 and len(l2) > 0:
        if l1[0] < l2[0]:
            tmp.append(l1[0])
            del l1[0]
        else:
            tmp.append(l2[0])
            del l2[0]
    tmp.extend(l1)
    tmp.extend(l2)
    return tmp

12 找零问题

Python

def coinChange(values, money, coinsUsed): #values T[1:n]数组 #valuesCounts 钱币对应的种类数 #money 找出来的总钱数 #coinsUsed 对应于目前钱币总数i所使用的硬币数目 for cents in range(1, money+1): minCoins = cents #从第一个开始到money的所有情况初始 for value in values: if value <= cents: temp = coinsUsed[cents - value] + 1 if temp < minCoins: minCoins = temp coinsUsed[cents] = minCoins print('面值为:{0} 的最小硬币数目为:{1} '.format(cents, coinsUsed[cents]) ) if __name__ == '__main__': values = [ 25, 21, 10, 5, 1] money = 63 coinsUsed = {i:0 for i in range(money+1)} coinChange(values, money, coinsUsed)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def  coinChange(values, money, coinsUsed):
    #values    T[1:n]数组
    #valuesCounts   钱币对应的种类数
    #money  找出来的总钱数
    #coinsUsed   对应于目前钱币总数i所使用的硬币数目
    for cents in range(1, money+1):
        minCoins = cents     #从第一个开始到money的所有情况初始
        for value in values:
            if value <= cents:
                temp = coinsUsed[cents - value] + 1
                if temp < minCoins:
                    minCoins = temp
        coinsUsed[cents] = minCoins
        print('面值为:{0} 的最小硬币数目为:{1} '.format(cents, coinsUsed[cents]) )
 
if __name__ == '__main__':
    values = [ 25, 21, 10, 5, 1]
    money = 63
    coinsUsed = {i:0 for i in range(money+1)}
    coinChange(values, money, coinsUsed)

原理

    for x in sort_array:
        bucket_list[x - 1] = -1

今天栽了个坑,好好反省,就是这样。

13 广度遍历和深度遍历二叉树

给定一个数组,构建二叉树,并且按层次打印这个二叉树

Python

## 14 二叉树节点 class Node(object): def __init__(self, data, left=None, right=None): self.data = data self.left = left self.right = right tree = Node(1, Node(3, Node(7, Node(0)), Node(6)), Node(2, Node(5), Node(4))) ## 15 层次遍历 def lookup(root): stack = [root] while stack: current = stack.pop(0) print current.data if current.left: stack.append(current.left) if current.right: stack.append(current.right) ## 16 深度遍历 def deep(root): if not root: return print root.data deep(root.left) deep(root.right) if __name__ == '__main__': lookup(tree) deep(tree)

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
## 14 二叉树节点
class Node(object):
    def __init__(self, data, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right
 
tree = Node(1, Node(3, Node(7, Node(0)), Node(6)), Node(2, Node(5), Node(4)))
 
## 15 层次遍历
def lookup(root):
    stack = [root]
    while stack:
        current = stack.pop(0)
        print current.data
        if current.left:
            stack.append(current.left)
        if current.right:
            stack.append(current.right)
## 16 深度遍历
def deep(root):
    if not root:
        return
    print root.data
    deep(root.left)
    deep(root.right)
 
if __name__ == '__main__':
    lookup(tree)
    deep(tree)

选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理大致是将后面的元素最小元素一个个取出然后按顺序放置。

    sort_array[:] = [x + 1 for x in range(len(bucket_list)) if bucket_list[x] == -1]

思路是比较简单的,无非是依次比较l...

17 前中后序遍历

深度遍历改变顺序就OK了

步骤

#堆排序
def heap_sort(sort_array):
   #没有写出来,再想想
   pass

18 求最大树深

Python

def maxDepth(root): if not root: return 0 return max(maxDepth(root.left), maxDepth(root.right)) + 1

1
2
3
4
def maxDepth(root):
        if not root:
            return 0
        return max(maxDepth(root.left), maxDepth(root.right)) + 1

在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,

#测试例子
def algo_sort_test(sort_array, sort_method):
    sort_method(sort_array)

19 求两棵树是否相同

Python

def isSameTree(p, q): if p == None and q == None: return True elif p and q : return p.val == q.val and isSameTree(p.left,q.left) and isSameTree(p.right,q.right) else : return False

1
2
3
4
5
6
7
def isSameTree(p, q):
    if p == None and q == None:
        return True
    elif p and q :
        return p.val == q.val and isSameTree(p.left,q.left) and isSameTree(p.right,q.right)
    else :
        return False

再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。

if __name__ == '__main__':

20 前序中序求后序

推荐:

Python

def rebuild(pre, center): if not pre: return cur = Node(pre[0]) index = center.index(pre[0]) cur.left = rebuild(pre[1:index + 1], center[:index]) cur.right = rebuild(pre[index + 1:], center[index + 1:]) return cur def deep(root): if not root: return deep(root.left) deep(root.right) print root.data

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def rebuild(pre, center):
    if not pre:
        return
    cur = Node(pre[0])
    index = center.index(pre[0])
    cur.left = rebuild(pre[1:index + 1], center[:index])
    cur.right = rebuild(pre[index + 1:], center[index + 1:])
    return cur
 
def deep(root):
    if not root:
        return
    deep(root.left)
    deep(root.right)
    print root.data

重复第二步,直到所有元素均排序完毕。

    sort_array = [1, 2, 3, 5, -4, 4, 10, 3, 19, 13, 16, 18, 5, 190, 456, 23]
    algo_sort_test(sort_array, select_sort)
    print sort_array

21 单链表逆置

Python

class Node(object): def __init__(self, data=None, next=None): self.data = data self.next = next link = Node(1, Node(2, Node(3, Node(4, Node(5, Node(6, Node(7, Node(8, Node(9))))))))) def rev(link): pre = link cur = link.next pre.next = None while cur: tmp = cur.next cur.next = pre pre = cur cur = tmp return pre root = rev(link) while root: print root.data root = root.next

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Node(object):
    def __init__(self, data=None, next=None):
        self.data = data
        self.next = next
 
link = Node(1, Node(2, Node(3, Node(4, Node(5, Node(6, Node(7, Node(8, Node(9)))))))))
 
def rev(link):
    pre = link
    cur = link.next
    pre.next = None
    while cur:
        tmp = cur.next
        cur.next = pre
        pre = cur
        cur = tmp
    return pre
 
root = rev(link)
while root:
    print root.data
    root = root.next

代码

    sort_array = [1, 2, 3, 5, -4, 4, 10, 3, 19, 13, 16, 18, 5, 190, 456, 23]
    algo_sort_test(sort_array, bubble_sort)
    print sort_array   

def selection_sort(list):
    n=len(list)
   for i in range (0,n):
       min = i
       for j in range(i+1,n):
           if list[j]<list[min]:
               min=j
               list[min],list[i]=list[i],list[min]
   return list

    sort_array = [1, 2, 3, 5, -4, 4, 10, 3, 19, 13, 16, 18, 5, 190, 456, 23]
    algo_sort_test(sort_array, insert_sort)
    print sort_array     

插入排序

    sort_array = [1, 2, 3, 5, -4, 4, 10, 3, 19, 13, 16, 18, 5, 190, 456, 23]
    algo_sort_test(sort_array, merge_sort_wrapper)
    print sort_array

原理

    sort_array = [1, 2, 3, 5, -4, 4, 10, 300, 19, 13, 16, 18, 500, 190, 456, 23]
    algo_sort_test(sort_array, quick_sort)
    print sort_array 

插入排序(Insertion Sort)是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。

    sort_array = [1, 2, 3, 5, -4, 4, 10, 3, 19, 13, 16, 18, 5, 190, 456, 23]
    algo_sort_test(sort_array, shell_sort)
    print sort_array      

步骤

    sort_array = [1, 2, 3, 5, 4, 10, 19, 13, 16, 18, 190, 456, 23]
    algo_sort_test(sort_array, radix_sort)
    print sort_array      

从第一个元素开始,该元素可以认为已经被排序

    print 'OK'

取出下一个元素,在已经排序的元素序列中从后向前扫描

非常基础的知识内容,选择、冒泡、插入、归并、基数,还有快排都能手写出来,但写了一遍发现堆排序忘了怎么做了。要复习啦。

如果该元素(已排序)大于新元素,将该元素移到下一位置

代码如下: # -*- coding: utf-8 -*- # 测试各种排序算法 # link:www.jb51.net # date:2013/2/2 #选择排序 def select_sort(sort_array): for i, elem in enum...

重复步骤3,直到找到已排序的元素小于或者等于新元素的位置

将新元素插入到该位置后

重复步骤2~5

代码

def insert_sort(list):
    n = len(list)
    for i in range(1, n):
        # 后一个元素和前一个元素比较
        # 如果比前一个小
        if list[i] < list[i - 1]:
            # 将这个数取出
            temp = list[i]
            # 保存下标
            index = i
            # 从后往前依次比较每个元素
            for j in range(i - 1, -1, -1):
                # 和比取出元素大的元素交换
                if list[j] > temp:
                    list[j + 1] = list[j]
                    index = j
                else:
                    break
            # 插入元素
            list[index] = temp
    return list
希尔排序

原理

希尔排序,也称递减增量排序算法,是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。

希尔排序是基于插入排序的以下两点性质而提出改进方法的:

插入排序在对几乎已经排好序的数据操作时,效率高,即可以达到线性排序的效率

但插入排序一般来说是低效的,因为插入排序每次只能将数据移动一位。

步骤

每次以一定步长(就是跳过等距的数)进行排序,直至步长为1.

代码

def shell_sort(list):
    n = len(list)
    # 初始步长
    gap = round(n / 2)
    while gap > 0:
        for i in range(gap, n):
            # 每个步长进行插入排序
            temp = list[i]
            j = i
            # 插入排序
            while j >= gap and list[j - gap] > temp:
                list[j] = list[j - gap]
                j -= gap
            list[j] = temp
        # 得到新的步长
        gap = round(gap / 2)
    return list
步长使用的是Donald Shell的建议,另外步长还可以使用Sedgewick提出的(1, 5, 19, 41, 109,...)。

也可以使用 斐波那契数列 除去0和1将剩余的数以黄金分区比的两倍的幂进行运算得到的数列。

归并排序

原理

归并操作(归并算法),指的是将两个已经排序的序列合并成一个序列的操作。归并排序算法依赖归并操作。

步骤

迭代法

申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列

设定两个指针,最初位置分别为两个已经排序序列的起始位置

比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置

重复步骤3直到某一指针到达序列尾

将另一序列剩下的所有元素直接复制到合并序列尾

递归法

假设序列共有n个元素:

将序列每相邻两个数字进行归并操作,形成 {displaystyle floor(n/2)} floor(n/2)个序列,排序后每个序列包含两个元素

将上述序列再次归并,形成 {displaystyle floor(n/4)} floor(n/4)个序列,每个序列包含四个元素

重复步骤2,直到所有元素排序完毕

代码

# 递归法
def merge_sort(list):
    # 认为长度不大于1的数列是有序的
    if len(list) <= 1:
        return list
    # 二分列表
    middle = len(list) // 2
    left = merge_sort(list[:middle])
    right = merge_sort(list[middle:])
    # 最后一次合并
    return merge(left, right)
# 合并
def merge(left, right):
    l,r=0,0
    result=[]
    while l<len(left) and r<len(right):
        if left[l] <right[r]:
            result.append(left[l])
            l+=1
        else:
            result.append(right[r])
            r +=1
        reslut +=left[l:]
        result+=right[r:]               
    return result
鄙人不才,不知归并排序的迭代法如何用Python实现,望指教。

快速排序

原理

快速排序使用分治法(Divide and conquer)策略来把一个序列(list)分为两个子序列(sub-lists)。

步骤

从数列中挑出一个元素,称为"基准"(pivot),

重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区结束之后,该基准就处于数列的中间位置。这个称为分区(partition)操作。

递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。

代码

普通版

def quick_sort(list):
    less = []
    pivotList = []
    more = []
    # 递归出口
    if len(list) <= 1:
        return list
    else:
        # 将第一个值做为基准
        pivot = list[0]
        for i in list:
            # 将比急转小的值放到less数列
            if i < pivot:
                less.append(i)
            # 将比基准打的值放到more数列
            elif i > pivot:
                more.append(i)
            # 将和基准相同的值保存在基准数列
            else:
                pivotList.append(i)
        # 对less数列和more数列继续进行排序
        less = quick_sort(less)
        more = quick_sort(more)
        return less + pivotList + more
咳咳,下面这段代码出自《Python cookbook 第二版》传说中的三行实现python快速排序。

def qsort(arr):
    if len(arr) <= 1:
        return arr
    else:
        pivot = arr[0]
        return qsort([x for x in arr[1:] if x < pivot]) +
               [pivot] +
               qsort([x for x in arr[1:] if x >= pivot])
当然还有一行语法糖版本:

qs = lambda xs : ( (len(xs) <= 1 and [xs]) or [ qs( [x for x in xs[1:] if x < xs[0]] ) + [xs[0]] + qs( [x for x in xs[1:] if x >= xs[0]] ) ] )[0]
是不是感受到了Python的魅力?

堆排序

原理

堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。

步骤

创建最大堆:将堆所有数据重新排序,使其成为最大堆

最大堆调整:作用是保持最大堆的性质,是创建最大堆的核心子程序

堆排序:移除位在第一个数据的根节点,并做最大堆调整的递归运算

代码

def heap_sort(list):
    # 创建最大堆
    for start in range((len(list) - 2) // 2, -1, -1):
        sift_down(list, start, len(list) - 1)

    # 堆排序
    for end in range(len(list) - 1, 0, -1):
        list[0], list[end] = list[end], list[0]
        sift_down(list, 0, end - 1)
    return list

# 最大堆调整
def sift_down(lst, start, end):
    root = start
    while True:
        child = 2 * root + 1
        if child > end:
            break
        if child + 1 <= end and lst[child] < lst[child + 1]:
            child += 1
        if lst[root] < lst[child]:
            lst[root], lst[child] = lst[child], lst[root]
            root = child
        else:
            break
计数排序

原理

当输入的元素是n个0到k之间的整数时,它的运行时间是Θ(n + k)。计数排序不是比较排序,排序的速度快于任何比较排序算法。

由于用来计数的数组C的长度取决于待排序数组中数据的范围(等于待排序数组的最大值与最小值的差加上1),这使得计数排序对于数据范围很大的数组,需要大量时间和内存。例如:计数排序是用来排序0到100之间的数字的最好的算法,但是它不适合按字母顺序排序人名。但是,计数排序可以用在基数排序算法中,能够更有效的排序数据范围很大的数组。

步骤

找出待排序的数组中最大和最小的元素

统计数组中每个值为i的元素出现的次数,存入数组 C 的第 i 项

对所有的计数累加(从C中的第一个元素开始,每一项和前一项相加)

反向填充目标数组:将每个元素i放在新数组的第C(i)项,每放一个元素就将C(i)减去1

代码

def count_sort(list):
    min = 2147483647
    max = 0
    # 取得最大值和最小值
    for x in list:
        if x < min:
            min = x
        if x > max:
            max = x
    # 创建数组C
    count = [0] * (max - min +1)
    for index in list:
        count[index - min] += 1
    index = 0
    # 填值
    for a in range(max - min+1):
        for c in range(count[a]):
            list[index] = a + min
            index += 1
    return list
第九种排序

None?

当然不会

自然就是系统自带的

list.sort()

上一篇:mongodb数据抓取详细介绍 下一篇:没有了
返回顶部