排序算法的python实现

当下 ║ 2018.12.12

人生苦短，我们都要用Python,不定期更新Python相关知识点

知识点

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

排序的稳定性： 经过某种排序后，如果两个记录序号同等，且两者在原无序记录中的先后秩序依然保持不变，则称所使用的排序方法是稳定的，反之是不稳定的。

内排序和外排序 内排序：排序过程中，待排序的所有记录全部放在内存中 外排序：排序过程中，使用到了外部存储。 通常讨论的都是内排序。

影响内排序算法性能的三个因素：

时间复杂度：即时间性能，高效率的排序算法应该是具有尽可能少的关键字比较次数和记录的移动次数

空间复杂度：主要是执行算法所需要的辅助空间，越少越好。

算法复杂性。主要是指代码的复杂性。

首先定义交换任意两项位置的函数swap。

def swap(x,i,j):

'''

交换x的i,j位置元素

'''

temp = x[i]

x[i] = x[j]

x[j] = temp

1、选择排序

选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法。

def selectionSort(x):

i = 0

while i < len(x) - i:

j = i + 1

minindex = i

while j < len(x):

if x[minindex] > x[j]:

minindex = j

j += 1

if minindex != i:

swap(x,i,minindex)

i += 1

return x

函数包括一个嵌套的循环，对于大小为n的列表，外围的循环执行n-1次，内部循环的次数从n-1递减到1，因此，选择排序在各种情况下的复杂度为平方阶.

2、二元选择排序法（选择排序改进）

选择排序法每轮只找最小值，效率较低，可以考虑每次同时寻找最小值和最大值，并且在某一轮如果最小值与最大值相同，说明剩下的数字都相同，可以直接结束。

此外，与选择排序不同的是，需要考虑到如果第i轮里，恰好第i个数就是最大值时，先交换minindex和i之后，最大值的下标变成了minindex，这时候应该交换minindex和n-i-1，而不是maxindex和n-i-1。

def selectionSort_1(x):

i = 0

while i <= len(x) // 2:###两侧一起向中心移动，因此为一半

minindex = i

maxindex = i

j = i + 1

while j < len(x) - i :

if x[minindex] > x[j]:

minindex = j

if x[maxindex] < x[j]:

maxindex = j

j+= 1

if x[minindex] == x[maxindex]:

return x

if minindex != i:

swap(x,i,minindex)

if maxindex != len(x) - 1 - i :

if maxindex != i:

swap(x,len(x) - 1 - i,maxindex)

else:

swap(x,len(x) - 1 - i, minindex)

i += 1

return x

3、冒泡排序

冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的排序算法。

它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果他们的顺序（如从大到小、首字母从A到Z）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素已经排序完成。

这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。

def BubbleSort(x):

j = len(x) - 1

while j > 0:

i = 0

while i < j:

if x[i] > x[i + 1]:

swap(x,i,i+1)

i += 1

j -= 1

return x

类似选择排序，冒泡排序也是一个嵌套的循环，如果列表是已经排好序的，冒泡排序不会执行任何的交换，在最坏的情况下，为平方阶复杂度。

4、冒泡排序法改进

在最好的情况下，冒泡排序法依然会执行每个循环但不进行任何操作，可以设定一个标记判断冒泡排序法在一次内层循环中是否进行了交换，如果没有，说明算法已经使排好序的，就可以直接返回，不过这种方法只是对最好的情况进行了改进.

def BubbleSort_1(x):

j = len(x) - 1

while j > 0 :

flag = False

i = 0

while i < j:

if x[i] > x[i + 1]:

swap(x,i,i+1)

flag = True

i += 1

if not flag:

return x

j -= 1

return x

5、双向冒泡排序法

冒泡排序法存在所谓的“乌龟问题”，假设我们需要将序列按照升序排序。序列中的较小的数字又大量存在于序列的尾部，这样会让小数字在向前移动得很缓慢，因此针对这一问题，产生了双向冒泡排序法，也称鸡尾酒排序法。

双向冒泡排序法由两个方向同时进行冒泡，首先由左向右为大元素移动方向，从右向左为小元素移动方向，然后每个元素都依次执行。在第i次移动后，前i个和后i个元素都放到了正确的位置。

def BidirectionalBubbleSort(x):

j = 0

while j <= len(x)//2:###两侧一起向中心移动，因此为一半

flag = False

for i in range(j ,len(x) - j - 1):

if x[i]>x[i+1]:

swap(x,i,i+1)

flag=True

for i in range(len(x)- 1 - j,j,-1):

if x[i]<x[i-1]:

swap(x,i,i-1)

flag=True

if not flag:

return x

j += 1

return x

6、插入排序法

有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序，这个时候就要用到一种新的排序方法——插入排序法,插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为O(n^2)。是稳定的排序方法。插入算法把要排序的数组分成两部分：第一部分包含了这个数组的所有元素，但将最后一个元素除外（让数组多一个空间才有插入的位置），而第二部分就只包含这一个元素（即待插入元素）。在第一部分排序完成后，再将这个最后元素插入到已排好序的第一部分中。

插入排序的基本思想是：每步将一个待排序的记录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。

def InsertionSort(x):

i = 1

while i < len(x):

j = i - 1

item = x[i]

while j >= 0 and item < x[j]:

x[j + 1] = x[j]

j -= 1

x[j + 1] = item

i += 1

return x

7、希尔排序(插入排序改进)

希尔排序(Shell's Sort)是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因D.L.Shell于1959年提出而得名。

希尔算法的逻辑是，先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序，具体步骤如下：

1.设定一个较大间隔gap，对所有间隔为gap的数据通过插入排序法进行排序；

2.执行完之后根据某种逻辑缩小gap（代码中采用除以3取整的办法），重复上述过程，直到gap = 0。

通过以上步骤，最终得到的列表是排好序的，并且可以证明，这种方法的平均的复杂度是O(nlogn)。

def HashSort(x):

gap = round(len(x)*2/3)

while gap > 0 :

print('gap = ',gap )

i = gap

while i < len(x):

j = i - gap

item = x[i]

while j >= 0 and item < x[j]:

x[j + gap] = x[j]

j -= gap

x[j + gap] = item

i += 1

gap = round(gap/3)

return x