def wash_card(card_list, repeat, length):
    if repeat < 1:
        return card_list
    left = card_list[:length]
    right = card_list[length:]
    new_card_list = []
    for i in range(length - 1, -1, -1):
        new_card_list.append(right[i])
        new_card_list.append(left[i])
    new_card_list.reverse()
    return wash_card(new_card_list, repeat - 1, length)

import time
import random
import copy
def bubble_sort(list):
    '''
    冒泡排序
    '''
    length = len(list)
    # 第一级遍历
    for index in range(1, length):
        # 第二级遍历
        for j in range(1, length - index):
            if list[j] > list[j + 1]:
                # 交换两者数据，这里没用temp是因为python 特性元组。
                list[j + 1], list[j] = list[j], list[j + 1]
    return list
def bubble_sort_flag(list):
    '''
    带标记的冒泡排序
    '''
    length = len(list)
    flag = True
    for index in range(1, length):
        if not flag:  # 没有发生交换，直接返回list
            return list
        flag = False
        for j in range(1, length - index):
            if list[j] > list[j + 1]:
                list[j + 1], list[j] = list[j], list[j + 1]
                flag = True
    return list
def selection_sort(list):
    '''
    选择排序
    '''
    n = len(list)
    for i in range(1, n):
        min = i
        for j in range(i + 1, n):
            if list[j] < list[min]:
                min = j
        if i != min:
            list[min], list[i] = list[i], list[min]
    return list
def insert_sort(list):
    '''
    插入排序
    '''
    n = len(list)
    for i in range(2, n):
        # 后一个元素和前一个元素比较
        # 如果比前一个小
        if list[i] < list[i - 1]:
            list[0] = list[i]
            j = i - 1
            while list[j] > list[0]:
                list[j + 1] = list[j]
                j -= 1
            list[j + 1] = list[0]
    return list
def shell_sort(list):
    '''
    希尔排序
    '''
    length = len(list)
    # 初始步长
    increment = length
    while increment > 1:
        increment = increment // 3 + 1;
        for i in range(increment + 1, length):
            if list[i] < list[i - increment]:
                list[0] = list[i]
                j = i
                while j >= increment and list[j - increment] > list[0]:
                    list[j] = list[j - increment]
                    j -= increment
                list[j] = list[0]
    return list
def merge_sort(list):
    '''
    归并排序
    '''
    # 认为长度不大于1的数列是有序的
    if len(list) <= 1:
        return list
    # 二分列表
    middle = len(list) // 2
    left = merge_sort(list[:middle])
    right = merge_sort(list[middle:])
    # 最后一次合并
    return merge(left, right)
# 合并
def merge(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
def quick_sort(list):
    '''
    快速排序
    '''
    if len(list) <= 1:
        return list
    else:
        pivot = list[0]
        return quick_sort([x for x in list[1:] if x < pivot]) + [pivot] + quick_sort([x for x in list[1:] if x >= pivot])
def shiftDown(arr, index, length):  # 自顶向下堆化，从k开始堆化
    N = length - 1
    while 2 * index <= N:
        j = 2 * index
        if j < N and arr[j] < arr[j + 1]:  # 选出左右孩子节点中更大的那个
            j += 1
        if arr[index] < arr[j]:
            arr[index], arr[j] = arr[j], arr[index]
            index = j
        else:
            break
def heap_Sort(l):
    '''
    堆排序
    '''
    n = len(l) - 1
    for i in range(n // 2, 0, -1):
        shiftDown(l, i, len(l))
    while n > 1:
        l[1], l[n] = l[n], l[1]
        shiftDown(l, 1, n)
        n -= 1
def count_sort(list):
    '''
    计数排序
    '''
    # 取得最大值和最小值
    max_ = max(list)
    min_ = min(list)
    # 创建数组C
    length = max_ - min_ + 1
    count = [0] * length
    # 统计每项出现的次数
    for index in list:
        if index > 0:
            count[index] += 1
        # 负数放在最大数后面
        if index < 0:
            count[max_ + abs(index)] += 1
    index = 1
    # 填值
    for a in range(length - 1, max_, -1):
        for c in range(1, count[a] + 1):
            list[index] = -a + max_
            index += 1
    for a in range(max_ + 1):
        for c in range(1, count[a] + 1):
            list[index] = a
            index += 1
    return list
def test(func, random_list):
    l = copy.deepcopy(random_list)
    print(func.__doc__)
    s = time.time()
    func(l)
    print(time.time() - s)
func = [bubble_sort, bubble_sort_flag, selection_sort, insert_sort, merge_sort, shell_sort, quick_sort, count_sort,
        heap_Sort]
for i in range(3):
    print('-----------------')
    random_list = [random.randint(1, 10000) for i in range(40)]
    random_list[0] = 0
    last = []
    for each_func in func:
        test(each_func, random_list)

int Sequential_search(int* a,int n,int key)
{
    int i;
    for (i = 1; i <=n; i++)
    {
        if(a[i]==key)
            return i;
    }
    return 0;
}
// 有哨兵版
// 时间复杂度O(n)
int Sequential_search(int* a,int n,int key)
{
    int i;
    a[0]=key;
    i=n;
    while(a[i]!=key)
        i--;
    return i;
}

// 时间复杂度O(logn)
int Binary_Search(int* a,int n,int key)
{
    int low,high,mid;
    low=1;
    high=n;
    while(low<=high)
    {
        mid=(low+high)/2;            //折半
        if(a[mid]>key)
            high=mid-1;
        else if(a[mid]<key)
            low=mid+1;
        else                        //a[mid]==key
            return mid;
    }
    return 0;
}

// 插值查找
int Insert_Search(int* a,int n,int key)
{
    int low,high,mid;
    low=1;
    high=n;
    while(low<=high)
    {
        mid=low+(high-low)*(key-a[low])/(a[high]-a[low]);            //插值
        if(a[mid]>key)
            high=mid-1;
        else if(a[mid]<key)
            low=mid+1;
        else                        //a[mid]==key
            return mid;
    }
    return 0;
}

// 斐波那契查找
// 斐波那契数列：
// 0    1     2     3     4     5     6    ....
// 0    1     1     2     3     5     8    ....
int Fibonacci_Search(int* a,int n,int key)
{
    int low,hgih,mid,i,k;
    low=1;
    high=n;
    k=0;
    while(n<F[k]-1)            //计算n位于斐波那契数列的位置
        k++;
    for(i=n;i<F[k]-1;i++)    //对不满的数值补全，防止数组越界
        a[i]=a[n];
    while(low<=high)
    {
        mid=low+F[k-1]-1;
        if(a[mid]>key)
        {
            high=mid-1;
            k=k-1;
        }
        else if(a[mid]<key)
        {
            low=mid+1;
            k=k-2;
        }
        else
        {
            if(mid<n)
                return mid;
            else
                return n;        //mid>n说明是最后一个，返回n
        }
    }
    return 0;
}