几种排序算法

1.直接插入排序，按升序排原理代码 2.直接选择排序，按升序排原理代码 3.希尔排序原理实例代码 4.冒泡排序原理实例代码 5.快速排序原理代码

1.直接插入排序，按升序排

原理

用两个for循环，外面的for循环是用来确定待插入有序序列的元素，里面的for循环是用来查找该元素插入的位置

首先要先找到应该插入的位置，然后将该位置后的元素后移，再将该元素插入到该位置，这样一次操作之后，该结点前的列表就是一个有序表了

直到将所有的元素都插入完，那么就是一个有序表了

代码

lst1=[15,26,17,36,54,8,3,12] def zhijiecharu(lst): for i in range(len(lst)): enum=lst[i] for j in range(len(lst[0:i])): if lst[i] < lst[j]: lst[j+1:i+1]=lst[j:i] lst[j]=enum break return lst print("直接插入排序的结果为：",zhijiecharu(lst1))

运行结果：

2.直接选择排序，按升序排

原理

将序列分为待排序和已排序的序列，已排序的序列放在最前面

每一次都会从待排序的序列找到最大/最小值，加入到已排序序列的最后/最前面的位置

代码

def choice_sort(lst): for i in range(len(lst)): min1=min(lst[i:]) ind = lst.index(min1) lst[i],lst[ind]=min1,lst[i] return lst print("直接选择排序的结果为：",choice_sort(lst))

运行结果为：

3.希尔排序

原理

将序列分组，每次分组的大小为列表长度除2.然后在组内将元素进行直接插入排序

实例

例如：有序列：36 25 48 12 65 25 43 58 76 32

第一次分组并排序后的序列为： 分组(d=5)：有5个组，每组的内容为：[36,25],[25,43],[48,58],[12,76],[65,32]

组内直接插入排序后： 25 25 48 12 32 36 43 58 76 65

第二次分组并排序后的序列为： 分组(d=2)：有2个组，每组的内容为：[25,48,32,43,76],[25,12,36,58,65]

组内直接插入排序后： 25 12 32 25 43 36 48 58 76 65

第二次分组并排序后的序列为： 分组(d=1)：有10个组

组内直接插入排序后： 12 25 25 32 36 43 48 58 65 76

代码

def shell_sort(list): n = len(list) # 初始步长 gap = n // 2 #每次分组的长度 while gap > 0: for i in range(gap, n): # 每个步长进行插入排序 temp = list[i] j = i # 插入排序 while j >= gap and list[j - gap] > temp: list[j] = list[j - gap] j -= gap list[j] = temp # 得到新的步长 gap = gap // 2 return list print("希尔排序后的序列为：",shell_sort(lst1))

运行结果为：

4.冒泡排序

原理

用两个for循环，最外层的for循环，用来控制冒泡的次数，里面的for循环，用来控制每一趟冒泡需要比较的次数。

冒泡的次数应该是数组长度-1，每一趟比较的次数是冒泡次数-1

实例

假设有数组：[53,2,6,4,753,23]

第一次冒泡：

用第一个元素53，去和后面所有的元素进行比较，如果前一个数比后一个数大，就进行对换。53>2,将53与2对换、所以第一次冒泡的第一次比较之后数组为[2,53,6,5,753,23]，第二次比较53和6，因为53>6,进行对换[2,6,53,5,753,23]… 直到比较到最后一个数，此时的数组为：[2,6,5,53,23,753] 可以看到，冒泡一次之后，数组中最大的元素就已经到最后一个了，依次类推，第二次冒泡就将除最后一个元素之外的最大值放在了倒数第二个

第二次冒泡之后：[2,6,5,23,53,753] 第三次冒泡之后：[2,6,5,23,53,753] 第四次冒泡之后：[2,5,6,23,53,753] 第五次冒泡之后：[2,5,6,23,53,753] 此时已经结束了，因为只需要冒泡n-1次，假设有2个数，则只需要比较1次，就可以得到大小。

代码

def maopao(lst): for i in range(0,len(lst)-1): #比较趟数，需要比较n-1, max=lst[0]; for j in range(1,len(lst)-i): #每趟比较次数，n-1次 if max>lst[j]: lst[j-1],lst[j]=lst[j],lst[j-1] #进行互换 max = lst[j]; return lst

运行结果为：

5.快速排序

原理

先取左边第一个数作为基准值，用两个指针去记录元素，从最右边的指针开始进行比较，如果值比基准值小，就将其值和左边指针对应的元素进行对换，然后从左边开始进行比较，将元素值大于基准值的元素和右指针对应的元素进行对调，一直到左右指针之间没有元素为止，再将基准值放在两个指针中间，这样进行一趟比较之后，基准值左边的都是比基准值小的序列，右边的都是基准值大的序列

然后对左右序列再进行快排序

代码

def kuaipai(list, left, right): if left >= right: #判断下标值 return list jz = list[left]# 将左边第一位定位基准数，以此数将序列分为两部分 min = left #开始进行搜索 max = right while left != right: while left < right :# 从最右边开始查，找到第一个比基准值小的数 if list[right] >= jz: right -= 1 else:# 从最左边开始查，查找比基准值大的数 list[left] = list[right] left += 1 list[right] = list[left] list[right] = jz #递归调用 kuaipai(list, min, left - 1) kuaipai(list, left + 1, max) return list lst=[13451,24,1234,23,34,43,23] print(kuaipai(lst,0,len(lst)-1))

运行结果为：