几种基础排序算法的python实现

最近发生了些事情，所以有点忙，然后心情还有点小复杂，所好久不上文章了，在这里和大家道个歉！！

！

！！

歉道完了，大家气也消了吧！下面开始讲正题了！

最近利用晚上闲下来的时间整理了一些基础的排序算法，这些排序算法一般的就是在学习数据结构的时候都是要求掌握的，作为一个开发者来说，会排序那是最基础的技能，也是最重要的技能，下面我们就一起来看看吧！

插入排序

插入排序思想：每一趟将一个待排序元素，按其排序码大小插入到前面已经排好序的一组元素的适当位置上，直到所有待排序元素元素全部插入为止

思路：

假定前i个构成的子序列是处于已排序的情况下进行排序的，然后将第i个元素与前i个构成的子序列逆序进行比较，如果是要升序排序，则比较第i个元素是否比j=i-1(i-1需要>=0)的元素大，如果是则第i个元素的位置（即j+1的位置上）保持不动，反之则将j=i-1的元素放置到i的位置，再进行第i个元素与j=i-2(i-2需要>=0)的,依次进行，如果第i个元素刚好比j=i-3大，则将第i个元素插入到j=i-2（即j+1的位置）上。

代码：

definsertion_sort(a):

l =len(a)

j =

foriinrange(1,l):

temp = a[i]

forjinrange(i -1,-1,-1):

iftemp

a[j +1] = a[j]# 则第j个元素先后移1位

else:# 如果第i个元素小于等于前i个元素中的第j个则结束循环

break

a[j +1] = temp# 将i个元素赋值给空着的位置

foriinrange(,l):

print(a[i])

快速排序

思路：

任意选取一个数据（通常选用数组的第一个数）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序。

一趟快速排序的算法是：

1）设置两个变量i、j，排序开始的时候：i=0，j=N-1；

2）以第一个数组元素作为关键数据，赋值给key，即key=A[0];

3）从j开始向前搜索，即由后开始向前搜索(j–)，找到第一个小于key的值A[j]，将A[j]和A[i]互换；

4）从i开始向后搜索，即由前开始向后搜索(i++)，找到第一个大于key的A[i]，将A[i]和A[j]互换；

5）重复第3、4步，直到i=j； (3,4步中，没找到符合条件的值，即3中A[j]不小于key,4中A[i]不大于key的时候改变j、i的值，使得j=j-1，i=i+1，直至找到为止。找到符合条件的值，进行交换的时候i， j指针位置不变。另外，i==j这一过程一定正好是i+或j-完成的时候，此时令循环结束）

代码，使用递归算法来实现：

defquick_sort(arr,low,high):

# temp = a[0]

i = low

j = high

ifi >= j:

returnarr

temp = arr[i]

whilei

whilei = temp:

j = j -1

arr[i] = arr[j]

whilei

i = i +1

arr[j] = arr[i]

arr[i] = temp

quick_sort(arr,low,i -1)

quick_sort(arr,j +1,high)

returnarr

冒泡排序

思路：

比较相邻的元素。如果第一个比第二个大，就交换他们两个。

对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。

针对所有的元素重复以上的步骤，除了最后一个。

持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

代码：

defbubble_sort(arr):

length =len(arr)

whilelength >:

foriinrange(length -1):

ifarr[i] > arr[i +1]:

arr[i] = arr[i] + arr[i +1]

arr[i +1] = arr[i] - arr[i +1]

arr[i] = arr[i] - arr[i +1]

length -=1

选择排序

思路：

每一趟从待排序的数据元素中选出最小（最大）的元素，顺序放在待排序的数列最前，直到全部待排序的数据元素全部排完。

例子：

[4, 2, 3] 找出最小的：2,与第一个元素交换

[2, 4, 3] 找出最小的：3，与第二个元素交换

[2, 3, 4]

代码：

defselection_sort(a):

forjinrange(,len(a)-1):

count = j#记录最小元素下标

#每次找出最小元素

foriinrange(j,len(a)-1):

ifa[count] > a[i+1]:

count = i+1

#python特有的交换值方法，交换最小元素和待排序元素中最前一个

a[j],a[count] = a[count],a[j]

foriinrange(,len(a)):

print(a[i])

堆排序

先介绍一下堆，堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。如下图：

思路：

将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了

堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为O(nlogn)，它也是不稳定排序。首先简单了解下堆结构。

在排序之前我们需要构造一个大顶堆，之后再使用堆排序

代码：

defadjustHead(a,i,l):

temp = a[i]#取出当前元素

k =2*i +1#从左子节点开始，即2*i+1

whilek

ifk+1

k=k+1

ifa[k] > temp:

a[i] = a[k]

i = k

else:

break

k =2*k +1#把该节点当作父节点，继续操作

a[i] = temp#将父节点值赋值给该子节点

defheap_sort(arr):

l =len(arr)

foriinrange(int(l/2-1),-1,-1):

adjustHead(arr,i,l)

# 交换堆顶和最后一个元素，并调整堆结构

forjinrange(l-1,,-1):

arr[],arr[j] = arr[j],arr[]#将堆顶元素和末尾元素进行交换

adjustHead(arr,,j)#重新对对进行调整

forkinrange(,l):

print(arr[k])

基数排序

基数排序又称为“桶子法”，从低位开始将待排序的数按照这一位的值放到相应的编号为0~9的桶中。等到低位排完得到一个子序列，再将这个序列按照次低位的大小进入相应的桶中，一直排到最高位为止，数组排序完成。

思路：

(1)遍历序列找出最大的数(为的是确定最大的数是几位数)；

(2)开辟一个与数组大小相同的临时数组tmp；

(3)用一个count数组统计原数组中某一位(从低位向高位统计)相同的数据出现的次数；

(4)用一个start数组计算原数组中某一位(从最低位向最高位计算)相同数据出现的位置；

(5)将桶中数据从小到大用tmp数组收集起来；

(6)重复(3)(4)(5)直到所有位都被统计并计算过，用tmp收集起来；

(7)将tmp数组拷回到原数组中；

代码：

importmath

defradix_sort(arr):

radix =10#基数

# k可以表示任意整数

k =int(math.ceil(math.log(max(arr),radix)))

#math.log对arr中最大的数取对数，log(max(arr),10),并对其取整得到最大值的位数

bucket =[[]foriinrange(radix)]

foriinrange(1,k+1):

forvalueinarr:

# 析取整数第k位数字（从低到高）10**2位10的二次方

bucket[int(value%(radix**i)/(radix**(i-1)))].append(value)

delarr[:]

foreachinbucket:

arr.extend(each)#桶合并

bucket = [[]foriinrange(radix)]

“可爱的萝莉等你点一下！”