本文用Python实现了快速排序、插入排序、希尔排序、归并排序、堆排序、选择排序、冒泡排序共7种排序算法。
一、快速排序
1.介绍
快速排序由C. A. R. Hoare在1962年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
2.步骤及流程图
(1)从数列中挑出一个元素，称“基准”
(2)重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
(3)递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
流程图：（字很丑~后边还是不画了哈）
3.python实现
#encoding=utf-8 import random #快速排序 def qsort(list,low,high): if low >= high: return first=low last=high key=list[first] #主循环，算法重点，见流程图 while last>first: while last>first and list[last] >= key: last-=1 list[first]=list[last] while last>first and list[first] <= key: first+=1 list[last]=list[first] list[first]=key #这两行利用递归完成两个分区的排序 qsort(list,low,first-1) qsort(list,first+1,high) #以下是调用快速排序方法 my_list=[] for i in range(8): my_list.append(random.randint(1,300)) qsort(my_list,0,len(my_list)-1) print(my_list)
4.视觉效果展示
二、插入排序
1.介绍
插入排序（Insertion Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
2.步骤
(1)从第一个元素开始，该元素可以认为已经被排序
(2)取出下一个元素，在已经排序的元素序列中从后向前扫描
(3)如果该元素（已排序）大于新元素，将该元素移到下一位置
(4)重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
(5)将新元素插入到该位置中
(6)重复步骤2
3.python实现
#encoding=utf-8 import random # 插入排序 def insert_sort(lists): count = len(lists) for i in range(1, count): #取下一个元素到key key = lists[i] j = i - 1 while j >= 0: #找到新元素（key）的正确位置 if lists[j] > key: lists[j + 1] = lists[j] lists[j] = key j -= 1 return lists #调用插入排序方法 my_list=[] for i in range(8): my_list.append(random.randint(1,300)) insert_sort(my_list) print(my_list)
三、希尔排序
1.介绍
希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因DL．Shell于1959年提出而得名。 希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
2.python实现（小詹写的运行过程出了点错，先借用下别人的小程序哈）
#encoding=utf-8 # 希尔排序的实质就是分组插入排序，该方法又称缩小增量排序，因DL．Shell于1959年提出而得名。 # 希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。 # 希尔排序是基于插入排序的以下两点性质而提出改进方法的： # 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率 # 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位 def ShellInsetSort(array, len_array, dk): # 直接插入排序 for i in range(dk, len_array): # 从下标为dk的数进行插入排序 position = i current_val = array[position] # 要插入的数 index = i j = int(index / dk) # index与dk的商 index = index - j * dk # while True: # 找到第一个的下标，在增量为dk中，第一个的下标index必然 0<=index<dk< span=""> # index = index - dk # if 0<=index and index <dk:< span=""> # break # position>index,要插入的数的下标必须得大于第一个下标 while position > index and current_val < array[position-dk]: array[position] = array[position-dk] # 往后移动 position = position-dk else: array[position] = current_val def ShellSort(array, len_array): # 希尔排序 dk = int(len_array/2) # 增量 while(dk >= 1): ShellInsetSort(array, len_array, dk) print(">>:",array) dk = int(dk/2) if __name__ == "__main__": array = [49, 38, 65, 97, 76, 13, 27, 49, 55, 4] print(">:", array) ShellSort(array, len(array)) </dk:<></dk<>
3.视觉效果展示
以上就是本期的内容，欢迎小伙伴们扫码订阅点赞噢~
