Python数据结构以及排序

August 01, 2017 本文总阅读量次 7198

前记：

Python自带了一些数据结构,不需要自己实现既可以快速调用.

1.对数据的操作

  • 从序列提取变量
    首先是两个简单的提取变量栗子
    1
    2
    3
    4
    5
    6
    >>>p = (4,5)
    >>>x, y = p
    >>>x
    4
    >>>y
    5
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    >>>data = ['ACME',  50, 91.1, (2017, 8, 1) ]
    >>>name, shares, price, (year, mon, day) = data
    >>>name
    'ACME'
    >>>shares
    50
    >>>price
    91.1
    >>>year
    2017
    >>>mon
    8
    >>>day
    1
    python中的字符串可以分解（中文就不行。。。），在python中还可以通过函数来处理
    如这个栗子，去掉序列的第一个和最后一个数字
    1
    2
    3
    def drop_first_last(grades):
        first, *middle, last = grades
        return avg(middle)
  • 保留后面N个元素（使用到Python里面的collections模块）
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    >>> from collections import deque
    >>> q = deque(maxlen = 3)
    >>> q.append(1)
    >>> q.append(2)
    >>> q.append(3)
    >>> q
    deque([1, 2, 3], maxlen=3)
    >>> q.append(4)
    >>> q.append(4)
    >>> q
    deque([3, 4, 4], maxlen=3)
    >>> q.append(4)
    >>> q.append(5)
    >>> q.append(6)
    >>> q.append(7)
    >>> q
    deque([5, 6, 7], maxlen=3)

  • 控制字典元素顺序
    python中的字典元素是没有顺序的，OrderedDict()可以让字典拥有顺序
    注：（1）如果要josn字段也拥有顺序，那么josn.dumps(d)就OK了
    （2）OrderedDict()的大小是普通字典的两倍
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    >>> from collections import OrderedDict
    >>> d = OrderedDict()
    >>> d['foo'] = 1
    >>> d['bar'] = 2
    >>> d['spam'] = 3
    >>> d['grok'] = 4
    >>> for key in d:
    ...     print(key, d[key])
    ... 
    foo 1
    bar 2
    spam 3
    grok 4
    ps：字典里面有个zip函数可以将字典的key值和value值进行反转
    注意：zip()创建的是一个迭代器，内容只能被消费一次，例如只能print一次zipdict，第二次print时会报错
    1
    2
    dict = {'a':1, 'b':2, 'c':3}
    zipdict = zip(dict.vakues(), dict.keys())
  • 找出列表中出现最频繁的单词
    利用collections模块中的Counter类的most_commomn()方法可以直接显示结果
    1
    2
    3
    4
    5
    from collections import Counter
    list = [1,2,3,4,1,5,1,6,2,7,2,8,1,9,3]
    list_counts = Counter(list)
    top_three = list_counts.most_common(3)
    print(top_three)
    显示结果：[(1, 4), (2, 3), (3, 2)]
    当然，也可以用count计数，再用sorted进行排序

    2.语法糖

  • map()函数
    map()接受一个Iterable和一个函数，map将传入的函数依次作用到序列的每个元素，并把结果作为新的Iterator返回
