本章重点
1.快速排序
2.冒泡排序
3.希尔排序
1.快速排序
def QuickSort(myList, start, end):
# 判断start是否小于end,如果为false,直接返回
if start < end:
i, j = start, end
# 设置基准数
base = myList[i]
while i < j:
# 如果列表后边的数比基准数大或相等,则前移一位直到有比基准数小的数
while (i < j) and (myList[j] >= base):
j = j - 1
# 如找到,则把第j个元素赋值给第i个元素
myList[i] = myList[j]
# 同样的方式比较前半区
while (i < j) and (myList[i] <= base):
i = i + 1
myList[j] = myList[i]
# 做完第一轮比较之后,列表被分成了两个半区,并且i=j，此时找到基准值
myList[i] = base
# 递归前后半区
# print(base, myList)
QuickSort(myList, start, i - 1)
QuickSort(myList, j + 1, end)
return myList
myList = [7, 6, 5, 3, 12, 20, 1, 9, 11, 4, 15, 10, 8]
print("myList:",QuickSort(myList, 0, len(myList) - 1))
2.冒泡排序
1.比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2.对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
3.针对所有的元素重复以上的步骤，除了最后一个。
4.持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较
时间复杂度O(n)~O(n^2)
#1
def bubble_sort(array):
if len(array) <2:
return array
else:
num = 0
for j in range(len(array)-1):
for i in range(len(array)-1-j):
num += 1
if array[i] > array[i+1]:
mid = array[i+1]
array[i+1], array[i] = array[i], mid
print(array)
print(num)
return array
array_0 = [12, 23, 54, 32, 11, 76, 5, 73]
print(bubble_sort(array_0))
Fig1.png
#2
def bubbleSort(arr):
n = len(arr)
# 遍历所有数组元素
for i in range(n):
# Last i elements are already in place
for j in range(0, n-i-1):
if arr[j] > arr[j+1] :
arr[j], arr[j+1] = arr[j+1], arr[j]
arr = [64, 34, 25, 12, 22, 11, 90]
bubbleSort(arr)
print ("排序后的数组:")
for i in range(len(arr)):
print ("%d" %arr[i]),
Fig2.png
#3
def bubble_sort(nums):
for i in range(len(nums) - 1):
for j in range(len(nums) - i - 1):
if nums[j] > nums[j + 1]:
nums[j], nums[j + 1] = nums[j + 1], nums[j]
return nums
Fig3.png
3.希尔排序
希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。
希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录"基本有序"时，再对全体记录进行依次直接插入排序。
# 希尔排序的实质就是分组插入排序，该方法又称缩小增量排序，因DL．Shell于1959年提出而得名。
# 希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。
# 希尔排序是基于插入排序的以下两点性质而提出改进方法的：
# 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率
# 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位
网友评论