【数据】数据结构，查询排序算法

排队问题

事件驱动

历史记录

括号匹配问题

压栈调用

链表（Linked List）是通过指针连接起来的一系列节点，每个节点有自身数据，然后指向下一个节点，形成一条数据链。

动态结构：内存空间可以动态申请，适合不确定数据量的场景。

查询慢，插入快

单链表必须从头依次遍历查找，时间复杂度为O(n)

在单链表中，一旦定位好要插入的位置，插入结点的时间复杂度是很低的，就是 O(1)。

删除节点快，时间复杂度为O(1)

花名册录入

适合不确定数据量的场景。

升级循环单项链表

双向链表（Doubly Linked List） 是一种链式存储结构，它与单向链表不同之处在于：每个节点（Node）除了存储数据（data）外，有两个指针指向前后

一个节点通常包含三个部分

节点可以向前查找，向后查找

(1) 在头部插入

(2) 在尾部插入

查找操作从头节点开始遍历，直到找到目标节点或遍历完链表。

升级循环双向链表

回顾回述问题

跳表的做法就是给链表做索引，而且是分层索引。第一层索引是n/2个，第二层的索引是n/4个，第三层索引是n/8个，即每隔两个数据就记下个索引

索引对象记录了三个数据，一个是要比对的数据值，一个是索引的下一个索引，还有就是索引下层的索引或链表。

最底层的链表包含所有元素；如果一个元素出现在第i层的链表中，则它在第i层之下的链表也都会出现；

跳表是需要建立索引的，大概建立n个索引，是用空间换时间的典型算法，只不过跳表所需要的空间不是链表中存储的数据对象。

那第一级索引的结点个数大约就是 n/2，第二级索引的结点个数大约就是 n/4

也就是说，第 k 级索引的结点个数是第 k-1 级索引的结点个数的 1/2，那第 k级索引结点的个数就是 n/(2的k次方)。

查询的时间平均复杂度为 logn

高效的动态插入，而且插入操作的时间复杂度也是 O(logn)。

对于纯粹的单链表，有序需要遍历每个结点，来找到插入的位置。复杂度会达到O(n)

当我们往跳表中插入数据的时候，我们可以选择同时将这个数据插入到部分索引层中。而我们通过一个随机函数，来决定将这个结点插入到哪几级索引中，比如随机函数生成了值 K

比起单纯的单链表，跳表需要存储多级索引，肯定要消耗更多的存储空间。那到底需要消耗多少额外的存储空间呢？

假设原始链表大小为 n，那第一级索引大约有 n/2 个结点，第二级索引大约有 n/4 个结点，以此类推，每上升一级就减少一半，直到剩下 2 个结点。如果我们把每层索引的结点数写出来是一个等比数列。这几级索引的结点总和就是 n/2+n/4+n/8…+8+4+2=n-2。所以，跳表的空间复杂度是 O(n)。也就是说，如果将包含 n 个结点的单链表构造成跳表，我们需要额外再用接近 n 个结点的存储空间。

实际上，在软件开发中，我们不必太在意索引占用的额外空间。在讲数据结构和算法时，我们习惯性地把要处理的数据看成整数，但是在实际的软件开发中，原始链表中存储的有可能是很大的对象，而索引结点只需要存储关键值和几个指针，并不需要存储对象，所以当对象比索引结点大很多时，那索引占用的额外空间就可以忽略了。

跳表的本质是一个多层的有序链表，同时结合了二分和链表的思想；

由很多层索引组成，每一层索引是通过随机函数随机产生的，每一层都是一个有序的链表，默认是升序 ；

如果顺序错误则交换

每轮确定一个最大值

O(n^2)

O(n^2)

常数级空间O(1)

不需要额外数组

稳定排序算法

外层循环控制轮数

相邻元素比较

def bubble_sort_recursion(self, array=None):
        """
        # every loop block to find a max object by comparing one by one.
        # then using recursion to sort remaining raw_array[0:n-1].
        """
        n = len(array)
        if n < 2:
            return array
        # using the for loop to find the max number index.
        for i in range(0, len(array) - 1):
            if array[i] > array[i + 1]:
                temp = array[i]
                array[i] = array[i + 1]
                array[i + 1] = temp
        return self.bubble_sort_recursion(array[0:n-1]) + [array[n-1]]

提前结束排序

从两端向中间遍历

O(n^2)

def selected_sort(self, array=None):
        """
        # every loop block to find a min object, and then to exchange to the first position.
        # opt: in one loop to find the min and max object at same time.
        """
        if array:
            self.raw_array = array
        for j in range(0, len(self.raw_array) - 1):  # n-1 times loop.
            temp = self.raw_array[j]
            for ii in range(j + 1, len(self.raw_array)):
                if temp > self.raw_array[ii]:
                    temp = self.raw_array[ii]
                    self.raw_array[ii] = self.raw_array[j]
                    self.raw_array[j] = temp
        return self.raw_array

    def selected_sort_opt(self, array=None):
        """
        # every loop block to find a min index and max index,
        # and then to exchange to the first and last position.
        """
        if array:
            self.raw_array = array
        n = len(self.raw_array)
        i_left = 0
        i_right = n - 1
        while i_left < i_right:
            index_min, index_max = i_left, i_left
            # find the min and max index in one loop from the left to right.
            for i in range(i_left, i_right + 1):
                if self.raw_array[index_min] > self.raw_array[i]:
                    index_min = i
                if self.raw_array[index_max] < self.raw_array[i]:
                    index_max = i
            # judge the min and max mun in one loop, and then to exchange the position.
            if index_min != i_left:
                tl = self.raw_array[i_left]
                self.raw_array[i_left] = self.raw_array[index_min]
                self.raw_array[index_min] = tl
            if index_max == i_left:
                index_max = index_min
            if index_max != i_right:
                tr = self.raw_array[i_right]
                self.raw_array[i_right] = self.raw_array[index_max]
                self.raw_array[index_max] = tr
            i_left = i_left + 1
            i_right = i_right - 1
        return self.raw_array

def quick_sort(self, array=None):
        """
        # using the first element to be the pivot.
        # using the left and right pointer to compare the element.
        # opt: using the random element to be the pivot.
        """
        if array is None:
            array = self.raw_array
        n = len(array)
        if n < 2:
            return array
        # using the first element to be the pivot.
        pivot = array[0]
        left = list()
        right = list()
        for i in range(1, n):
            if array[i] < pivot:
                left.append(array[i])
            else:
                right.append(array[i])
        # using recursion to sort the left and right array.
        left = self.quick_sort(array=left)
        right = self.quick_sort(array=right)
        return left + [pivot] + right

def quick_sort_opt(self, array=None):
        """
        # using the random element to be the pivot.
        # using the left and right pointer to compare the element.
        """
        if array is None:
            array = self.raw_array
        n = len(array)
        if n < 2:
            return array
        # using the random element to be the pivot.
        pivot = array[random.randint(0, n - 1)]
        left = list()
        right = list()
        for i in range(0, n):
            if array[i] < pivot:
                left.append(array[i])
            else:
                right.append(array[i])
        # using recursion to sort the left and right array.
        left = self.quick_sort(array=left)
        right = self.quick_sort(array=right)
        return left + right