冒泡排序、选择排序、插入排序、快速排序、二叉树

冒泡排序（Bubble Sort）

冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的排序算法。

它重复地走访过要排序的数列，一次笔记两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行知道没有在需要的交换，也就是说该数列已经排序完成。

这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端，故名。

data_set = [ 9,1,22,31,45,3,6,2,11 ]
 
loop_count = 0
for j in range(len(data_set)):
    for i in range(len(data_set) - j- 1): # -1 是因为每次比对的都 是i 与i +1,不减1的话,最后一次对比会超出list 获取范围,-j是因为,每一次大loop就代表排序好了一个最大值,
　　　　　　　　　　　　　　　　　　　　　　　　　　放在了列表最后面,下次loop就不用再运算已经排序好了的值 了
        if data_set[i] > data_set[i+1]: #switch
            tmp = data_set[i]
            data_set[i] = data_set[i+1]
            data_set[i+1] = tmp
        loop_count +=1
    print(data_set)
print(data_set)
print("loop times", loop_count)

　　

 

选择排序

The algorithm works by selecting the smallest unsorted item and then swapping it with the item in the next position to be filled.

The selection sort works as follows: you look through the entire array for the smallest element, once you find it you swap it (the smallest element) with the first element of the array. Then you look for the smallest element in the remaining array (an array without the first element) and swap it with the second element. Then you look for the smallest element in the remaining array (an array without first and second elements) and swap it with the third element, and so on. Here is an example,The worst-case runtime complexity is O(n²).

data_set = [ 9,1,22,31,45,3,6,2,11 ]
 
smallest_num_index = 0 #初始列表最小值,默认为第一个
 
loop_count = 0
for j in range(len(data_set)):
    for i in range(j,len(data_set)):
        if data_set[i] < data_set[smallest_num_index]: #当前值 比之前选出来的最小值 还要小,那就把它换成最小值
            smallest_num_index = i
        loop_count +=1
    else:
        print("smallest num is ",data_set[smallest_num_index])
        tmp = data_set[smallest_num_index]
        data_set[smallest_num_index] =  data_set[j]
        data_set[j] = tmp
 
    print(data_set)
    print("loop times", loop_count)

方法二：

思路：利用索引

 插入排序

插入排序(Insertion Sort)的基本思想是：将列表分为2部分，左边为排序好的部分，右边为未排序的部分，循环整个列表，每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子序列中的适当位置，直到全部记录插入完成为止。

插入排序非常类似于整扑克牌。

在开始摸牌时，左手是空的，牌面朝下放在桌上。接着，一次从桌上摸起一张牌，并将它插入到左手一把牌中的正确位置上。为了找到这张牌的正确位置，要将它与手中已有的牌从右到左地进行比较。无论什么时候，左手中的牌都是排好序的。

也许你没有意识到，但其实你的思考过程是这样的：现在抓到一张7，把它和手里的牌从右到左依次比较，7比10小，应该再往左插，7比5大，好，就插这里。为什么比较了10和5就可以确定7的位置？为什么不用再比较左边的4和2呢？因为这里有一个重要的前提：手里的牌已经是排好序的。现在我插了7之后，手里的牌仍然是排好序的，下次再抓到的牌还可以用这个方法插入。编程对一个数组进行插入排序也是同样道理，但和插入扑克牌有一点不同，不可能在两个相邻的存储单元之间再插入一个单元，因此要将插入点之后的数据依次往后移动一个单元。

li = [3,34,5,34,23,45,56,3]

for i in range(len(li)):

    while i >0 and li[i] < li[i-1]:

        # tmp = li[i]
        # li[i] = li[i-1]
        # li[i-1] = tmp
        li[i],li[i-1] = li[i-1],li[i]

        i -= 1
        print(li)

# print(li)

　　

[3, 5, 34, 34, 23, 45, 56, 3]
[3, 5, 34, 23, 34, 45, 56, 3]
[3, 5, 23, 34, 34, 45, 56, 3]
[3, 5, 23, 34, 34, 45, 3, 56]
[3, 5, 23, 34, 34, 3, 45, 56]
[3, 5, 23, 34, 3, 34, 45, 56]
[3, 5, 23, 3, 34, 34, 45, 56]
[3, 5, 3, 23, 34, 34, 45, 56]
[3, 3, 5, 23, 34, 34, 45, 56]

快速排序（quick sort）

设要排序的数组是A[0]……A[N-1]，首先任意选取一个数据（通常选用数组的第一个数）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序。值得注意的是，快速排序不是一种稳定的排序算法，也就是说，多个相同的值的相对位置也许会在算法结束时产生变动　　

注：在待排序的文件中，若存在多个关键字相同的记录，经过排序后这些具有相同关键字的记录之间的相对次序保持不变，该排序方法是稳定的；若具有相同关键字的记录之间的相对次序发生改变，则称这种排序方法是不稳定的。
要注意的是，排序算法的稳定性是针对所有输入实例而言的。即在所有可能的输入实例中，只要有一个实例使得算法不满足稳定性要求，则该排序算法就是不稳定的。 

排序演示

其实就是分两组，左边和右边

示例

假设用户输入了如下数组：

下标	0	1	2	3	4	5
数据	6	2	7	3	8	9

创建变量i=0（指向第一个数据）, j=5(指向最后一个数据), k=6(赋值为第一个数据的值)。

我们要把所有比k小的数移动到k的左面，所以我们可以开始寻找比6小的数，从j开始，从右往左找，不断递减变量j的值，我们找到第一个下标3的数据比6小，于是把数据3移到下标0的位置，把下标0的数据6移到下标3，完成第一次比较：

下标	0	1	2	3	4	5
数据	3	2	7	6	8	9

i=0 j=3 k=6