1
2
3
4
5
6
>>> def f(x):
...     return x * x
...
>>> r = map(f, [1, 2, 3, 4, 5, 6, 7, 8, 9])
>>> list(r)
[1, 4, 9, 16, 25, 36, 49, 64, 81]
  • reduce()函数
    reduce把一个函数作用在一个序列[x1, x2, x3, …]上，这个函数必须接收两个参数，reduce把结果继续和序列的下一个元素做累积计算
    1
    2
    3
    4
    5
    6
    >>> from functools import reduce
    >>> def add(x, y):
    ...     return x + y
    ...
    >>> reduce(add, [1, 3, 5, 7, 9])
    25
  • filter()函数
    filter()把传入的函数依次作用于每个元素，然后根据返回值是True还是False决定保留还是丢弃该元素。
    1
    2
    3
    4
    5
    def is_odd(n):
        return n % 2 == 1

    list(filter(is_odd, [1, 2, 4, 5, 6, 9, 10, 15]))
    # 结果: [1, 5, 9, 15]
  • sorted()函数
    sorted()函数也是一个高阶函数，它不仅可以排序，它还可以接收一个key函数来实现自定义的排序
    默认排序
    1
    2
    >>> sorted([36, 5, -12, 9, -21])
    [-21, -12, 5, 9, 36]
    用key值实现排序
    1
    2
    >>> sorted([36, 5, -12, 9, -21], key=abs)
    [5, 9, -12, -21, 36]
  • 匿名函数
    在Python中，对匿名函数提供了有限支持。还是以map()函数为例，计算f(x)=x2时，除了定义一个f(x)的函数外，还可以直接传入匿名函数：
    1
    2
    >>> list(map(lambda x: x * x, [1, 2, 3, 4, 5, 6, 7, 8, 9]))
    [1, 4, 9, 16, 25, 36, 49, 64, 81]
    通过对比可以看出，匿名函数lambda x: x * x实际上就是：
    1
    2
    def f(x):
        return x * x
    匿名函数有个限制，就是只能有一个表达式，不用写return，返回值就是该表达式的结果

    3.算法排序

    虽然python本身有sorted，但还是了解一下比较好，毕竟你校招面试时别人问你用python写冒泡排序你直接写sorted()吧。。。（虽然我觉得这样的面试很奇怪，知道这部分思想就行了。。。）
    排序按模型分类有：

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

  • 冒泡算法
    之所以被叫为冒泡算法，是因为他就像泡泡一样，越大的元素会经由交换慢慢“浮”到数列的顶端
    而冒泡算法需要：
    （1）共循环 n-1 次
    （2）每次循环中，如果 前面的数大于后面的数，就交换
    （3）设置一个标签，如果上次没有交换，就说明这个是已经好了的（节省不必要的计算过程）。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    def bubble_sort(l):
        flag = True
        for i in range(len(l)-1, 0, -1):
            if flag: 
                flag = False
                for j in range(i):
                    if l[j] > l[j + 1]:
                        l[j], l[j+1] = l[j+1], l[j]
                        flag = True
            else:
                break
    num_list = [21,44,2,45,33,4,3,67]
    bubble_sort(num_list)
    print(num_list)  # [2, 3, 4, 21, 33, 44, 45, 67]
  • 选择排序
    选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。
    1
    2
    3
    4
    5
    6
    7
    8
    9
     def insert_sort(num_list):
      for i in range(len(num_list)-1):
        for j in range(i+1, len(num_list)):
          if num_list[i]>num_list[j]:
            num_list[i],num_list[j] = num_list[j],num_list[i]
      return num_list

    li = [21,44,2,45,33,4,3,67]
    print(insert_sort(li))
  • 插入排序
    插入排序总结：

1.当前需要排序的元素(array[i])，跟已经排序好的最后一个元素比较(array[i-1])，如果满足条件继续执行后面的程序，否则循环到下一个要排序的元素。
2.缓存当前要排序的元素的值，以便找到正确的位置进行插入。
3.排序的元素跟已经排序号的元素比较，比它大的向后移动(升序)。
4.要排序的元素，插入到正确的位置。

1
2
3
4
5
6
7
8
9
10
11
12
def insert_sort(array):
    for i in range(1, len(array)):
        if array[i - 1] > array[i]:
            temp = array[i]     # 当前需要排序的元素
            index = i           # 用来记录排序元素需要插入的位置
            while index > 0 and array[index - 1] > temp:
                array[index] = array[index - 1]     # 把已经排序好的元素后移一位，留下需要插入的位置
                index -= 1
                array[index] = temp # 把需要排序的元素，插入到指定位置
    return array
li = [21,44,2,45,33,4,3,67]
print(insert_sort(li))

这段程序主要就在while里面，每增加一个数，就要扔进while里面，再从里面列表的最后一个数开始比较，直到这个新增加的数比列表里面的数大才停止比较

  • 归并排序
    归并排序描述起来好简单。就是把规模分成两组，一组都小于某个数n, 另一组都大于等于n。于是规模为n的问题，变成了2个n/2规模的问题。一次次这样划分下去，直到只剩下一个元素,一个元素当然是排好充的,然后再两两合并,直到得到原始问题的解。
    其最坏情况是Θ(nlgn)
    这个思想是分治法
    可以看做是把他一直一半一半的切，切到为一个数据，再用类似选择排序那样慢慢比较大小，最后慢慢组合起来

    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
    #升序
    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
                print(ret,'c')
            return ret
     
        if not literal or len(literal) == 1:
            return literal

        literal1, literal2 = divide(literal)
        print(literal1,literal2,'a')
        literal1 = conquer(literal1)
        literal2 = conquer(literal2)
        print(literal1,literal2,'b')
        return  merge(literal1, literal2)
    li = [21,44,2,45,33,4,3,67]
    print(merge_sort(li))

  • 快速排序
    快速排序（Quicksort）是对冒泡排序的一种改进。由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    def quick_sort(num_list):

      if num_list == []:
        return num_list
      smallList = []
      bigList = []
      middleElement = num_list[0]
      for i in num_list[1:]:
        if i <= middleElement:
          smallList.append(i)
        else:
          bigList.append(i)
      return quick_sort(smallList)+[middleElement]+quick_sort(bigList)
    li = [21,44,2,45,33,4,3,67]
    print(quick_sort(li))

  • 算法排序小总结
    当然还有堆排（暂时不知道怎么写- -），基数排序等/这些都是内部排序(内部排序是数据记录在内存中进行排序)，当n较大，则应采用时间复杂度为O(nlog2n)的排序方法：快速排序、堆排序或归并排序序
    这些排序里面，快速排序是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短；插入排序是稳定的；
    在写总结时，顺便百度了一下，结果发现有个dalao写了这个看后受益匪浅啊～

查看评论