最新消息:XAMPP默认安装之后是很不安全的,我们只需要点击左方菜单的 "安全"选项,按照向导操作即可完成安全设置。

python代码实现_冒泡排序,选择排序,插入排序,快速排序

XAMPP案例 admin 43浏览 0评论

Python排序算法_冒泡排序,选择排序,插入排序,快速排序的python实现

CA0074

1.冒泡排序

每轮循环中依次比较相邻两个数的大小,交换元素顺序使得大的值往后移动,时间复杂度O(n2)

#冒泡排序def BubbleSort(array):    for i in range(len(array)-1):        for j in range(len(array)-i-1):            if array[j]>array[j+1]:                array[j+1],array[j]=array[j],array[j+1]    return array 

2.选择排序

每轮循环中比较所有的元素,每次都选择出该轮循环最小的值放在左边,从左至右升序排列,时间复杂度为O(n2)

def SelectionSort(array):    for i in range(len(array)-1):        for j in range(i+1,len(array)):            if array[j]<array[i]:                array[i],array[j]=array[j],array[i]    return array

3.插入排序

每轮循环中,比较相邻的数,将小的数插入到大的数的前面,时间复杂度为O(n2)

#插入排序def InsertSort(array):    for i in range(1,len(array)):        pos=i        temp=array[pos]        while pos>0 and array[pos-1]>array[pos]:            array[pos]=array[pos-1]            array[pos-1]=temp             pos=pos-1    return array

4.快速排序

随机选择中轴值(例如每次选择该区中的第一个元素为中轴值),将数组分区,比中轴值小的元素排在左边,比中轴值大的排在右边,在各子区按以上方法重复分区,最终的子区中将会有1个元素或0个元素(基准情形),完成排序。时间复杂度为O(nlogn)/相同元素排序代码会无限递归,已发文更正

#快速排序:def quicksort(array):    if len(array)<2:        return array    else:        pivot=array[0]        less=[x for x in array if x <= pivot]        more=[x for x in array if x > pivot]        return quicksort(less)+[pivot]+quicksort(more)

排序算法的稳定性

1.稳定:当A=B,元素A原本在B前面,排序完成后A仍然在B的前面。

2.不稳定:当A=B,A原本在B的前面,排序之后A可能会出现在B的后面。

冒泡排序和插入排序,比较元素时均为相邻比较,因此不会出现同值元素位置互换;选择排序,在某一轮比较时可能出现元素之间跳跃交换,因此不稳定;快速排序的中轴值选定后,以以上代码为例,原本在中轴值右边的同值元素会分到左区,因此不稳定。总结如下表:

排序方法 时间复杂度 稳定性
冒泡排序 O(n2) 稳定
选择排序 O(n2) 不稳定
插入排序 O(n2) 稳定
快速排序 O(nlogn) 不稳定

1.冒泡排序

每轮循环中依次比较相邻两个数的大小,交换元素顺序使得大的值往后移动,时间复杂度O(n2)

#冒泡排序def BubbleSort(array):    for i in range(len(array)-1):        for j in range(len(array)-i-1):            if array[j]>array[j+1]:                array[j+1],array[j]=array[j],array[j+1]    return array 

2.选择排序

每轮循环中比较所有的元素,每次都选择出该轮循环最小的值放在左边,从左至右升序排列,时间复杂度为O(n2)

def SelectionSort(array):    for i in range(len(array)-1):        for j in range(i+1,len(array)):            if array[j]<array[i]:                array[i],array[j]=array[j],array[i]    return array

3.插入排序

每轮循环中,比较相邻的数,将小的数插入到大的数的前面,时间复杂度为O(n2)

#插入排序def InsertSort(array):    for i in range(1,len(array)):        pos=i        temp=array[pos]        while pos>0 and array[pos-1]>array[pos]:            array[pos]=array[pos-1]            array[pos-1]=temp             pos=pos-1    return array

4.快速排序

随机选择中轴值(例如每次选择该区中的第一个元素为中轴值),将数组分区,比中轴值小的元素排在左边,比中轴值大的排在右边,在各子区按以上方法重复分区,最终的子区中将会有1个元素或0个元素(基准情形),完成排序。时间复杂度为O(nlogn)/相同元素排序代码会无限递归,已发文更正

#快速排序:def quicksort(array):    if len(array)<2:        return array    else:        pivot=array[0]        less=[x for x in array if x <= pivot]        more=[x for x in array if x > pivot]        return quicksort(less)+[pivot]+quicksort(more)

排序算法的稳定性

1.稳定:当A=B,元素A原本在B前面,排序完成后A仍然在B的前面。

2.不稳定:当A=B,A原本在B的前面,排序之后A可能会出现在B的后面。

冒泡排序和插入排序,比较元素时均为相邻比较,因此不会出现同值元素位置互换;选择排序,在某一轮比较时可能出现元素之间跳跃交换,因此不稳定;快速排序的中轴值选定后,以以上代码为例,原本在中轴值右边的同值元素会分到左区,因此不稳定。总结如下表:

排序方法 时间复杂度 稳定性
冒泡排序 O(n2) 稳定
选择排序 O(n2) 不稳定
插入排序 O(n2) 稳定
快速排序 O(nlogn) 不稳定

转载请注明:XAMPP中文组官网 » python代码实现_冒泡排序,选择排序,插入排序,快速排序