python-数据结构与算法- 面试常考排序算法题-快排-冒泡-
2019-04-15 本文已影响0人
Jayce_xi
算法可视化网站推荐---->visualgo
0.面试题中的排序算法
一些排序算法可能在工作中用的会比较少，但是面试却是不得不面对的问题。算法有助于提高我们对数据结构的理解以及提高自己的逻辑能力，没事刷刷真的不错。
1.快排
面试最推荐而且也是写的最多的
快排的思路是分而治之，相当于我每次去将一个数归为，直到所有的数都归为了，那么这个排序也就成功了。
快排第一种思路：（这个思路参考下，不要写）
| 平均时间复杂度 | 最好时间复杂度 | 最坏时间复杂度 | 空间复杂度 | 排序方式 |
|---|---|---|---|---|
| O(nlogn) | O(nlogn) | O(n2) | O(nlogn) | in-place |
import random
def quickSort(nums): # 这种写法的平均空间复杂度为 O(nlogn),时间复杂度为O(nlogn)
if len(nums) <= 1:
return nums
mid = nums[0] # 基准值
left = [nums[i] for i in range(1, len(nums)) if nums[i] < mid]
right = [nums[i] for i in range(1, len(nums)) if nums[i] >= mid]
return quickSort(left) + [mid] + quickSort(right)
li = list(range(100))
random.shuffle(li)
print(li)
print(quickSort(li))
这个利用到了递归，分而治之，但是这个算法的空间复杂度较高，有可以优化的点。在做算法题的时候，对于列表字典这些可变数据结构，一定要明白如何去利用这些数据结构本身的内存而不是再去开辟很多新的内存。
快排第二种思路：
| 平均时间复杂度 | 最好时间复杂度 | 最坏时间复杂度 | 空间复杂度 | 排序方式 |
|---|---|---|---|---|
| O(nlogn) | O(nlogn) | O(n2) | O(log) | in-place |
import random
class Solution(object):
"""
快排
时间复杂度为O(nlogn),最差情况为O(n2)
空间复杂度为O(logn)
"""
def partition(self, li: list, left, right):
tmp = li[left]
while left < right:
while left < right and li[right] >= tmp:
right -= 1
li[left] = li[right]
while left < right and li[left] <= tmp:
left += 1
li[right] = li[left]
li[left] = tmp
return left
def quick_sort(self, li, left, right):
if left < right:
mid = self.partition(li, left, right)
self.quick_sort(li, left, mid - 1)
self.quick_sort(li, mid + 1, right)
li = list(range(100))
random.shuffle(li)
print(li)
solution = Solution()
print(solution.quick_sort(li, 0, len(li) - 1))
print(li)
与第一种方法不同的点就是在于对空间的利用，利用了li本身的内存空间。
- 写在同一个函数里
如何把他们写在同一个函数里并且有一个new idea，在找到两边各一个不属于各自位置的值后，进行交换。
def quick_sort(li, start, end):
if start >= end:
return
left, right = start, end
tmp = li[left]
while left < right:
# 设置一个基准点
while left < right:
while left < right and li[right] >= tmp: # 至少要一个等号，不然会出现死循环
right -= 1
li[left] = li[right]
while left < right and li[left] <= tmp: # 因为如果没有一边有等号，当列表中有两个相同值的时候，就无法跳出循环
left += 1
li[right] = li[left]
li[left] = tmp
quick_sort(li, start, left - 1)
quick_sort(li, left + 1, end)
if __name__ == '__main__':
import random
li = list(range(100))
li.append(55)
random.shuffle(li)
print(li)
print(quick_sort(li, 0, 99))
print(li)
- 顺便把参数数量也降低一下：
def quick_sort(li):
def _quick_sort(li, start, end):
if start >= end:
return
left, right = start, end
tmp = li[left]
while left < right:
# 设置一个基准点
while left < right:
while left < right and li[right] >= tmp: # 至少要一个等号，不然会出现死循环
right -= 1
li[left] = li[right]
while left < right and li[left] <= tmp: # 因为如果没有一边有等号，当列表中有两个相同值的时候，就无法跳出循环
left += 1
li[right] = li[left]
li[left] = tmp
_quick_sort(li, start, left - 1)
_quick_sort(li, left + 1, end)
_quick_sort(li, 0, len(li)-1)
2.冒泡排序
| 平均时间复杂度 | 最好时间复杂度 | 最坏时间复杂度 | 空间复杂度 | 排序方式 |
|---|---|---|---|---|
| O(n2) | O(n) | O(n2) | O(1) | in-place |
理解的关键点在于左半部分是有序区。
冒泡作为最简单的排序算法之一，面试的时候万不得已（其他的都记不住了），还是不要写。写个快排能好多了。
import random
class Solution(object):
"""
冒泡排序
"""
@staticmethod
def bubble_sort(li):
for i in range(len(li) - 1): # 交换的次数
flag = True # flag的作用是当这个序列就是一个升序（这边排的是升序），那么久可以降低时间复杂度到O(n)
for j in range(len(li) - i - 1): # 剩余需要交换的元素
if li[j] > li[j + 1]:
li[j], li[j + 1] = li[j + 1], li[j]
flag = False
if flag:
return li
return li
li = list(range(100))
random.shuffle(li)
print(li)
solution = Solution()
solution.bubble_sort(li)
print(li)
3.选择排序
| 平均时间复杂度 | 最好时间复杂度 | 最坏时间复杂度 | 空间复杂度 | 排序方式 |
|---|---|---|---|---|
| O(n2) | O(n2) | O(n2) | O(1) | in-place |
选择排序主要需要注意点是左边部分是有序区。
也不推荐写，时间复杂度高，效率低，太简单了。
import random
class Solution(object):
"""
选择排序
"""
def select_sort(self, li):
for i in range(len(li) - 1):
min_pos = i
for j in range(i+1, len(li)): # 左部分是有序区
if li[min_pos] > li[j]:
min_pos = j
li[i], li[min_pos] = li[min_pos], li[i]
return li
li = list(range(100))
random.shuffle(li)
print(Solution().select_sort(li))
4.插入排序
插入排序如同打扑克一样，每次将后面的牌插到前面已经排好序的牌中。使得左半部分为有序区域。
| 平均时间复杂度 | 最好时间复杂度 | 最坏时间复杂度 | 空间复杂度 | 排序方式 |
|---|---|---|---|---|
| O(n2) | O(n2) | O(n2) | O(1) | in-place |
import random
def insert_sort(li):
for i in range(1, len(li)):
# i 表示趟数 还表示摸到牌的位置
j = i - 1 # 取到摸到牌的前一张,也就是有序位置的最后一张牌
tmp = li[i]
while j >= 0 and li[j] > tmp:
# 两个终止条件： 1. j==-1 2. j位置的值小于等于tmp
li[j + 1] = li[j]
j -= 1
li[j + 1] = tmp
li = list(range(10000))
random.shuffle(li)
insert_sort(li)
print(li)
5.堆排序（Heap Sort）
import random
def sift(li, low, high):
"""
堆调整程序
:param li:
:param low:
:param high:
:return:
"""
tmp = li[low]
i = low
j = 2 * i + 1
while j <= high: # 第一个退出条件：j不存在
if j + 1 <= high and li[j + 1] > li[j]: # 如果右孩子存在并且右孩子比左孩子大
j += 1 # j指向右孩子
if li[j] > tmp:
li[i] = li[j]
i = j
j = 2 * i + 1
else: # 第二个退出条件：j位置的值比tmp小
break
li[i] = tmp
def heap_sort(li):
# 1. 建堆
n = len(li)
for i in range(n // 2 - 1, -1, -1): # i表示遍历的low
sift(li, i, n - 1) # low:i high:统一写成最后一个位置对正确性没有影响
# 2. 挨个出数：退休 棋子 调整
for i in range(n - 1, 0, -1): # i 表示当前位置堆的high
li[i], li[0] = li[0], li[i]
sift(li, 0, i - 1)
# print(li)
li = list(range(100000))
random.shuffle(li)
heap_sort(li)
print(li)
6.二分查找
二分查找非常简单，是建立在列表有序的情况下，利用二分法不断逼近目标值的。
def binary_search(li, target):
left = 0
right = len(li) - 1
while left <= right:
mid = (right - left) // 2 # 取一个中间值
if target > li[mid]:
left = mid + 1 # 如果比目标值比中位值还要大，调整右边界指针
elif target < li[mid]:
right = mid - 1 # 如果比目标值比中位值要小，调整左边界指针
else:
return mid
return -1
算法的稳定性
选择排序、快速排序、希尔排序、堆排序不是稳定的排序算法，而冒泡排序、插入排序、归并排序和基数排序是稳定的排序算法
