冒泡排序
思想:
- 比较相邻的元素。如果第一个比第二个大,就交换它们两个;
- 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对,这样在最后的元素应该会是最大的数;
- 针对所有的元素重复以上的步骤,除了最后一个;
- 重复步骤1~3,直到排序完成。
在相邻元素相等时,它们并不会交换位置,冒泡排序是稳定排序。
代码
# O(n^2)复杂度
def bubbleSort(arr):
for i in range(1, len(arr)):
for j in range(0, len(arr) - i):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
return arr
if __name__ == '__main__':
print(bubbleSort([134, 234, 34, 44, 5567, 564, 6, 78, 3, 32, 2, 3456, 5]))
插入排序
思想
直接插入排序O(n^2^) 稳定排序算法,适合于基本有序的情况,无序且n较大时,复杂度高。
- 将第1个数作为已排好的序列,从第i=2个数开始,每次判断要将r[i]插入到已排好序列的第几个位置(使用顺序查找法)。
- 每查找一个,不满足插入位置,就逐个后移, 为避免数组越界,可以在 r[0] 处暂存待插入的数据。
代码
# O(n^2)复杂度
def InsertSort(arr):
for i in range(1, len(arr) - 1):
for j in range(i):
if arr[i + 1] < arr[j]:
arr.insert(j, arr.pop(i + 1))
return arr
a = [134, 234, 34, 44, 5567, 564, 6, 78, 3, 32, 2, 3456, 5]
print(InsertSort(a))
选择排序
思想
- 在未排序序列中找到最小(大)元素,存放到排序序列的起始位置
- 从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。
- 重复第二步,直到所有元素均排序完毕。
代码
# O(n^2)复杂度
def SelectSort(arr):
for i in range(len(arr)):
min_pos = i
for j in range(i, len(arr)):
if arr[j] < arr[min_pos]:
min_pos = j
arr.insert(i, arr.pop(min_pos))
# print(arr)
return arr
a = [134, 234, 34, 44, 5567, 564, 6, 78, 3, 32, 2, 3456, 5]
print(SelectSort(a))
归并排序
思想
- 设定两个指针,最初位置分别为两个已经排序序列的起始位置;
- 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置;
- 重复步骤3
- 直到某一指针达到序列尾;
- 将另一序列剩下的所有元素直接复制到合并序列尾。
代码
def MergeSort(arr):
if len(arr) == 1:
return arr
else:
arr1, arr2 = MergeSort(arr[:len(arr) // 2]), MergeSort(arr[len(arr) // 2:])
arr1_pos = 0
arr2_pos = 0
new_arr = []
while True:
if arr1_pos >= len(arr1):
for i in range(arr2_pos, len(arr2)):
new_arr.append(arr2[i])
break
elif arr2_pos >= len(arr2):
for i in range(arr1_pos, len(arr1)):
new_arr.append(arr1[i])
break
elif arr1[arr1_pos] < arr2[arr2_pos]:
new_arr.append(arr1[arr1_pos])
arr1_pos += 1
else:
new_arr.append(arr2[arr2_pos])
arr2_pos += 1
return new_arr
print(MergeSort([134, 234, 34, 44, 5567, 564, 6, 78, 3, 32, 2, 3456, 5]))
快速排序
思路
1.先从数列中取出一个数作为基准数。
2.分区过程,将比这个数大的数全放到它的右边,小于或等于它的数全放到它的左边。
3.再对左右区间重复第二步,直到各区间只有一个数。
代码
# O(nlog(n))复杂度
def QuickSort(arr, low, high):
if high - low == 1:
if arr[high] < arr[low]:
arr[high], arr[low] = arr[low], arr[high]
return
return
if low < high:
standard = arr[low]
start_pos = low
end_pos = high
low += 1
while True:
while arr[high] > standard and low != high:
high -= 1
while arr[low] < standard and low != high:
low += 1
if low == high:
break
arr[high], arr[low] = arr[low], arr[high]
arr[start_pos], arr[low] = arr[low], arr[start_pos]
QuickSort(arr, start_pos, low - 1)
QuickSort(arr, low + 1, end_pos)
a = [134, 234, 34,34, 44, 5567, 454, 564, 6, 78, 3, 32, 2, 3456, 5]
QuickSort(a, 0, len(a) - 1)
print(a)
希尔排序
思路
- 选择一个增量序列 t1,t2,……,tk,其中 ti > tj, tk = 1;
- 按增量序列个数 k,对序列进行 k 趟排序;
- 每趟排序,根据对应的增量 ti,将待排序列分割成若干长度为 m 的子序列,分别对各子表进行直接插入排序。仅增量因子为 1 时,整个序列作为一个表来处理,表长度即为整个序列的长度。
代码
# 时间复杂度O(n^(3/2))
def ShellSort(arr: list):
gap = len(arr) // 2
while True:
for j in range(gap): # 对于gap所分的每一个组
for i in range(j + gap, len(arr), gap): # 进行插入排序
tmp = arr[i]
pos = i
for k in range(i - gap, -1, -gap):
if arr[k] > tmp:
arr[k + gap] = arr[k]
pos = k
arr[pos] = tmp
if gap == 1:
break
gap = int(gap / 2)
a = [134, 234, 34, 44, 5567, 564, 6, 78, 3, 32, 2, 3456, 5]
ShellSort(a)
print(a)
堆排序
思想
- 创建一个堆;
- 把堆首(最大值)和堆尾互换;
- 把堆的尺寸缩小 1,把新的数组顶端数据调整到相应位置;
- 重复步骤 2,直到堆的尺寸为 1。
代码
# 时间复杂度O(n^(3/2))
def HeapSort(arr):
length = len(arr)
while True:
for i in range(length // 2 - 1, -1, -1):
switch(arr, i, length)
arr[0], arr[length - 1] = arr[length - 1], arr[0]
length -= 1
if length == 0:
break
def switch(arr, pos, length):
left = pos * 2 + 1
right = pos * 2 + 2
if left < length and arr[left] > arr[pos]:
arr[pos], arr[left] = arr[left], arr[pos]
if right < length and arr[right] > arr[pos]:
arr[pos], arr[right] = arr[right], arr[pos]
a = [134, 234, 34, 44, 5567, 564, 6, 78, 3, 32, 2, 3456, 5]
HeapSort(a)
print(a)
Comments | NOTHING