六大排序 - 简书

## 1.冒泡排序

```python

# 2 冒泡排序：它重复的走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来，走访数列的工作是重复的执行到没有再需要交换，也就是说该数列已经完成排序。

#时间复杂度 O(n^2)

#空间复杂度：O(1)

#稳定性：稳定

def bubble_sort(blist):

count = len(blist)

for i in range(0,count):

for j in range(i+1,count):

if blist[i] > blist[j]:

blist[i],blist[j] = blist[j],blist[i]

return blist

print(bubble_sort([4,5,6,7,8,2,3,1,0]))

```

___

## 2.插入排序

```python

#1 插入排序:插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的，个数加1 的有序数据，算法用于少量数据的排序，首先将第一个作为已经排好序的，然后每次从后的取出插入到前面并排序。

#时间复杂度 O(n^2)

#空间复杂度：O(1)

#稳定性：稳定

def insert_sort(ilist):

for i in range(len(ilist)):

for j in range(i):

if ilist[i] < ilist[j]:

ilist.insert(j,ilist.pop(i))

break

return ilist

print(insert_sort([4,6,7,3,2,1,8,0]))

```

___

## 3.选择排序

```python

#3 选择排序：第一趟，在待排序记录r1 。。。r(n)中选出最小的记录，将它与r1 交换，第二趟，在待排序记录r2 ~ r(n) 中选出最小的记录，将它与 r2 交换，以此类推，第i趟在待排序记录 r[i]~r[n]中选出最小的记录，将它与r[i]交换，使有序序列不断增长直到全部排序完毕。

#时间复杂度 O(n^2)

#空间复杂度：O(1)

#稳定性：不稳定

def select_sort(slist):

#外层循环控制循环次数

for i in range(len(slist)):

#假设找到的最小元素下标为j

x = i

#寻找最小元素的过程

for j in range(i,len(slist)):

#假设最小下标的值，大于循环中一个元素，那么就改变最小值的下标

if slist[j] < slist[x]:

x = j

#循环一开始就假设把最小值的下标赋值给变量 x

# 在不停的循环中，不停的交换两个不一样大小的值

slist[i],slist[x] = slist[x],slist[i]

#返回排好序的列表

return slist

if __name__ == '__main__':

arrayList = [4,5,6,7,3,2,6,9,8]

select_sort(arrayList)

print(arrayList)

```

___

## 4.希尔排序

```python

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

#时间复杂度 O(n^2)

#空间复杂度：O(nlogn)

#稳定性：不稳定

def shell_sort(slist):

count = len(slist)

step = 2

group = count // step

while group>0:

for i in range(group):

j = i + group

while j < count:

key = slist[j]

k = j - group

while k >= 0:

if slist[k] > key:

slist[k+group] = slist[k]

slist[k] = key

k = k - group

j = j + group

group = group // step

return slist

# print(shell_sort([4,5,7,3,2,6,9,8,0]))

def ShellSort(arrList):

arrayLen = len(arrList)

h = 1

while h < arrayLen//3:

h = h * 3 + 1

#插入排序的方法，判断是不是后一个比前一个要小

#如果是则交换

while h >= 1:

for i in range(h,arrayLen):

j = i

while j >= h and arrList[j] < arrList[j-h]:

arrList[j] ,arrList[j-h] = arrList[j-h],arrList[j]

j -= h

h //= 3

if __name__ == '__main__':

arrList = [14,33,27,10,35,19,42,44]

ShellSort(arrList)

print(arrList)

```

___

## 5.归并排序

