文章目录
希尔排序算法分析时间复杂度
快速排序算法分析时间复杂度
归并排序算法分析时间复杂度
常见排序算法效率比较
希尔排序
希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。 希尔排序的基本思想是：将数组列在一个表中并对列分别进行插入排序，重复这过程，不过每次用更长的列（步长更长了，列数更少了）来进行。最后整个表就只有一列了。将数组转换至表是为了更好地理解这算法，算法本身还是使用数组进行排序。
算法分析
'''希尔排序'''
def
shell_sort(alist
):
n
= len(alist
)
# gap为步长，选择gap值的元素进行判断
gap
= n
#gap值减少为
1时，外部循环停止
while gap
> 0:
# 按步长进行插入排序
for j
in range(gap
, n
):
#第一层的数据进行排序后，然后下一层的值为gap
+1位置的值
i
= j
# 将gap位置的值与前gap的值相比较，进行排序
while i
>0:
if alist
[i
]<alist
[i
-gap
]:
alist
[i
],alist
[i
- gap
] =alist
[i
- gap
],alist
[i
]
i
-= gap
else:
break
# 得到新的步长
gap
= gap
li
= [11,13,5,7,20]
a
=[11,13,5,33,4,17,7,20,9,15,10,50]
shell_sort(li
)
print(li
)
shell_sort(a
)
print(a
)
时间复杂度
最优时间复杂度：根据步长序列的不同而不同 最坏时间复杂度：O(n^2) 稳定想：不稳定
快速排序
快速排序（英语：Quicksort），又称划分交换排序（partition-exchange sort），通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
算法分析
"""快速排序"""
def
quick_sort(alist
, start
, end
):
# 递归的退出条件
if start
>= end
:
return
# 设定起始元素为要寻找位置的基准元素
mid
= alist
[start
]
# low为序列左边的由左向右移动的游标
low
= start
# high为序列右边的由右向左移动的游标
high
= end
len(alist
)
while low
< high
:
# 如果low与high未重合，high指向的元素不比基准元素小，则high向左移动
while low
< high and alist
[high
] >= mid
:
high
-= 1
# 将high指向的元素放到low的位置上
alist
[low
] = alist
[high
]
# 如果low与high未重合，low指向的元素比基准元素小，则low向右移动
while low
< high and alist
[low
] < mid
:
low
+= 1
# 将low指向的元素放到high的位置上
alist
[high
] = alist
[low
]
# 退出循环后，low与high重合，此时所指位置为基准元素的正确位置
# 将基准元素放到该位置
alist
[low
] = mid
# 对基准元素左边的子序列进行快速排序
quick_sort(alist
, start
, low
-1)
# 对基准元素右边的子序列进行快速排序
quick_sort(alist
, low
+1, end
)
alist
= [20,13,5,7,11,30,3,65,45]
quick_sort(alist
,0,len(alist
)-1)
print(alist
)
时间复杂度
最优时间复杂度：O(nlogn) 最坏时间复杂度：O(n^2) 稳定性：不稳定
归并排序
归并排序是采用分治法的一个非常典型的应用。归并排序的思想就是先递归分解数组，再合并数组。 将数组分解最小之后，然后合并两个有序数组，基本思路是比较两个数组的最前面的数，谁小就先取谁，取了后相应的指针就往后移一位。然后再比较，直至一个数组为空，最后把另一个数组的剩余部分复制过来即可。
算法分析
最后的算法原理分析一样，因此就写了一部分
def
merge_sort(alist
):
if len(alist
) <= 1:
return alist
# 二分分解
num
= len(alist
)
left
= merge_sort(alist
[:num
])
right
= merge_sort(alist
[num
:])
# 合并
return merge(left
,right
)
def
merge(left
, right
):
'''合并操作，将两个有序数组left[]和right[]合并成一个大的有序数组'''
#left与right的下标指针
l
, r
= 0, 0
result
= []
while l
<len(left
) and r
<len(right
):
if left
[l
] < right
[r
]:
result
.append(left
[l
])
l
+= 1
else:
result
.append(right
[r
])
r
+= 1
result
+= left
[l
:]
result
+= right
[r
:]
return result
alist
= [54,26,93,17,77,31,44,55,20]
sorted_alist
= merge_sort(alist
)
print(sorted_alist
)
时间复杂度
最优时间复杂度：O(nlogn) 最坏时间复杂度：O(nlogn) 稳定性：稳定
常见排序算法效率比较
