python实现经典排序算法

冒泡排序

这里是向前冒泡，即每一趟排序后最小元素冒泡至最前

def bubble_sort(lst):
    for i in range(len(lst)): 
        for j in range(i+1,len(lst)):
            if lst[i] > lst[j]:
                temp = lst[j]
                lst[j] = lst[i]
                lst[i] = temp
    return lst

选择排序

选择排序和冒泡相似，每一趟排序完后将最小元素选择至最前，只是在比较过程中不交换元素位置，而是使用额外的变量将当前最小元素的位置记下，当整个列表比较完以后，将待排序最前元素与最小元素交换

def select_sort(lst):
    #与冒泡相似，只是比较时不交换元素
    for i in range(len(lst)-1):
        #min负责记录下最小元素的位置
        min = i
        for j in range(i+1,len(lst)):
            if lst[min] > lst[j]:
                min = j
        #将最小元素与第一个元素交换，选择出第一个最小元素
        temp = lst[i]
        lst[i] = lst[min]
        lst[min] = temp
    return lst

快速排序

核心思想： 选择一个元素放到合适的位置，使左边元素都比它小，右边元素都比它大

算法流程：这里选择第一个元素

quick_sort主函数所做的事：

• 判断列表若长度小于1，则不用排序，直接返回
• 列表长度大于一，得到待排序列表第一个元素的在列表中的正确位置对该位置左边和右边的元素分别递归快速排序

partition函数所做的事：得到选择元素的正确位置（使其左边元素均比它小，右边元素均比它大）

• left指向待排序列表的第一个元素，right指向最后一个元素（赋给元素的索引）
• 将第一个元素的值赋给item，全程使用item进行比较，当left等于right循环结束，这里使用left小于right作为结束条件
• 循环开始，先从最右边开始，item与right指向元素进行比较，若right比item大，则right往左移一个位置（自减一）
  当right比item小时，则将right指向元素赋值给left（因为此时的item值等于left,所以left值不会丢失），并且
• item开始与左边元素进行比较
• item与此时left指向元素比较，若left元素小于item，left右移，否则将left元素赋给right，并且重复步骤3
• item不断与left，right元素比较，是left和right逐渐靠近，也就是待比较的范围不断缩小，直到left和right相等时，代表整个列表比较完，item找到了合适的位置。比较过程中，不断将比item小的元素放置左侧，大的元素
  放置右侧，实现了左侧元素均比它小，右侧元素比它大的目的

# 快速排序：选择一个元素放到合适的位置，使左边元素都比它小，右边元素都比它大
 
def quick_sort(lst,left,right):    
    if left >= right:
        return lst
    i = partition(lst,left,right)
    quick_sort(lst,left,i-1)
    quick_sort(lst,i+1,right)
    return lst
     
def partition(lst,left,right):
    item = lst[left]
    while left < right:
        while (left<right and item<lst[right]):
            right-=1
        lst[left] = lst[right]    
        while (left<right and item>=lst[left]):
            left+=1
        lst[left]=lst[right]
    lst[right]=item
    return right
 

归并排序

merge2_sort函数：

• 判断列表长度若小于，即没有元素或只有一个元素时直接返回
• 否则不断递归，左半部分右半部分不断拆分，拆分到最小时开始合并成有序列表together，重复合并

merge2函数：实现两个有序列表的合并，

• 定义一个列表result将排序比较过程中的元素由小到大依次追加
• 左列表的元素依次和右列表元素比较，当比右列表元素小时，直接放入result，说明已排好序，然后左列表下一个元素开始比较，当比右列表元素大时，右列表该元素放入result，继续与下一个右列表元素比较
• 直到两个列表其中一个没有元素时，停止比较，有多余元素的列表直接将剩下元素追加进result中，合并完毕

def  merge2_sort(lst):
    #递归切分成最小一个元素
    print lst
    if len(lst)<2:
        return lst
    else:
        mid = len(lst)//2
        left = merge2_sort(lst[:mid])
        right = merge2_sort(lst[mid:])
        together = merge2(left,right)
        print('merge:',together)
        return together
 
def merge2(left,right):
    #合并过程
    i = 0
    j = 0
    result = []
    while i<len(left) and j<len(right):
        if left[i]<right[j]:
            result.append(left[i])
            i+=1
        else:
            result.append(right[j])
            j+=1
    #当左边列表更长或右边列表更长时直接往结果列表添加
    while i < len(left):
        result.append(left[i])
        i+=1
    while j < len(right):
        result.append(right[j])
        j+=1
    return result