尚学堂：Python中的希尔排序和选择排序

前言

今天天分享一下我之前学习和写的python中的冒泡排序和插入排序。

希尔排序

希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法（前面冒泡排序和希尔排序是稳定的）。该方法因DL．Shell于1959年提出而得名。

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

1）插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率。

2）但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位。

下面看一下希尔排序Python算法实现

#shell_sort.py

def shell_sort(lists):

# 希尔排序

length = len(lists)

step = 2

group = length // step#注意这里一定是双斜杠，否则算出来的结果是float类型，下同

while group > 0:

for i in range(0, group):

j = i group

while j

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

shell_sort(lists)

print(lists)

选择排序

选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法（比如序列[5， 5， 3]第一次就将第一个[5]与[3]交换，导致第一个5挪动到第二个5后面）。

下面看一下选择排序Python算法实现

#selection_sort.py

def selection_sort(lists):

length = len(lists)

for i in range(0, length):

min = i

for j in range(i 1, length):

if lists[j]

min = j

lists[i], lists[min] = lists[min], lists[i]

return lists

selection_sort(lists)

print(lists)

小结

这里我们同时学习的是希尔排序和选择排序，希尔排序是插入排序的延伸，选择排序则比较简单直接，一般来说排序算法有插入排序、希尔排序、冒泡排序、快速排序、直接选择排序、堆排序、归并排序、基数排序等八种算法。由于最近较忙，排序算法就先到这里了，下面会有更多不同的精彩内容，敬请期待。

希望通过上面的内容能帮助大家深刻理解和学习希尔排序和选择排序。如果你有什么好的意见，建议，或者有不同的看法，我都希望你留言和我们进行交流、讨论。