# 冒泡排序 ： 把最大的值移到未尾，操作值
#冒泡排序（Bubble Sort）也是一种简单直观的排序算法。
#它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。
#走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
#这个算法的名字由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端。


def mao_pao(num_list):
    num_len = len(num_list)
    a = num_list
    # 控制循环的次数
    for j in range(num_len):
        # 添加标记位 用于优化(如果没有交换表示有序,结束循环)
        sign = False
        # 内循环每次将最大值放在最右边
        for i in range(num_len - 1 - j):
            if a[i] > a[i+1]:
                a[i], a[i+1] = a[i+1], a[i]
                sign = True
                # 如果没有交换说明列表已经有序，结束循环
        if not sign:
          break


arr = [97, 23, 11, 44, 22, 66, 15,1993]
mao_pao(arr)
print(arr)


#选择排序法:(把坐标直接交换) 一遍过后锁定，先确定最小值的坐标记住后并调换到最左边，操作坐标
#选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理如下。
# 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，
# 然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
# 以此类推，直到所有元素均排序完毕。
def xz_pc(arr):
  for i in range(len(arr)): 
    min_idx = i 
    for j in range(i+1, len(arr)): 
        if arr[min_idx] > arr[j]: 
            min_idx = j 
                
    arr[i], arr[min_idx] = arr[min_idx], arr[i] 

arr = [97, 23, 11, 44, 22, 66, 15,1993]
xz_pc(arr)
print(arr)

#快速排序法

#挑选基准值：从数列中挑出一个元素，称为"基准"（pivot）;
#分割：重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（与基准值相等的数可以到任何一边）。
#在这个分割结束之后，对基准值的排序就已经完成;
#递归排序子序列：递归地将小于基准值元素的子序列和大于基准值元素的子序列排序。
#递归到最底部的判断条件是数列的大小是零或一，此时该数列显然已经有序。

#选取基准值有数种具体方法，此选取方法对排序的时间性能有决定性影响。

def partition(arr,low,high): 
    i = ( low-1 )         # 最小元素索引 标记点
    pivot = arr[high]     # 基准值
  
    for j in range(low , high): #从0到数组内数据循环一遍
  
        # 当前元素小于或等于 pivot 
        if   arr[j] <= pivot:  #小于等于基准值就标记后，进行互换操作
          
            i = i+1 
            arr[i],arr[j] = arr[j],arr[i] 
  
    arr[i+1],arr[high] = arr[high],arr[i+1] 
    return ( i+1 ) 
# 快速排序函数
def quickSort(arr,low,high): 
    if low < high: 
  
        pi = partition(arr,low,high)  #返回标记点
  
        quickSort(arr, low, pi-1)  #循环递归 以标记点左边
        quickSort(arr, pi+1, high) #循环递归 以标记点右边

arr = [97, 23, 11, 44, 22, 66, 15,1993]
quickSort(arr,0,7)
print(arr)     

#插入排序
#插入排序（英语：Insertion Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入
def insertionSort(arr): 
    for i in range(1, len(arr)): 
        key = arr[i] 
        j = i-1
        while j >=0 and key < arr[j] : 
                arr[j+1] = arr[j] 
                j -= 1
        arr[j+1] = key 

arr = [97, 23, 11, 44, 22, 66, 15,1993]
insertionSort(arr)
print(arr) 

#归并排序
#归并排序（英语：Merge sort，或mergesort），是创建在归并操作上的一种有效的排序算法。
#该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

#分治法:
#分割：递归地把当前序列平均分割成两半。
#集成：在保持元素顺序的同时将上一步得到的子序列集成到一起（归并）。
def merge(arr, l, m, r): 
    n1 = m - l + 1
    n2 = r- m 
    # 创建临时数组
    L = [0] * (n1)
    R = [0] * (n2)
    # 拷贝数据到临时数组 arrays L[] 和 R[] 
    for i in range(0 , n1): 
        L[i] = arr[l + i] 
  
    for j in range(0 , n2): 
        R[j] = arr[m + 1 + j] 
  
    # 归并临时数组到 arr[l..r] 
    i = 0     # 初始化第一个子数组的索引
    j = 0     # 初始化第二个子数组的索引
    k = l     # 初始归并子数组的索引
  
    while i < n1 and j < n2 : 
        if L[i] <= R[j]: 
            arr[k] = L[i] 
            i += 1
        else: 
            arr[k] = R[j] 
            j += 1
        k += 1
  
    # 拷贝 L[] 的保留元素
    while i < n1: 
        arr[k] = L[i] 
        i += 1
        k += 1
  
    # 拷贝 R[] 的保留元素
    while j < n2: 
        arr[k] = R[j] 
        j += 1
        k += 1
  
