数据结构与算法系列9--排序算法(冒泡、插入、选择)
冒泡排序
思想:
冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较,看是否满足大小关系要求。如果不满足就让它俩互换。一次冒泡会让至少一个元素移动到它应该在的位置,重复n次,就完成了n个数据的排序工作。
#优化版本
def bubbleSort(data_list):
n=len(data_list)
if n<=1:
return
for i in range(n):
flag=False#记录是否存在交换,提前退出冒泡循环的标志位
for j in range(n-1-i):
if data_list[j]>data_list[j+1]:
data_list[j],data_list[j+1]=data_list[j+1],data_list[j]
flag=True#表示有数据交换
if not flag:
#如果一趟下来没有数据交换说明已经排好序了,跳出循环
print("break")
break
aa=[5,3,7,2,9,1]
print(bubbleSort(aa))
第一,冒泡排序是原地排序算法吗?
冒泡的过程只涉及相邻数据的交换操作,只需要常量级的临时空间,所以它的空间复杂度为O(1),是一个原地排序算法。
第二,冒泡排序是稳定的排序算法吗?
在冒泡排序中,只有交换才可以改变两个元素的前后顺序。为了保证冒泡排序算法的稳定性,当有相邻的两个元素大小相等的时候,我们不做交换,相同大小的数据在排序前后不会改变顺序,所以冒泡排序是稳定的排序算法。
第三,冒泡排序的时间复杂度是多少?
最好情况下,要排序的数据已经是有序的了,我们只需要进行一次冒泡操作,就可以结束了,所以最好情况时间复杂度是O(n)。而最坏的情况是,要排序的数据刚好是倒序排列的,我们需要进行n次冒泡操作,所以最坏情况时间复杂度为O(n2)。
平均情况下的时间复杂度是O(n2)。
插入排序
思想:
首先,我们将数组中的数据分为两个区间,已排序区间和未排序区间。初始已排序区间只有一个元素,就是数组的第一个元素。插入算法的核心思想是取未排序区间中的元素,在已排序区间中找到合适的插入位置将其插入,并保证已排序区间数据一直有序。重复这个过程,直到未排序区间中元素为空,算法结束。
def insertSort(data_list):
n=len(data_list)
if n<=1:
return
#初始已排序区间只有一个元素,就是数组的第一个元素。
for i in range(1,n):
value=data_list[i]
j=i-1
#查找插入的位置,j为在有序组中的下标,由大到小递减
while j>=0:
if a[j]>values:
a[j+1]=a[j] #数据搬移
j=j-1
else:
break
data_list[j+1]=value #插入数据
第一,插入排序是原地排序算法吗?
从实现过程可以很明显地看出,插入排序算法的运行并不需要额外的存储空间,所以空间复杂度是O(1),也就是说,这是一个原地排序算法。
第二,插入排序是稳定的排序算法吗?
在插入排序中,对于值相同的元素,我们可以选择将后面出现的元素,插入到前面出现元素的后面,这样就可以保持原有的前后顺序不变,所以插入排序是稳定的排序算法。
第三,插入排序的时间复杂度是多少?
如果要排序的数据已经是有序的,我们并不需要搬移任何数据。如果我们从尾到头在有序数据组里面查找插入位置,每次只需要比较一个数据就能确定插入的位置。所以这种情况下,最好是时间复杂度为O(n)。注意,这里是从尾到头遍历已经有序的数据。如果数组是倒序的,每次插入都相当于在数组的第一个位置插入新的数据,所以需要移动大量的数据,所以最坏情况时间复杂度为O(n2)。
平均情况下的时间复杂度是 O(n2)。
选择排序
思想
选择排序算法的实现思路有点类似插入排序,也分已排序区间和未排序区间。但是选择排序每次会从未排序区间中找到最小的元素,将其放到已排序区间的末尾。
# 选择排序
def selection_sort(a: List[int]):
if len(a) <= 1: return
for i in range(len(a)):
min_index = i
min_val = a[i]
for j in range(i, len(a)):
if a[j] < min_val:
min_val = a[j]
min_index = j
a[i], a[min_index] = a[min_index], a[i]
第一,选择排序是原地排序算法吗?
是一种原地排序算法。
第二,选择排序是稳定的排序算法吗?
选择排序是一种不稳定的排序算法。从我前面画的那张图中,你可以看出来,选择排序每次都要找剩余未排序元素中的最小值,并和前面的元素交换位置,这样破坏了稳定性。
比如5,8,5,2,9这样一组数据,使用选择排序算法来排序的话,第一次找到最小元素2,与第一个5交换位置,那第一个5和中间的5顺序就变了,所以就不稳定了。正是因此,相对于冒泡排序和插入排序,选择排序就稍微逊色了。
第三,选择排序的时间复杂度是多少?
选择排序的最好情况时间复杂度、最坏情况和平均情况时间复杂度都为O(n2)。
对比:
冒泡排序和插入排序的时间复杂度都是O(n2),都是原地排序算法,为什么插入排序要比冒泡排序更受欢迎呢?
从代码实现上来看,冒泡排序的数据交换要比插入排序的数据移动要复杂,冒泡排序需要3个赋值操作,而插入排序只需要1个。看这段操作:
冒泡排序中数据的交换操作:
if (a[j] > a[j+1]) { // 交换
int tmp = a[j];
a[j] = a[j+1];
a[j+1] = tmp;
flag = true;
}
插入排序中数据的移动操作:
if (a[j] > value) {
a[j+1] = a[j]; // 数据移动
} else {
break;
}
所以,虽然冒泡排序和插入排序在时间复杂度上是一样的,都是O(n2),但是如果我们希望把性能优化做到极致,那肯定首选插入排序。
附图: