# 返回 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

# 测试数组

arr = [ 2, 3, 4, 10, 40 ]

x = 10

# 函数调用

result = binarySearch(arr, 0, len(arr)-1, x) 

if result != -1:

    print ("元素在数组中的索引为 %d" % result )

else:

    print ("元素不在数组中")

def search(arr, n, x): 

    for i in range (0, n):

        if (arr[i] == x):

            return i;

    return -1; 

# 在数组 arr 中查找字符 D

arr = [ 'A', 'B', 'C', 'D', 'E' ];

x = 'D';

n = len(arr);

result = search(arr, n, x)

if(result == -1):

    print("元素不在数组中")

else:

    print("元素在数组中的索引为", 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]

insertionSort(arr)

print ("排序后的数组:")

for i in range(len(arr)):

    print ("%d" %arr[i])

def partition(arr,low,high):

    i = ( low-1 )         # 最小元素索引

    pivot = arr[high]

    for j in range(low , high): 

        # 当前元素小于或等于 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[] --> 排序数组

# low  --> 起始索引

# high  --> 结束索引

# 快速排序函数

def quickSort(arr,low,high):

    if low < high: 

        pi = partition(arr,low,high) 

        quickSort(arr, low, pi-1)

        quickSort(arr, pi+1, high) 

arr = [10, 7, 8, 9, 1, 5]

n = len(arr)

quickSort(arr,0,n-1)

print ("排序后的数组:")

for i in range(n):

    print ("%d" %arr[i]),

import sys

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 ("排序后的数组：")

for i in range(len(A)):

    print("%d" %A[i]),

def bubbleSort(arr):

    n = len(arr)

    # 遍历所有数组元素

    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]

arr = [64, 34, 25, 12, 22, 11, 90]

bubbleSort(arr)

print ("排序后的数组:")

for i in range(len(arr)):

    print ("%d" %arr[i]),

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 = [12, 11, 13, 5, 6, 7]

n = len(arr)

print ("给定的数组")

for i in range(n):

    print ("%d" %arr[i]), 

mergeSort(arr,0,n-1)

print ("\n\n排序后的数组")

for i in range(n):

    print ("%d" %arr[i]),

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 = [ 12, 11, 13, 5, 6, 7]

heapSort(arr)

n = len(arr)

print ("排序后")

for i in range(n):

    print ("%d" %arr[i]),

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 ( "字符数组排序 %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)

arr = [ 12, 34, 54, 2, 3] 

n = len(arr)

print ("排序前:")

for i in range(n):

    print(arr[i]), 

shellSort(arr) 

print ("\n排序后:")

for i in range(n):

    print(arr[i]),

from collections import defaultdict 

class Graph:

    def __init__(self,vertices):

        self.graph = defaultdict(list)

        self.V = vertices

    def addEdge(self,u,v):

        self.graph[u].append(v) 

    def topologicalSortUtil(self,v,visited,stack): 

        visited[v] = True

        for i in self.graph[v]:

            if visited[i] == False:

                self.topologicalSortUtil(i,visited,stack) 

        stack.insert(0,v) 

    def topologicalSort(self):

        visited = [False]*self.V

        stack =[] 

        for i in range(self.V):

            if visited[i] == False:

                self.topologicalSortUtil(i,visited,stack) 

        print (stack) 

g= Graph(6)

g.addEdge(5, 2);

g.addEdge(5, 0);

g.addEdge(4, 0);

g.addEdge(4, 1);

g.addEdge(2, 3);

g.addEdge(3, 1); 

print ("拓扑排序结果：")

g.topologicalSort()