def bubble_sort(alist):
    for j in range(len(alist)-1,0,-1):
        # j表示每次遍历需要比较的次数，是逐渐减小的
        for i in range(j):
            if alist[i] > alist[i+1]:
                alist[i], alist[i+1] = alist[i+1], alist[i]

li = [54,26,93,17,77,31,44,55,20]
bubble_sort(li)
print(li)

def selection_sort(alist):
    n = len(alist)
    # 需要进行n-1次选择操作
    for i in range(n-1):
        # 记录最小位置
        min_index = i
        # 从i+1位置到末尾选择出最小数据
        for j in range(i+1, n):
            if alist[j] < alist[min_index]:
                min_index = j
        alist[i], alist[min_index] = alist[min_index], alist[i]

alist = [54,226,93,17,77,31,44,55,20]
selection_sort(alist)
print(alist)

def insert_sort(alist):
    # 从第二个位置，即下标为1的元素开始向前插入
    for i in range(1, len(alist)):
        # 从第i个元素开始向前比较，如果小于前一个元素，交换位置
        for j in range(i, 0, -1):#j = i [ i,i-1,i-2,i-3.....1]
            if alist[j] < alist[j-1]:
                alist[j], alist[j-1] = alist[j-1], alist[j]

def insert_sort2(alist):
    '插入排序代码另一种写法'
    n = len(alist)
    # 从右边的无序序列中取出多少个元素执行这样的过程
    for i in range(1, n):
        # i = [1, 2, 3, n-1]
        #j代表内层循环起始值
        j = i   #[j ,j-1,j-2,j-3.....1]
        #执行从右边的无序序列中取出的第一个元素，即i位置的元素，然后将其插入到前面的正确位置中
        while j > 0:
            if alist[j] < alist[j-1]:
                alist[j], alist[j-1] = alist[j-1], alist[j]
                j -= 1
            else: break# 本步对算法进行了优化
# 最优时间复杂度：O(n) （升序排列，序列已经处于升序状态）
# 最坏时间复杂度：O(n2)

if __name__=='__main__':
    alist = [54, 26, 93, 17, 77, 31, 44, 55, 20]
    insert_sort(alist)
    print(alist)
    alist = [54, 26, 93, 17, 77, 31, 44, 55, 20]
    insert_sort2(alist)
    print(alist)

def shell_sort1(alist):
    n = len(alist)
    # 初始步长
    gap = n // 2
    while gap > 0:#gap>=1,即gap变化到0之前，插入算法的次数
        # 按步长进行插入排序
        for i in range(gap, n):
            j = i
            # 插入排序
            while j>=gap and alist[j-gap] > alist[j]:
                alist[j-gap], alist[j] = alist[j], alist[j-gap]
                j -= gap
        # 得到新的步长
        gap = gap // 2

def shell_sort2(alist):
    '希尔排序的另一种书写方式'
    n = len(alist)
    # 初始步长
    gap = n // 2#gap值自己可调，从数学角度找到最好的gap，n//2并不是最好的，看自己计算选择出最好的步长
    # gap变化到0之前，插入算法的次数
    while gap > 0:
        #插入算法，与普通的插入算法的区别就是gap步长
        for j in range(gap, n):#以下几步和插入排序较为相似
            #j = [gap, gap+1, gap+2, gap+3,....,n-1]
            i = j
            while i>0:
                if alist[i] < alist[i-gap]:
                    alist[i-gap], alist[i] = alist[i], alist[i-gap]
                    i -= gap
                else:
                    break
        # 得缩短gap步长
        gap = gap // 2

alist = [54,26,93,17,77,31,44,55,20]
shell_sort1(alist)
print(alist)
shell_sort2(alist)
print(alist)

def quick_sort(alist, start, end):
    """快速排序"""

    # 递归的退出条件
    if start >= end:
        return

    # 设定起始元素为要寻找位置的基准元素
    mid = alist[start]

    # low为序列左边的由左向右移动的游标
    low = start

    # high为序列右边的由右向左移动的游标
    high = end

    while low < high:
        # 如果low与high未重合，high指向的元素不比基准元素小，则high向左移动
        while low < high and alist[high] >= mid:
            high -= 1
        # 将high指向的元素放到low的位置上
        alist[low] = alist[high]

        # 如果low与high未重合，low指向的元素比基准元素小，则low向右移动
        while low < high and alist[low] < mid:
            low += 1
        # 将low指向的元素放到high的位置上
        alist[high] = alist[low]

    # 退出循环后，low与high重合，此时所指位置为基准元素的正确位置
    # 将基准元素放到该位置
    alist[low] = mid

    # 对基准元素左边的子序列进行快速排序
    quick_sort(alist, start, low-1)

    # 对基准元素右边的子序列进行快速排序
    quick_sort(alist, low+1, end)


alist = [54,26,93,17,77,31,44,55,20]
quick_sort(alist,0,len(alist)-1)
print(alist)

