画一下本文主要实现归并排序和希尔排序如果想实现其他算法可参考这篇

选择冒泡

这两种排序方案简单到很难说是什么算法其中选择排序通过遍历一次数组选出其中最大小的值放在新数组的第一位,再从剩下的数里选出最大小的放到第二位依次类推冒泡排序则是通过重复走访要排序的数组比较相邻元素如果顺序不符合要求则交换位置直到不需要交换为止。

选择排序冒泡排序

tempN-i):if(x[j]x[j1]):x[j],x[j1]

x[j1],x[j]下面给出选择排序的绘图代码其他的所有排序算法其实只需改变核心部分。

import

#存储当前顺序用于绘图nowIndex.append([i,j,iMax])

#存储当前的i,j,max位置用于绘图if(x[j]x[iMax]):iMax

jxs.append(x*1)nowIndex.append([i,j,iMax])x[iMax],x[i]

x[i],x[iMax]fig,

np.repeat(gray,N)colors[nowIndex[n]]

b,g,rax.clear()bar

插入排序的基本思路是将数组分为前后两个部分前面有序后面无序。

逐个扫描无序数组将每次扫描的数插入到有序数组中从而有序数组越来越长无序数组越来越短直到整个数组都是有序的。

核心代码为

xi​被取出放在旁边所以其动态图中大部分时间会缺失一个值在图中将其置于最右侧其动态过程如图所示蓝色表示抽出来准备插进去的那根bar

归并排序

排序算法到这里才算有点意思归并排序是算法导论中介绍分治概念时提到的基本思路是将数组拆分成子数组然后令子数组有序再令数组之间有序从而整个数组有序。

算法步骤

如果数组元素大于2则将数组分成左数组和右数组如果数组等于2则将数组转成有序数组对左数组和右数组执行1操作。

合并左数组和右数组。

log

X[iterL:]if(X[iterL]Y[iterR]):xNew.append(X[iterL])iterL

1else:xNew.append(Y[iterR])iterR

1return

Merge(MergeSort(x[:nL]),MergeSort(x[nL:]))当然这么写效率是非常低的如果像高效还是得用指针但我都已经用Python了所以就不去想效率的问题问题的关键是这种带有返回值的递归程序根本没法画图啊。

。

。

所以还是改成指针的写法

def

XL[iterL:]returnif(XL[iterL]XR[iterR]):X[i]

XL[iterL]iterL

len(X)//2MergeSort(X[:nL])MergeSort(X[nL:])Merge(X,nL)这个图。

。

怎么说呢因为在【Merge】过程中有很多bar被掩盖掉了所以可能只有画图的人能看懂吧。

。

。

希尔排序

O(n2)的排序算法又称为缩小增量排序本质上也是一种分治方案。

在归并排序中先将长度为n的数组划分为nL和nR两部分然后继续划分直到每个数组的长度不大于2再对每个不大于2的数组进行排序。

这样每个子数组内部有序而整体无序然后将有序的数组进行回溯重组直到重新变成长度为n的数组为止。

希尔排序反其道而行之在将数组划分为nL和nR后对nL和nR进行按位排序使得nL和nR内部无序但整体有序。

然后再将数组进行细分当数组长度变成1的时候内部也就谈不上无序了而所有长度为1的数组整体有序也就是说有这些子数组所组成的数组是有序的。

算法步骤

如果数组元素大于2则将数组分成左数组和右数组并对左数组和右数组的元素进行一对一地排序。

对每一个数组进行细分然后将每个子数组进行一对一排序。

def