排序算法

插入排序

def inster_sort(lists):
    count = len(lists)
    for i in range (1,count):
        key = lists[i]
        j = i -1
        while j>=0:
            if lists[j] > key:
                lists[j+1] = lists[j]
                lists[j] = key
            j -= 1
     return lists
# 时间复杂度O(n**2)，空间复杂度O(1) ，稳定

希尔排序

def shell_sort(lists):
    # 希尔排序
    count = len(lists)
    step = 2
    group = count / step
    while group > 0:
        for i in range(0, group):
            j = i + group
            while j < count:
                k = j - group
                key = lists[j]
                while k >= 0:
                    if lists[k] > key:
                        lists[k + group] = lists[k]
                        lists[k] = key
                    k -= group
                j += group
        group /= step
    return lists

冒泡排序

def bubble_sort(lists):
    # 冒泡排序
    count = len(lists)
    for i in range(0, count):
        for j in range(i + 1, count):
            if lists[i] > lists[j]:
                lists[i], lists[j] = lists[j], lists[i]
    return lists
# 时间复杂度O(n*2)，空间复杂度O(nlog2N)，稳定

快速排序

def quick_sort(lists, left, right):
    # python 快速排序
    if left >= right:
        return lists
    key = lists[left]
    low = left
    high = right
    while left < right:
        while left < right and lists[right] >= key:
            right -= 1
        lists[left] = lists[right]
        while left < right and lists[left] <= key:
            left += 1
        lists[right] = lists[left]
    lists[right] = key
    quick_sort(lists, low, left - 1)
    quick_sort(lists, left + 1, high)
    return lists
# 时间复杂度O(n*log2N)，空间复杂度O(nlog2N)，不稳定

# include <stdio.h>
# include <stdlib.h>
# define BFU_SIZE 10
# c 快速实现
# 打印数组元素
void display(int array[],int maxlen){
    int i ;
    for(i=0;i<maxlen;i++){
        printf("%-3d",array[i]);
    }
    printf("\n");
    return ;
}

# 执行交换两个数的值
void swap(int *a,int *b){
    int temp;
    temp=*a;
    *a=*b;
    *b=temp;
    return;
}

# 快排算法
void quicksort(int attay[],int maxlen,int begin,int end){
    int i,j;
    if(begin<end){
        i=begin+1;
        j=end;
        while(i<j){
            if(array[i]>array[begin]){
                swap(&array[i],&array[j]);
                j--;
            }
            else{
                i++;
            }
        }
        # 此时数组分成了两个部分，进行比较，确定 基准数
        if(array[i]>=array[begin]){
            i--;
        }
        swap(&array[begin],&array[i]);
        quicksort(array,maxlen,begin,i);
        quicksort(array,amxlen,j,end);
    }
}

int main(){
    int n;
    int array[BUF_SIZE]={}
    int maxlen=BUF_SIZE
    
    printf("排序之前");
    display(array,maxlen)
    
    quicksort(array,amxlen,0,maxxlen-1);
    printf("排序之后");
    display(araay,maxxlen);

    retunr 0;
}

直接选择排序

def select_sort(lists):
    # python 选择排序
    count = len(lists)
    for i in range(0, count):
        min = i
        for j in range(i + 1, count):
            if lists[min] > lists[j]:
                min = j
        lists[min], lists[i] = lists[i], lists[min]
    return lists
# 时间复杂度O(n**2)，空间复杂度O(1)，不稳定

# c 选择排序
void selection_sort(int arr[],int n){
    int i,j,k;
    for(i=0;i<n;i++){
        k=-1;
        int m =arr[i];
        for(j=i;j<n;j++){
            if(arr[j]<m){
                m=arr[j];
                k=j;
            }
        }
        if(k!=1){
            arr[k]=arr[i];
            arr[i]=m;
        }
    }
    
}

堆排序

from collections import deque
L=deque([34,23,32,45,67,87])
l.appendleft(0)

def element_exchange(numbers,low,high):
    temp=numbers[low]
    i=low
    j=2*i
    
    while j<=high:
        # 如果右节点较大，则j指向右节点
        if j<high and numbers[j]<numbers[j+1]:
            j=j+1
        if temp>numbers[j]:
            # 将numbers[j]放到双亲节点上
            numbers[i]=numbers[j]
            i=j
            j=i*2
        else:
            break;
    # 被调整节点放入最终位置        
    numbers[i]=temp

def top_heap_sort(numbers):
    length=len(numbers)-1
    # 指定第一个元素的下标，是无序序列的第一个非叶子节点
    first_exchange_element=length/2
    # 建立初始堆
    print first_exchange_element
    for x in tange(first_exchange_element):
        element_exchange(numbers,first_exchange_element-x,length)
    # 将根节点放到最终位置，继续堆排序
    for y in range(length-1):
        temp=numbers[1]
        numbers[1]=numbers[length-y]
        numbers[length-y]=temp
        element_exchange(numbers,1,length-y-1)
# 时间复杂度O(n*log2N),空间复杂度O(1),不稳定

归并排序

# 进行拆分
def merge_sort(lists):
    # 长度不足1，直接返回
    if len(lists) <= 1:
        return lists
    # 二分
    num = len(lists) / 2
    # 递归拆分
    left = merge_sort(lists[:num])
    right = merge_sort(lists[num:])
    # 执行比较
    return merge(left, right)
# 进行比较合并
def merge(a,b):
    c = []
    h=j=0
    while j<len(a) and h<len(b):
        # 小的进入
        if a[j] < b[h]:
            c.append(a[j])
            j+=1
        else:
            c.append(b[h])
            h+=1
    # a遍历完，插入b
    if j==len(a):
        for i in b[h:]:
            c.append(b[i])
    # b遍历完，插入a
    if h==len(b):
        for i in a[j:]:
            c.append(i)
    return c
# 时间复杂度O(n*log2N)，空间复杂度O(1)，稳定

基数排序

import math
def radix_sort(lists, radix=10):
    k = int(math.ceil(math.log(max(lists), radix)))
    bucket = [[] for i in range(radix)]
    for i in range(1, k+1):
        for j in lists:
            bucket[j/(radix**(i-1)) % (radix**i)].append(j)
        del lists[:]
        for z in bucket:
            lists += z
            del z[:]
    return lists

斐波那契数列

# 递归实现
def item( num ):
    if num == 0 :
        res = 0
    elif num == 1:
        res = 1
    else:
        res = item ( num - 1) + item (num -2)
    return res

def printFibo( no ):
    i = 0

    while i < no:
        print item(i)
        i += 1

# 迭代器实现，返回一个列表
def fibo(num):
    numList = [0,1]

    for i in range(num - 2):
        numList.append(numList[-2] + numList[-1])
    return numList

深度遍历

def DFS(nodes):
    # queue是堆栈
    # order是存放的具体路径
    queue,order=[],[]
    queue.append(nodes)
    while queue:
        v=queue.pop()
        order.append(v)
        for w in sequense[v]:
            if w not in order and w not in queue:
                queue.append(w)
    return order

广度遍历

def BFS(node):
    queue,order=[],[]
    queueu.append(node)
    order.append(node)
    while queue:
        v=queue.pop()
        for w in sequense[v]:
            if w not in order:
                order.append(w)
                queue.append(w)
    return order

二分查找

def binary_search(find,list1):
    low=0
    high=len(list1)
    while low<high:
        mid=(low+high)/2
        if list1[mid]==find:
            return mid
        elif list1[mid]>find:
            high=mid-1
        else:
            low=mid+1
    return -1

​