五大排序算法(Python)

所谓排序,就是使一串记录,按照其中的某个或某些关键字的大小,递增或递减的排列起来的操作。排序算法,就是如何使得记录按照要求排列的方法。

冒泡排序

基本思想

两个数比较大小,较大的数下沉,较小的数冒起来。

算法描述

  • 比较相邻的元素。如果第一个比第二个大,就交换它们两个;
  • 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对,这样在最后的元素应该会是最大的数;
  • 针对所有的元素重复以上的步骤,除了最后一个;
  • 重复步骤1~3,直到排序完成。

动态演示

代码实现

def bubble_sort(alist):
    n = len(alist)
    for i in range(n-1):
        for j in range(n-i-1):
            if alist[j] > alist[j+1]:
                alist[j],alist[j+1] = alist[j+1],alist[j]

选择排序

基本思想

在长度为N的无序数组中,第一次遍历n-1个数,找到最小的数值与第一个元素交换;
第二次遍历n-2个数,找到最小的数值与第二个元素交换;
。。。
第n-1次遍历,找到最小的数值与第n-1个元素交换,排序完成。

动态演示

代码实现

def select_sort(alist):
    n = len(alist)
    for i in range(n-1):
        min = i
        for j in range(i+1,n-1):
            if alist[min]>alist[j]:
                min = j
        alist[i],alist[min] = alist[min],alist[i]

插入排序

基本思想

在要排序的一组数中,假定前n-1个数已经排好序,现在将第n个数插到前面的有序数列中,使得这n个数也是排好顺序的。如此反复循环,直到全部排好顺序。

动态演示

代码实现

def insert_sort(alist):
    n = len(alist)
    for i in range(n-1):
        j = i
        while j>0:
            if alist[j] < alist[j-1]:
                alist[j-1],alist[j]=alist[j],alist[j-1]
            else:
                break
        j-=1

快速排序

基本思想

  • 先从数列中取出一个数作为key值;
  • 将比这个数小的数全部放在它的左边,大于或等于它的数全部放在它的右边;
  • 对左右两个小数列重复第二步,直至各区间只有1个数。

动态演示

代码实现

def quick_sort(alist,start,end):
    if start>=end:
        return
    mid = alist[start]
    low = start
    high = end
    while low<high:
        while low<high and alist[high] >  mid:
            high-=1
        alist[low] = alist[high]
        while low<high and alist[low] <mid:
            low+=1
        alist[high]=alist[low]
    alist[low] = mid
    quick_sort(alist,start,low-1)
    quick_sort(alist,low+1,end)

归并排序

基本思想

首先考虑下如何将2个有序数列合并。这个非常简单,只要从比较2个数列的第一个数,谁小就先取谁,取了后就在对应数列中删除这个数。然后再进行比较,如果有数列为空,那直接将另一个数列的数据依次取出即可。

动态演示

代码实现

def merg_sort(alist):
    n = len(alist)
    if n<=1:
        return alist
    mid = n//2
    left_array = merg_sort(alist[0:mid])
    right_array = merg_sort(alist[mid:])
    reult=[]
    left_point,right_point=0,0
    while left_point<len(left_array) and right_point<len(right_array):
        if left_array[left_point] > right_array[right_point]:
            reult.append(right_array[right_point])
            right_point+=1
        else:
            reult.append(left_array[left_point])
            left_point+=1
    reult.extend(left_array[left_point:])
    reult.extend(right_array[right_point:])
    return reult

人已赞赏
Python3

多线程和并发编程

2020-6-19 11:40:19

算法

有效的字母异位词

2020-6-29 11:53:29

0 条回复 A文章作者 M管理员
    暂无讨论,说说你的看法吧
个人中心
今日签到
有新私信 私信列表
搜索