# 返回 x 在 arr 中的索引，如果不存在返回 -1
def binarySearch (arr, l, r, x):
    # 基本判斷
    if r >= l:
        mid = int(l + (r - l)/2)
        # 元素整好的中間位置
        if arr[mid] == x:
            return mid
        # 元素小于中間位置的元素，只需要再比較左邊的元素
        elif arr[mid] > x:
            return binarySearch(arr, l, mid-1, x)
        # 元素大于中間位置的元素，只需要再比較右邊的元素
        else:
            return binarySearch(arr, mid+1, r, x)
    else:
        # 不存在
        return -1
 
# 測(cè)試數(shù)組
arr = [ 2, 3, 4, 10, 40]
x = int(input('請(qǐng)輸入元素：'))
# 函數(shù)調(diào)用
result = binarySearch(arr, 0, len(arr)-1, x)
 
if result != -1:
    print("元素在數(shù)組中的索引為 %d" % result)
else:
    print("元素不在數(shù)組中")

def search(arr, n, x):
    for i in range (0, n):
        if (arr[i] == x):
            return i
    return -1
 
# 在數(shù)組 arr 中查找字符 D
arr = [ 'A', 'B', 'C', 'D', 'E' ]
x = input("請(qǐng)輸入要查找的元素：")
n = len(arr)
result = search(arr, n, x)
if(result == -1):
    print("元素不在數(shù)組中")
else:
    print("元素在數(shù)組中的索引為", result)

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 = [12, 11, 13, 5, 6, 7, 9, 9, 17]
insertionSort(arr)
print("排序后的數(shù)組:")
print(arr)

list1 = [12, 11, 13, 5, 6, 7, 9, 9, 17]
for i in range(len(list1)-1, 0, -1):
    for j in range(0, i):
        if list1[i] < list1[j]:
            list1[i], list1[j] = list1[j], list1[i]
print(list1)

def partition(arr, low, high):
    i = (low-1)         # 最小元素索引
    pivot = arr[high]
 
    for j in range(low, high):
        # 當(dāng)前元素小于或等于 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)
 
# arr[] --> 排序數(shù)組
# low  --> 起始索引
# high  --> 結(jié)束索引
 
# 快速排序函數(shù)
def quickSort(arr, low, high):
    if low < high:
        pi = partition(arr, low, high)
        quickSort(arr, low, pi-1)
        quickSort(arr, pi+1, high)
    return arr
 
arr = [10, 7, 8, 9, 1, 5]
n = len(arr)
 
print("排序后的數(shù)組:")
print(quickSort(arr, 0, n-1))

A = [64, 25, 12, 22, 11]
for i in range(len(A)): 
    min_idx = i
    for j in range(i+1, len(A)):
        if A[min_idx] > A[j]:
            min_idx = j
 
    A[i], A[min_idx] = A[min_idx], A[i]
 
print("排序后的數(shù)組：")
print(A)

def bubbleSort(arr):
    n = len(arr)
    # 遍歷所有數(shù)組元素
    for i in range(n):
        # Last i elements are already in place
        for j in range(0, n-i-1):
 
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr
 
arr = [64, 34, 25, 12, 22, 11, 90]
 
print("排序后的數(shù)組:")
print(bubbleSort(arr))

def merge(arr, l, m, r):
    n1 = m - l + 1
    n2 = r - m
 
    # 創(chuàng)建臨時(shí)數(shù)組
    L = [0] * (n1)
    R = [0] * (n2)
 
    # 拷貝數(shù)據(jù)到臨時(shí)數(shù)組 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]
 
    # 歸并臨時(shí)數(shù)組到 arr[l..r]
    i = 0     # 初始化第一個(gè)子數(shù)組的索引
    j = 0     # 初始化第二個(gè)子數(shù)組的索引
    k = l     # 初始?xì)w并子數(shù)組的索引
 
    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)
    return arr
 
print ("給定的數(shù)組")
arr = [12, 11, 13, 5, 6, 7, 13]
print(arr)
n = len(arr)
mergeSort(arr, 0, n-1)
print("排序后的數(shù)組")
print(arr)

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]  # 交換
def heapSort(arr):
    n = len(arr)
    # Build a maxheap.
    for i in range(n, -1, -1):
        heapify(arr, n, i)
    # 一個(gè)個(gè)交換元素
    for i in range(n-1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]   # 交換
        heapify(arr, i, 0)
    return arr
arr = [12, 11, 13, 5, 6, 7, 13, 18]
heapSort(arr)
print("排序后的數(shù)組")
print(heapSort(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 = "wwwnowcodercom"
ans = countSort(arr)
print("字符數(shù)組排序 %s" %("".join(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)
    return arr
 
arr = [12, 34, 54, 2, 3, 2, 5]
 
print("排序前:")
print(arr)
print("排序后:")
print(shellSort(arr))