def mergeSort(arr,l,r): 
    if l < r:    
        m = int((l+(r-1))/2)
  
        mergeSort(arr, l, m) 
        mergeSort(arr, m+1, r) 
        merge(arr, l, m, r) 

arr = [97, 23, 11, 44, 22, 66, 15,1993]
mergeSort(arr,0,len(arr)-1)
print(arr)


#堆排序
#堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，
#并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。
def heapify(arr, n, i): 
    largest = i  
    l = 2 * i + 1     # left = 2*i + 1 
    r = 2 * i + 2     # right = 2*i + 2 
  
    if l < n and arr[i] < arr[l]: 
        largest = l 
  
    if r < n and arr[largest] < arr[r]: 
        largest = r 
  
    if largest != i: 
        arr[i],arr[largest] = arr[largest],arr[i]  # 交换
  
        heapify(arr, n, largest) 
  
def heapSort(arr): 
    n = len(arr) 
  
    # Build a maxheap. 
    for i in range(n, -1, -1): 
        heapify(arr, n, i) 
  
    # 一个个交换元素
    for i in range(n-1, 0, -1): 
        arr[i], arr[0] = arr[0], arr[i]   # 交换
        heapify(arr, i, 0) 
arr = [97, 23, 11, 44, 22, 66, 15,1993]
heapSort(arr)
print(arr)

#计数排序
#计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。
#作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。
def countSort(arr): 
    output = [0 for i in range(256)] 
    count = [0 for i in range(256)] 
    ans = ["" for _ in arr] 
    for i in arr: 
        count[ord(i)] += 1
    for i in range(256): 
        count[i] += count[i-1] 
    for i in range(len(arr)): 
        output[count[ord(arr[i])]-1] = arr[i] 
        count[ord(arr[i])] -= 1
    for i in range(len(arr)): 
        ans[i] = output[i] 
    return ans

arr = "wwwrunoobcom"
ans = countSort(arr) 
print(ans)

#希尔排序
#希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。
#希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录"基本有序"时，
#再对全体记录进行依次直接插入排序。
def shellSort(arr): 
    n = len(arr)
    gap = int(n/2)
    while gap > 0: 
        for i in range(gap,n): 
            temp = arr[i] 
            j = i 
            while  j >= gap and arr[j-gap] >temp: 
                arr[j] = arr[j-gap] 
                j -= gap 
            arr[j] = temp 
        gap = int(gap/2)

arr = [97, 23, 11, 44, 22, 66, 15,1993]
shellSort(arr)
print(arr)

#拓扑排序
#对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边(u,v)∈E(G)，则u在线性序列中出现在v之前。
#通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。
#简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。
#在图论中，由一个有向无环图的顶点组成的序列，当且仅当满足下列条件时，称为该图的一个拓扑排序（英语：Topological sorting）：
#每个顶点出现且只出现一次；
#若A在序列中排在B的前面，则在图中不存在从B到A的路径。



#线性查找
#线性查找指按一定的顺序检查数组中每一个元素，直到找到所要寻找的特定值为止。
def search(arr, n, x): 
  
    for i in range (0, n): 
        if (arr[i] == x): 
            return i 
    return -1 
arr = [97, 23, 11, 44, 22, 66, 15,1993]
print(search(arr,7,44))

# 二分法找下标
def binary_search(arr, target):
    """
    二分查找算法
    :param arr: 待查找的有序数组
    :param target: 目标值
    :return: 目标值在数组中的索引，若不存在则返回-1
    """
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1
# 递归二分法找下标


def binary_search_dg(arr, left, right, target):
    mid = (left + right) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search_dg(arr, mid+1, right, target)
    else:
        return binary_search_dg(arr, left, mid-1, target)


index = binary_search([9, 3, 4, 2, 22, 44], 4)
print(index)
index = binary_search_dg([9, 3, 4, 2, 22, 44], 0, 5, 22)
print(index)