网站设置搜索时间,永灿网站建设公司,网站开发完后如何上线,为女友做网站排序是每个算法工程师和开发者都需要一些知识的技能。 不仅要通过编码实现#xff0c;还要对编程本身有一般性的了解。 不同的排序算法是算法设计如何在程序复杂性#xff0c;速度和效率方面具有如此强大影响的完美展示。
让我们来看看前6种排序算法#xff0c;看看我们如何…排序是每个算法工程师和开发者都需要一些知识的技能。 不仅要通过编码实现还要对编程本身有一般性的了解。 不同的排序算法是算法设计如何在程序复杂性速度和效率方面具有如此强大影响的完美展示。
让我们来看看前6种排序算法看看我们如何在Python中实现它们
一、冒泡排序
冒泡排序是数据分析中常用的算法因为它清楚地演示了排序的工作原理同时简单易懂。 冒泡排序逐步遍历列表并比较相邻的元素对。 如果元素的顺序错误则会交换元素。 重复遍历列表的未排序部分直到列表被排序。 因为冒泡排序重复通过列表中未排序的部分所以它具有最差的On2复杂度。
def bubble_sort(arr):
def swap(i, j):
arr[i], arr[j] arr[j], arr[i]
n len(arr)
swapped True
x -1
while swapped:
swapped False
x x 1
for i in range(1, n-x):
if arr[i - 1] arr[i]:
swap(i - 1, i)
swapped True
return arr
二、选择排序
选择排序也很简单但通常优于冒泡排序。如果您在两者之间进行选择最好默认选择排序。 使用Selection排序我们将输入列表/数组分为两部分已排序的项目子列表和剩余要排序的项目子列表构成列表的其余部分。 我们首先找到未排序子列表中的最小元素并将其放在已排序子列表的末尾。 因此我们不断抓取最小的未排序元素并将其按排序子列表中的排序顺序放置。 该过程以迭代方式继续直到列表完全排序。
def selection_sort(arr):
for i in range(len(arr)):
minimum i
for j in range(i 1, len(arr)):
# Select the smallest value
if arr[j] arr[minimum]:
minimum j
# Place it at the front of the
# sorted end of the array
arr[minimum], arr[i] arr[i], arr[minimum]
return arr
三、插入排序
与冒泡排序和选择排序相比插入排序更快且可以说更简单。 有趣的是这是有多少人在玩纸牌游戏时对卡片进行排序 在每次循环迭代中插入排序从数组中删除一个元素。 然后它会在另一个已排序的数组中找到该元素所属的位置并将其插入其中。 它重复此过程直到没有输入元素。
def insertion_sort(arr, simulationFalse):
for i in range(len(arr)):
cursor arr[i]
pos i
while pos 0 and arr[pos - 1] cursor:
# Swap the number down the list
arr[pos] arr[pos - 1]
pos pos - 1
# Break and do the final swap
arr[pos] cursor
return arr
四、合并排序
合并排序是Divide and Conquer算法的完美典范。 它简单地使用了这种算法的2个主要步骤
1连续划分未排序列表直到有N个子列表其中每个子列表有1个“未排序”元素N是原始数组中元素的数量。
2反复合并即一次比较2个子列表以产生新的排序子列表直到所有元素完全合并为单个排序数组。
def merge_sort(arr):
# The last array split
if len(arr) 1:
return arr
mid len(arr) // 2
# Perform merge_sort recursively on both halves
left, right merge_sort(arr[:mid]), merge_sort(arr[mid:])
# Merge each side together
return merge(left, right, arr.copy())
def merge(left, right, merged):
left_cursor, right_cursor 0, 0
while left_cursor len(left) and right_cursor len(right):
# Sort each one and place into the result
if left[left_cursor] right[right_cursor]:
merged[left_cursorright_cursor]left[left_cursor]
left_cursor 1
else:
merged[left_cursor right_cursor] right[right_cursor]
right_cursor 1
for left_cursor in range(left_cursor, len(left)):
merged[left_cursor right_cursor] left[left_cursor]
for right_cursor in range(right_cursor, len(right)):
merged[left_cursor right_cursor] right[right_cursor]
return merged
五、快速排序
快速排序也是一种分而治之的算法。 虽然它有点复杂但在大多数标准实现中它的执行速度明显快于合并排序很少达到On²的最坏情况复杂度。 它有3个主要步骤
1我们首先从数组中选择一个数据作为基准数。
2将小于基准数的所有元素移动到基准数的左侧; 将所有大于基准数的元素移动到基准数的右侧。 这称为分区操作。
3递归地将上述两个步骤分别应用于每个元素子阵列直到其值小于和大于最后一个基准数。
def partition(array, begin, end):
pivot_idx begin
for i in xrange(begin1, end1):
if array[i] array[begin]:
pivot_idx 1
array[i], array[pivot_idx] array[pivot_idx], array[i]
array[pivot_idx], array[begin] array[begin], array[pivot_idx]
return pivot_idx
def quick_sort_recursion(array, begin, end):
if begin end:
return
pivot_idx partition(array, begin, end)
quick_sort_recursion(array, begin, pivot_idx-1)
quick_sort_recursion(array, pivot_idx1, end)
def quick_sort(array, begin0, endNone):
if end is None:
end len(array) - 1
return quick_sort_recursion(array, begin, end)
微信公众号python练手项目实战
更多机器学习算法的学习欢迎关注我们。对机器学习感兴趣的同学欢迎大家转发转载公众号文章让更多学习机器学习的伙伴加入公众号《python练手项目实战》在实战中成长。同时欢迎在公众号内留言;
