#无序表查找
def sequentialSearch(alist , item):
    pos = 0
    found =False
    while pos < len(alist) and not  found :
        if alist[pos] == item:
            found = True
        else:
            pos = pos+1
    return found

#有序表查找
def orderSequentialSearch(alist,item):
    pos =0
    found =False
    stop = False
    while pos < len(alist) and not found and not stop:
        if alist[pos] ==item :
            found =True
        else:
            if alist[pos] > item :
                stop =True
            else:
                pos =pos+1
    return found

#有序表二分查找（循环）
def binarySearch_1(alist,item):
    first =0
    last = len(alist) -1
    found = False
    while first <= last and not  found :
        midpoint = (first +last)//2
        if alist[midpoint] == item :
            found = True
        else:
            if item < alist[midpoint]:
                last = midpoint - 1
            else:
                first = midpoint + 1
    return found

#有序表二分查找（递归）
def  binarySearch_2(alist ,item):
    if len(alist) == 0:
        return False
    else:
        midpoint = len(alist)//2
        if  alist[midpoint] == item:
            return True
        else:
            if item < alist[midpoint]:
                return  binarySearch_2(alist[:midpoint],item)
            else:
                return binarySearch_2(alist[midpoint+1:],item)



#冒泡排序
def bubbleSort(alist):
    for passnum in range(len(alist) - 1, 0 , -1 ):
        for i in range(passnum):
            if alist[i] > alist[i + 1]:
                alist[i],alist[i + 1] = alist[i + 1],alist[i]
    return alist
# print(bubbleSort([1,4,2,6,8,44,12]))

#冒泡改进
def shortBubbleSort(alist):
    exhanges = True
    passnum = len(alist) - 1
    while passnum > 0 and exhanges:
        exhanges = False
        for i in  range(passnum):
            if alist[i] > alist[i + 1]:
                exhanges = True
                alist[i],alist[i + 1] = alist[i + 1],alist[i]
    return alist

# print(shortBubbleSort([1,4,2,6,8,44,12]))

#选择排序
def selectionSort(alist):
    for fillslot in range(len(alist) - 1,0,-1):
        pasitionOfMax = 0
        for location in range(1,fillslot +1):
            if alist[location] > alist[pasitionOfMax]:
                pasitionOfMax = location

        temp = alist[fillslot]
        alist[fillslot] = alist[pasitionOfMax]
        alist[pasitionOfMax] = temp
    return alist
#
# print( selectionSort([1,4,2,6,8,44,12]))

#插入排序
def insertionSort(alist):
    for index in range(1,len(alist)):
        currentvalue = alist[index]
        position =index
        while position > 0 and alist[position - 1 ] > currentvalue :
            alist[position] = alist[position - 1]
            position = position -1
        alist[position] = currentvalue

    return alist
# print(insertionSort([1,4,2,6,8,44,12]))

#希尔排序
def shellSort(alist):
    sublistcount = len(alist)//2
    while sublistcount > 0:
        for startposition in range(sublistcount):
            gapInsertionSort(alist,startposition,startposition)
        print("After increments of size",sublistcount,"The list is",alist)
        sublistcount =sublistcount//2

def  gapInsertionSort(alist,sart,gap):
    for i in range(sart + gap,len(alist),gap):
        currentvalue = alist[i]
        position = i
        while position >= gap and alist[position -gap] > concurrent:
            alist[position] =alist[position -  gap]
            position = position - gap
        alist[position] = currentvalue


#归并排序
def mergeSort(alist):
    if len(alist) > 1:
        mid = len(alist)//2
        lefthalf = alist[:mid]
        righthalf = alist[mid:]
        mergeSort(lefthalf)
        mergeSort(righthalf)
        i = j = k = 0
        while i < len(lefthalf) and j < len(righthalf):
            if lefthalf[i] < righthalf[j]:
                alist[k] = lefthalf[i]
                i = i + 1
            else:
                alist[k] = righthalf[j]
                j = j + 1
            k = k +1
        while i < len(lefthalf):
            i = i + 1
            k = k + 1
        while j < len(righthalf):
            alist[k] = righthalf[j]
            j = j + 1
            k = k + 1


#归并排序,python特性
def merge_sort(lst):
    if len(lst) <= 1:
        return lst
    middle = len(lst) // 2
    left = merge_sort(lst[ : middle])
    right = merge_sort(lst[middle :])
    merged = []
    while left and right:
        if left[0] <= right[0]:
            merged.append(left.pop(0))
        else:
            merged.append(right.pop(0))
    merged.extend(right if right else  left)
    return merged

#快排
def quickSort(alist):
    quickSortHelper(alist,0,len(alist) - 1)

def quickSortHelper(alist,first,last):
    if first < last:
        splitpoint =partition(alist,first,last)
        quickSortHelper(alist,first,splitpoint - 1)
        quickSortHelper(alist,splitpoint + 1,last)

def partition(alist,first,last):
    pivotvalue = alist[first]
    leftmark = first + 1
    rightmark = last
    done = False
    while not done:
        while leftmark <= rightmark and alist[leftmark] <= pivotvalue:
            leftmark = leftmark + 1
        while alist[rightmark] >= pivotvalue and rightmark >= leftmark:
            rightmark =rightmark - 1
        if rightmark < leftmark:
            done = True
        else:
            temp = alist[leftmark]
            alist[leftmark] = alist[rightmark]
            alist[rightmark] = temp
    temp = alist[first]
    alist[first] = alist[rightmark]
    alist[rightmark] = temp
    return rightmark