面试-排序-交换排序
一、交换排序:两两比较待排序的关键字,并交换不满足次序要求的那些偶对,直到全部满足为止。
常见的交换排序有冒泡排序和快速排序
1.冒泡排序
1)过程:比较相邻元素,使关键字较小的元素交换至关键字较大的元素之上,使得经过一次冒泡排序后,关键字最小的元素到达最顶端,接着找到第二小的元素,依次类推。
冒泡排序示意图
2)python实现:
def sort1(a):
length = len(a) - 1
exchange = True
while length >= 1 and exchange:
exchange = False
for i in range(length):
if a[i] > a[i + 1]:
a[i], a[i + 1] = a[i + 1], a[i]
exchange = True
length -= 1
return a
3)复杂度
空间复杂度:O(1)
时间复杂度:
平均 O( )
最好 O(n) :初始数据序列正序时
最坏 O( ) :初始数据序列反序时
2.快速排序:是由冒泡排序改进得来的
1)过程:在待排序的n个元素中任取一个元素(一般取第一个元素),把该元素放入最终位置后,整个数据区间被此元素分割成两个子区间。所有关键字比该元素小的放在前子区间,所有比它大的放在后子区间,并把该元素排在这两个子区间的中间,这个过程称作一趟快排。然对两个子区间重复上述过程,直至每个子区间只有一个元素为止。
快速排序示意图
2)python实现:
def sort2(a, low, high):
if low >= high:
return
i, j = low, high
tmp = a[low]
while i < j:
while i < j and a[j] > tmp:
j -= 1
a[i] = a[j]
while i < j and a[i] <= tmp:
i += 1
a[j] = a[i]
a[i] = tmp#最后i,j指向同一个元素
#递归前后半区
sort2(a, low,i-1)
sort2(a,j+1,high)
return a
3)复杂度
空间复杂度:O(log2n)
时间复杂度:
平均 O(nlog2n)
最好 O(nlog2n) :当数据随机分布时,快排性能越好
最坏 O( ) :当数据接近有序时,快排效率最低