def merge_sort(alist):
    if len(alist) <= 1:
        return alist
    # 二分分解
    num = len(alist)//2
    left = merge_sort(alist[:num])
    right = merge_sort(alist[num:])
    # 合并
    return merge(left,right)

def merge(left, right):
    '''合并操作，将两个有序数组left[]和right[]合并成一个大的有序数组'''
    #left与right的下标指针
    l, r = 0, 0
    result = []
    while l<len(left) and r<len(right):
        if left[l] < right[r]:
            result.append(left[l])
            l += 1
        else:
            result.append(right[r])
            r += 1
    result += left[l:]
    result += right[r:]
    return result

alist = [54,26,93,17,77,31,44,55,20]
sorted_alist = mergeSort(alist)
print(sorted_alist)

#沿左,右子节点较大者依次往下调整
def MAX_Heapify( array, HeapSize,root ):#在堆中做结构调整使得父节点的值大于子节点
    left = 2*root + 1
    right = left + 1
    larger = root
    if left < HeapSize and array[larger] < array[left]:
        larger = left
    if right < HeapSize and array[larger] <array[right]:
        larger = right
    if larger != root:#如果做了堆调整则larger的值等于左节点或者右节点的，这个时候做对调值操作
        array[larger],array[root] = array[root],array[larger]
        MAX_Heapify(array,HeapSize,larger)
 
#创建堆
def Build_MAX_Heap( array ):#构造一个堆，将堆中所有数据重新排序
    HeapSize = len( array )#将堆的长度单独拿出来方便
    for i in range( HeapSize // 2 - 1, -1, -1 ):#从后往前出数
        MAX_Heapify( array,HeapSize, i)
 
#大顶堆排序
def HeapSort( array ):#将根节点取出与最后一位做对调，对前面len-1个节点继续进行对调整过程。
    Build_MAX_Heap( array )
    #交换堆顶与最后一个结点,再调整堆
    for i in range(len(array) - 1, -1, -1 ):
        array[0], array[i] = array[i], array[0]
        MAX_Heapify(array, i, 0)
    return array
 
a = [ -3, 1, 3, 0, 9, -9, 11, 82, 7 ]
print(HeapSort(a))

#方式1
alist=[1,3,5,7,9,2,4,6,8,10]
x=int(input('请输入要查找的整数：'))
for i in alist:
    if i==x:
        print('找到了，整数%d在列表中。'%x)
#方式2
alist=[1,3,5,7,9,2,4,6,8,10]
x=int(input('请输入要查找的整数：'))
for i in range(len(alist)):
    if alist[i]==x:
        print('找打了，第%d个数是%d。'%(i+1,x))

def binary_search(alist, item):
    first = 0
    last = len(alist) - 1
    while first <= last:
        midpoint = (first + last) // 2
        if alist[midpoint] == item:
            return True
        elif item < alist[midpoint]:
            last = midpoint - 1
        else:
            first = midpoint + 1
    return False

testlist = [0, 1, 2, 8, 13, 17, 19, 32, 42, ]
print(binary_search(testlist, 3))
print(binary_search(testlist, 13))

def binary_search(alist, item):
    if len(alist) == 0:
        return False

    midpoint = len(alist) // 2
    if alist[midpoint] == item:
        return True
    elif item < alist[midpoint]:
        return binary_search(alist[:midpoint], item)
    else:
        return binary_search(alist[midpoint + 1:], item)


testlist = [0, 1, 2, 8, 13, 17, 19, 32, 42, ]
print(binary_search(testlist, 3))
print(binary_search(testlist, 13))

# 忽略了对数据类型，元素溢出等问题的判断。
 
class HashTable:
  def __init__(self, size):
    self.elem = [None for i in range(size)] # 使用list数据结构作为哈希表元素保存方法
    self.count = size # 最大表长
 
  def hash(self, key):
    return key % self.count # 散列函数采用除留余数法
 
  def insert_hash(self, key):
    """插入关键字到哈希表内"""
    address = self.hash(key) # 求散列地址
    while self.elem[address]: # 当前位置已经有数据了，发生冲突。
      address = (address+1) % self.count # 线性探测下一地址是否可用
    self.elem[address] = key # 没有冲突则直接保存。
 
  def search_hash(self, key):
    """查找关键字，返回布尔值"""
    star = address = self.hash(key)
    while self.elem[address] != key:
      address = (address + 1) % self.count
      if not self.elem[address] or address == star: # 说明没找到或者循环到了开始的位置
        return False
    return True
 
 
if __name__ == '__main__':
  list_a = [12, 67, 56, 16, 25, 37, 22, 29, 15, 47, 48, 34]
  hash_table = HashTable(12)
  for i in list_a:
    hash_table.insert_hash(i)
 
  for i in hash_table.elem:
    if i:
      print((i, hash_table.elem.index(i)), end=" ")
  print("
")
 
  print(hash_table.search_hash(15))
  print(hash_table.search_hash(33))