算法之快速排序

快排

快排的整体思路是找到一个数，通过让这个数的左边都比它小，右边都比它大来使它归位，也就是找到它的位置，这种方式是所有的数都进行这种方式进行快速排序。

快排的时间复杂度是：O(n log n)

快排的空间复杂度是：

def partition(li,left,right):
    tmp = li[left]

    while left < right:

        while left < right and li[right] >= tmp:
            right -=1
        li[left] = li[right]

        while left < right and li[left] <= tmp :
            left += 1
        li[right] = li[left]

    li[left] = tmp

    return left


def quick_sort(li,left,right):

    if left < right:
        mid = partition(li,left,right)
        quick_sort(li,left,mid)
        quick_sort(li,mid+1,right)



li = [96,23,1,78,34,2,99,25,67,123,69,43,75,88,8,24,55]

quick_sort(li,0,len(li)-1)

# !/usr/bin/env python
# -*- coding:utf-8 -*-
# Author: nulige

import time
import functools
import sys
import random
import copy

# 设置递归限制
sys.setrecursionlimit(1000000)
from concurrent import futures


def run_time(func):
    """为了装饰别的函数，统计函数执行的时间"""

    @functools.wraps(func)
    def wrapper(*args, **kwargs):
        # 开始时间
        start_time = time.time()
        # 调用被装饰的函数
        func(*args, **kwargs)
        # 结束时间
        end_time = time.time()
        # 打印输出，更佳的方法是将其写入到log中
        print("%s函数的执行时间为： %s s" % (func.__name__, end_time - start_time))

    return wrapper


@run_time
def fast_sort_1(data_list):
    """
    快排方法一：
    因为快排包含递归，所以不能直接被装饰，套一层外壳
    :param data_list:
    :return:
    """
    return fast_sort_basic1(data_list)


def fast_sort_basic1(data_list):
    """简单的快速排序，消耗内存，空间复杂度略高"""
    if len(data_list) == 0:
        # 如果传过来的数据为[],直接返回
        return []
    else:
        # 把第一个数据拿出来，
        # 比它小的数据放在左边，再次调用本函数                                    +第一个数据      +比它小的数据放在右边，再次调用本函数
        return fast_sort_basic1([i for i in data_list[1:] if i < data_list[0]]) + [data_list[0]]+ fast_sort_basic1([i for i in data_list[1:] if i > data_list[0]])


@run_time
def fast_sort_2(data_list):
    """
    快排方法二：
    拿到第一个元素，然后整理，直到左边元素比他小，右边元素比他大
    整理的过程
    :param data_list:
    :return:
    """
    # 然后结束，把6放在位置上，然后就这个中间的数字的位置就是最终 的位置
    fast_sort_basic2(data_list, 0, len(data_list) - 1)


def fast_sort_basic2(data, left, right):
    if left < right:
        # 调用partiton函数 mid 处为第一个元素应该待的地方
        mid = partition(data, left, right)
        # 对左边的数据继续做快速排序
        fast_sort_basic2(data, left, mid - 1)
        # 对右边的数据继续做快速排序
        fast_sort_basic2(data, mid + 1, right)


def partition(data, left, right):
    """
    #-------> 小
    #大<-------
    #将数据的左边的第一个数据，数据调整为自己应该待的位置
    #[5,2,1,4,3]
    # 从第一个数字开始，把它放在它应该在的位置，什么叫它应该在的位置，就是左边的数字都比它小，右边的数字都比它大
    1、从最右边开始找，找到第一个比它小的数 和 它 交换位置，把第一个数字放到新的位置
    2、然后从这个新的位置， 左边开始找比它大的数字，和它大小比较，然后和新的位置交换
    3、不断重复，就会使第一个数字出现在它应该出现的位置
    #那么这个数字所在的位置就是有序区
    """
    # 找到左边的第一个数据
    tmp = data[left]
    # 一直循环直到这个数据待在它自己该待的位置
    while left < right:
        # 从右边开始找数据
        while data[right] > tmp and left < right:
            # 找不到，继续往左找
            right = right - 1
        # 右边找到一个比它小，赶紧交换位置
        data[left] = data[right]
        # 从左边开始找数据
        while data[left] < tmp and left < right:
            # 找不到继续往右找
            left = left + 1
        # 左边找到一个比它大的赶紧交换位置
        data[right] = data[left]
    # 此时此刻左边和右边完全相同
    # 这个数据已经待在它该待的位置
    data[left] = tmp
    return left


if __name__ == '__main__':
    a = list(range(10000))
    random.shuffle(a)
    d = copy.deepcopy(a)
    e = copy.deepcopy(a)

    fast_sort_1(d)
    fast_sort_2(e)

 

冒泡排序

每次冒出来一个最大的值

def bubble_sort(li):

    for i in range(len(li)-1):
        for j in range(len(li)-1-i):
            if li[j] > li[j+1]:
                li[j],li[j+1] = li[j+1],li[j]


    return li



li = [96,23,1,78,34,2,99,25,67,123,69,43,75,88,8,24,55]

bubble_sort(li)

def bubble_sort(li):

    for i in range(len(li)-1):

        flag = False
        for j in range(len(li)-1-i):
            if li[j] > li[j+1]:
                li[j],li[j+1] = li[j+1],li[j]
                flag = True
        if not flag:
            return li

    return li



li = [96,23,1,78,34,2,99,25,67,123,69,43,75,88,8,24,55]

bubble_sort(li)

选择排序