12，常见的数据结构和排序算法_1.排序算法通常使用什么数据结构和存储结构?为什么?

常用数据结构

栈（stack）

栈，也被称为栈堆，是一种容器，支持存入元素、访问元素和删除元素。
栈的特点为只允许从容器的一端（栈顶）进行加入数据（push）和输出数据（pop）的运算。
栈没有位置的概念，保证可以访问、删除的都一定是最后存入的那个元素。这是一种默认的访问顺序。

由于栈数据结构只允许在一段进行操作，因而按照后进先出的原理运作（LIFO, Last In First Out)。

栈的实现

class Stack(object):
    def __init__(self):
        self.__list = []

    def push(self, item):
        '''Add a new item to the top'''
        self.__list.append(item)

    def pop(self):
        '''Pop the item in the top'''
        self.__list.pop()

    def peek(self):
        '''Return the item in the top'''
        if self.__list:
            return self.__list[-1]
        else:
            return None

    def is_empty(self):
        '''Decide whether the stack is empty'''
        return self.__list == []

    def size(self):
        '''Return the size of the stack'''
        return len(self.__list)
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
'
运行
运行

队列（queue）

队列（queue）是一种只允许在一段进行插入操作、另一端进行删除操作的线性表。
队列遵循先进先出（FIFO，First In First Out）的顺序。
被允许进行插入操作的一端为队尾，被允许删除的那一端为队首。
假设队列q = (a1, a2, …, an)，那么a1就是队头元素，an则是队尾元素。
我们总是从队首开始删除，在队尾进行插入。

队列的实现

class queue(object):
    def __init__(self):
        self.__list = []

    def enqueue(self, item):
        self.__list.append(item)

    def dequeue(self):
        return self.__list.pop(0)

    def is_empty(self):
        return self.__list == []

    def size(self):
        return len(self.__list)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
'
运行
运行

双向队列（deque）

Deque，全名double-ended queue，是一种具有队列和栈的性质的数据结构。
双端队列中的元素可以从两端弹出，插入和删除操作在标的两端进行。

双向队列的实现

class Deque(object):
    '''双端队列'''
    def __init__(self):
        self.__list = []

    def add_front(self, item):
        '''在头部添加'''
        self.__list.insert(0, item)

    def add_rear(self, item):
        '''在尾部添加'''
        self.__list.append(item)

    def pop_front(self):
        return self.__list.pop(0)

    def pop_rear(self):
        return self.__list.pop()

    def is_empty(self):
        return self.__list == []

    def size(self):
        return len(self.__list)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
'
运行
运行

常用排序算法

冒泡排序（bubble sort)

def bubble_sort(alist):
    n = len(alist)
    for j in range(n-1):
        for i in range(0, n - 1):
            if alist[i] > alist[i+1]:
                alist[i], alist[i + 1] = alist[i + 1], alist[i]
1
2
3
4
5
6
'
运行
运行

选择排序（select sort）

def select_sort(alist):
    n = len(alist)
    for j in range(n-1):
        min_index = j
        for i in range(j+1, n):
            if alist[min_index] > alist[i]:
                min_index = i
        alist[j], alist[min_index] = alist[min_index], alist[j]
1
2
3
4
5
6
7
8
'
运行
运行

插入排序

def insert_sort(alist):
    n = len(alist)
    for j in range(1, n):
        i = j
        while i > 0:
            if alist[i] < alist[i-1]:
                alist[i], alist[i-1] = alist[i-1], alist[i]
                i -= 1
            else:
                break
1
2
3
4
5
6
7
8
9
10
'
运行
运行