kelele67的学习笔记-python数据结构算法（二）

发表于 | 阅读次数

Python数据结构篇(2)

学习自大神博客

排序

  1. 冒泡排序：O(n2)
  2. 选择排序：O(n2)
  3. 插入排序：O(n2)O(n2)
  4. 快速排序：O(nlogn) ~ O(n2)
  5. 合并排序：O(nlogn)
  6. 希尔排序：[O(n),O(n2)]

冒泡排序

冒泡排序(bubble sort)：每个回合都从第一个元素开始和它后面的元素比较，如果比它后面的元素更大的话就交换，一直重复，直到这个元素到了它能到达的位置。每次遍历都将剩下的元素中最大的那个放到了序列的“最后”(除去了前面已经排好的那些元素)注意检测是否已经完成了排序，如果已完成就可以退出了。时间复杂度O(n2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def short_bubble_sort(a_list):
    exchanges = True
    pass_num = len(a_list) - 1
    while pass_num > 0 and exchanges:
        exchanges = False
        for i in range(pass_num):
            if a_list[i] > a_list[i + 1]:
                exchanges = True
                a_list[i], a_list[i + 1] = a_list[i + 1], a_list[i]
        pass_num = pass_num - 1
if __name__ == '__main__':
    a_list = [20, 40, 30, 90, 50, 80, 70, 60, 110, 100]
    short_bubble_sort(a_list)
    print(a_list)

选择排序

选择排序(selection sort)：每个回合都选择出剩下的元素中最大的那个，选择的方法是首先默认第一元素是最大的，如果后面的元素比它大的话，那就更新剩下的最大的元素值，找到剩下元素中最大的之后将它放入到合适的位置就行了。和冒泡排序类似，只是找剩下的元素中最大的方式不同而已。时间复杂度O(n2)

1
2
3
4
5
6
7
8
9
10
11
def selection_sort(a_list):
    for fill_slot in range(len(a_list) - 1, 0, -1):
        pos_of_max = 0
        for location in range(1, fill_slot + 1):
            if a_list[location] > a_list[pos_of_max]:
                pos_of_max = location
        a_list[fill_slot], a_list[pos_of_max] = a_list[pos_of_max], a_list[fill_slot]
a_list = [54, 26, 93, 17, 77, 31, 44, 55, 20]
selection_sort(a_list)
print(a_list)

插入排序

插入排序(insertion sort)：每次假设前面的元素都是已经排好序了的，然后将当前位置的元素插入到原来的序列中，为了尽快地查找合适的插入位置，可以使用二分查找。时间复杂度O(n2)O(n2)，别误以为二分查找可以降低它的复杂度，因为插入排序还需要移动元素的操作！

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
def insertion_sort(a_list):
    for index in range(1, len(a_list)):
        current_value = a_list[index]
        position = index
        while position > 0 and a_list[position - 1] > current_value:
            a_list[position] = a_list[position - 1]
            position = position - 1
        a_list[position] = current_value
def insertion_sort_binarysearch(a_list):
    for index in range(1, len(a_list)):
        current_value = a_list[index]
        positon = index
        low = 0
        high = index - 1
        while low<= high:
            mid = (low + high)/2
            if a_list[mid] > current_value:
                high = mid - 1
            else:
                low = mid + 1
        while positon> low:
            a_list[positon] = a_list[positon - 1]
            positon = positon - 1
            a_list[positon] = current_value
a_list = [54, 26, 93, 15, 77, 31, 44, 55, 20]
insertion_sort(a_list)
print(a_list)
insertion_sort_binarysearch(a_list)
print(a_list)

快速排序

快速排序(quick sort)：
想法一：如下图所示，它选择第一个元素作为主元，它同样可以按照下面提到的算法导论中将数组分成了4个不同的部分，但是这里其实有更好的解释方法。首先，它每次都是选择第一个元素都为主元，这个回合就是要确定主元的位置；然后，有两个指针，一个 leftmark 指向主元的后面一个位置，另一个 rightmark 指向要排序的数组最后一个元素；接着，两个指针分别向中间移动 leftmark遇到比主元大的元素停止，rightmark 遇到比主元小的元素停止，如果此时 leftmark < rightmark，也就是说中间还有未处理(未确定与主元大小关系)的元素，那么就交换 leftmark 和 rightmark 位置上的元素，然后重复刚才的移动操作，直到 rightmark < leftmark；最后，停止移动时候 rightmark就是主元要放置的位置，因为它停在一个比主元小的元素的位置上，之后交换主元和 rightmark指向的元素即可。完了之后，递归地对主元左右两边的数组进行排序即可。

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
def quick_sort(a_list):
    quick_sort_hepler(a_list, 0, len(a_list) - 1)
def quick_sort_hepler(a_list, first, last):
    if first < last:
        split_point = partition(a_list, first, last)
        quick_sort_hepler(a_list, first, split_point - 1)
        quick_sort_hepler(a_list, split_point + 1, last)
def partition(a_list, first, last):
    pivot_value = a_list[first]
    left_mark = first + 1
    right_mark = last
    done = False
    while not done:
        while left_mark <= right_mark and a_list[left_mark] <= pivot_value:
            left_mark = left_mark + 1
        while a_list[right_mark] >= pivot_value and right_mark >= left_mark:
            right_mark = right_mark - 1
        if right_mark < left_mark:
            done = True
        else:
            temp = a_list[left_mark]
            a_list[left_mark] = a_list[right_mark]
            a_list[right_mark] = temp
    temp = a_list[first]
    a_list[first] = a_list[right_mark]
    a_list[right_mark] = temp
    return right_mark
a_list = [54, 26, 93, 17, 77, 31, 44, 55, 20]
quick_sort(a_list)
print(a_list)