```python

# 当n较大，则应采用时间复杂度为O(nlog2n)的排序方法：快速排序、堆排序或归并排序序。

"""

归并排序：采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并

时间复杂度：O(nlog₂n)

空间复杂度：O(1)

稳定性：稳定

"""

# 归并排序 Merge_Sort

def MergeSort(arrayList):

arrayLen = len(arrayList)

#判断输入参数的正确性,如果长度小于1，就说明为1

if arrayLen <= 1:

return arrayList

midIndex = arrayLen//2

#左边的部分去做 MergeSort

leftArray = MergeSort(arrayList[:midIndex])

#右边的去做 MergeSort

rightArray = MergeSort(arrayList[midIndex:])

#将左右两边合并，称为一个新的数组，并已经排序成功

retArray = MergeCore(leftArray,rightArray)

return retArray

def MergeCore(leftArray,rightArray):

#首先需要定义两个指针,这两个指针，分别指向这两个数组的第一个元素

leftIndex = 0

rightIndex = 0

#获取两个数组的长度，用于指出上面两个指针的边界是什么

leftLen = len(leftArray)

rightLen = len(rightArray)

#定义一个返回的列表,这一步就代表空间复杂度至少是 O(n)

retList = []

#循环两个数组寻找最小值加入到返回值的数组中

while leftIndex < leftLen and rightIndex < rightLen:

if leftArray[leftIndex] < rightArray[rightIndex]:

retList.append(leftArray[leftIndex])

leftIndex += 1

else:

retList.append(rightArray[rightIndex])

rightIndex += 1

#下面的代码是将剩余的数组中内容放置在返回的数组中

retList.extend(leftArray[leftIndex:])

# while leftIndex < leftLen:

# retList.append(leftArray[leftIndex])

# leftIndex += 1

retList.extend(rightArray[rightIndex:])

# while rightIndex < rightLen:

# retList.append(rightArray[rightIndex])

# rightIndex += 1

return retList

if __name__ == '__main__':

# 14,33,27,10,35,19,42,44

retList = MergeSort([14,33,27,10,35,19,42,44])

print(retList)

```

___

## 6.快速排序

```python

"""

快速排序：是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短；

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列

时间复杂度：O(nlog₂n)

空间复杂度：O(nlog₂n)

稳定性：不稳定

"""

#快排的主函数，传入参数为一个列表，左右两端的下标

def QuickSort(array,leftIndex=0,rightIndex=None):

#数组的长度

arrayLen = len(array)

#长度为1 的话或者空的话直接返回数组

if arrayLen <= 1:

return array

#程序一开始如果没有给一个最右边的索引值导入话，那么我们就给它赋值一个就是数组的最右边的那个索引值。

if rightIndex == None:

rightIndex = arrayLen - 1

# 保护条件，只有满足左边索引小于右边索引的时候再开始排序

if leftIndex < rightIndex:

#找到基准的索引值传入参数，通过Partitions函数，获取k下标值

pivot = partition(array,leftIndex,rightIndex)

#递归前后半区对基准前面不部分继续快排

QuickSort(array,leftIndex,pivot - 1)

#对基准后半积分继续快排

QuickSort(array,pivot + 1,rightIndex)

def partition(array,leftIndex,rightIndex):

pivotValue = array[rightIndex]

#将最左侧的索引值给 i

i = leftIndex

#将最右侧的索引的前一个给j

j = rightIndex -1

#当left下标，小于right下标的情况下，此时判断二者移动是否相交，若未相交，则一直循环

while i < j:

# 当left对应的值大于锚点基准点参考值，就一直向左移动

while j > leftIndex and array[j] > pivotValue:

j -= 1

#当left对应的值小于基准点参考值，就一直向右移动

while i < rightIndex and array[i] <= pivotValue:

i += 1

#若移动完，二者仍未相遇则交换下标对应的值

if i < j:

array[j],array[i] = array[i],array[j]

i+=1

j-=1

#若移动完，已经相遇，则交换right对应的值和参考值

array[i],array[rightIndex] = array[rightIndex],array[i]

# 返回一个索引值

return i

# 《算法导论》中的快排程序

def partition2(array,leftIndex,rightIndex):

#设置一个左边的指针位置为左侧的前一个

i = leftIndex -1

#遍历除基准数之外的数

for j in range(leftIndex,rightIndex):

#比较遍历的数和基准数，若是小于基准数则换到数组前面去

if array[j] < array[rightIndex]:

#交换位置，将遍历的比基准数小的数放到我们指针的后一个上，然后这个时候指针向后移一位。当遍历的数大于我们的基准数的时候，不移动，而且指针也不发生变化，那么当我们遍历完一圈以后，把我们的基准数放到索引i 的后一个位置，那么就形成了一个基准数左边都是比它小的数，基准数右边都是比它大的数这样的模式。然后要把索引 i 的后一个位置作为基准数与原基准数交换位置，进而可以第二次来遍历比较。

array[j],array[i+1] = array[i+1],array[j]

i += 1

#遍历完了以后，将 left 位置上的数和最后一个数即 right 上的数互换位置，就重置基准数了。

array[rightIndex],array[i+1] = array[i+1],array[rightIndex]

#返回基准的下标

return i+1

if __name__ == '__main__':

array = [14,33,27,10,35,19,42,44]

QuickSort(array)

print(array)

```

排序内存使用

排序执行时间：

排序复杂度比较：