程序员面试必备之排序算法汇总(上)
希望小小詹同学学习同时能便于他人~
本文用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<>这里改过来了自己的也附加到下边，原因在于Python3.0，" / "就一定表示 浮点数除法，返回浮点结果;" // "表示整数除法。
#encoding=utf-8
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
array = [49, 38, 65, 97, 76, 13, 27, 49]
list1 = shell_sort(array)
print(list1)3.视觉效果展示
腾讯云开发者