接着，开始第二次比较，这次要变成找比k大的了，而且要从前往后找了。递加变量i，发现下标2的数据是第一个比k大的，于是用下标2的数据7和j指向的下标3的数据的6做交换，数据状态变成下表：

下标	0	1	2	3	4	5
数据	3	2	6	7	8	9

i=2 j=3 k=6

称上面两次比较为一个循环。

接着，再递减变量j，不断重复进行上面的循环比较。

在本例中，我们进行一次循环，就发现i和j“碰头”了：他们都指向了下标2。于是，第一遍比较结束。得到结果如下，凡是k(=6)左边的数都比它小，凡是k右边的数都比它大：

下标	0	1	2	3	4	5
数据	3	2	6	7	8	9

如果i和j没有碰头的话，就递加i找大的，还没有，就再递减j找小的，如此反复，不断循环。注意判断和寻找是同时进行的。

然后，对k两边的数据，再分组分别进行上述的过程，直到不能再分组为止。

注意：第一遍快速排序不会直接得到最终结果，只会把比k大和比k小的数分到k的两边。为了得到最后结果，需要再次对下标2两边的数组分别执行此步骤，然后再分解数组，直到数组不能再分解为止（只有一个数据），才能得到正确结果。

 

 

#_*_coding:utf-8_*_
 
 
def quick_sort(array,left,right):
    '''
 
    :param array:
    :param left: 列表的第一个索引
    :param right: 列表最后一个元素的索引
    :return:
    '''
    if left >=right:
        return
    low = left
    high = right
    key = array[low] #第一个值
 
    while low < high:#只要左右未遇见
        while low < high and array[high] > key: #找到列表右边比key大的值 为止
            high -= 1
        #此时直接 把key(array[low]) 跟 比它大的array[high]进行交换
        array[low] = array[high]
        array[high] = key
 
 
        while low < high and array[low] <= key : #找到key左边比key大的值，这里为何是<=而不是<呢？你要思考。。。
            low += 1
            #array[low] =
        #找到了左边比k大的值 ,把array[high](此时应该刚存成了key) 跟这个比key大的array[low]进行调换
        array[high] = array[low]
        array[low] = key
 
    quick_sort(array,left,low-1) #最后用同样的方式对分出来的左边的小组进行同上的做法
    quick_sort(array,low+1, right)#用同样的方式对分出来的右边的小组进行同上的做法
 
 
 
if __name__ == '__main__':
 
    array = [96,14,10,9,6,99,16,5,1,3,2,4,1,13,26,18,2,45,34,23,1,7,3,22,19,2]
    #array = [8,4,1, 14, 6, 2, 3, 9,5, 13, 7,1, 8,10, 12]
    print("before sort:", array)
    quick_sort(array,0,len(array)-1)
 
    print("-------final -------")
    print(array)

　

二叉树

class TreeNode(object):

    def __init__(self, left=0, right=0, data=0):
        self.left = left
        self.right = right
        self.data = data


class BTree(object):

    def __init__(self, root=0):
        self.root = root

    def is_empty(self):
        if self.root is 0:
            return True
        else:
            return False

    def preorder(self, treenode):
        '前序（pre-order，NLR）遍历'
        if treenode is 0:
            return
        print(treenode.data)
        self.preorder(treenode.left)
        self.preorder(treenode.right)

    def inorder(self, treenode):
        '中序（in-order，LNR'
        if treenode is 0:
            return
        self.inorder(treenode.left)
        print(treenode.data)
        self.inorder(treenode.right)

    def postorder(self, treenode):
        '后序（post-order，LRN）遍历'
        if treenode is 0:
            return
        self.postorder(treenode.left)
        self.postorder(treenode.right)
        print(treenode.data)


node1 = TreeNode(data=1)
node2 = TreeNode(node1, 0, 2)
node3 = TreeNode(data=3)
node4 = TreeNode(data=4)
node5 = TreeNode(node3, node4, 5)
node6 = TreeNode(node2, node5, 6)
node7 = TreeNode(node6, 0, 7)
node8 = TreeNode(data=8)
root = TreeNode(node7, node8, 'root')

bt = BTree(root)
#生成的二叉树

# ------------------------
#          root
#       7        8
#     6
#   2   5
# 1    3 4
#
# -------------------------

'''
print '前序（pre-order，NLR）遍历 ：
'
bt.preorder(bt.root)

print '中序（in-order，LNR) 遍历 ：
'
bt.inorder(bt.root)

print '后序（post-order，LRN）遍历 ：
'
bt.postorder(bt.root)

求二叉树的和与最大值

"""
求二叉树最大值与和
"""

class TreeNode(object):

    def __init__(self, left=0, right=0, data=0):
        self.left = left
        self.right = right
        self.data = data


class BTree(object):

    def __init__(self, root=0):
        self.root = root
        self.li = []
        self.sum = 0
        self.big = 0

    def is_empty(self):
        if self.root is 0:
            return True
        else:
            return False


    def postorder(self, treenode):
        '后序（post-order，LRN）遍历'
        if treenode is 0:
            return
        self.postorder(treenode.left)
        self.postorder(treenode.right)
        if treenode.data > self.big:
            self.big = treenode.data
        self.li.append(treenode.data)
        self.sum += treenode.data


node1 = TreeNode(data=1)
node2 = TreeNode(node1, 0, 2)
node3 = TreeNode(data=3)
node4 = TreeNode(data=4)
node5 = TreeNode(node3, node4, 5)
node6 = TreeNode(node2, node5, 6)
node7 = TreeNode(node6, 0, 7)
node8 = TreeNode(data=8)
root = TreeNode(node7, node8, 2)

if __name__ == '__main__':

    bt = BTree(root)
    bt.postorder(bt.root)
    print("最大值为：", bt.big)
    print("和为：", bt.sum)