算法小结(三)：列表排序2
2021-04-14 本文已影响0人
ShowMeCoding
一、希尔排序（Shell Sort）
1、基本思路
（1）首先取一个整数d1=n/2，将元素分为d1个组，每组相邻元素距离为d1，在各组内进行直接插入排序
（2）取第二个整数d2=d1/2，重复上述分组排序过程，直到d1=1，即所有元素在同一组内进行直接插入排序
（3）希尔排序每趟并不使所有元素都有序，而是整体数据越来越接近有序；最后一趟排序使所有数据有序
2、代码实现
插入排序+希尔排序
def insert_sort_gap(li, gap):
for i in range(gap, len(li)): #i 表示摸到的牌的下标
tmp = li[i]
j = i - gap #j指的是手里的牌的下标
while j >= 0 and li[j] > tmp:
li[j+gap] = li[j]
j -= gap
li[j+gap] = tmp
def shell_sort(li):
d = len(li) // 2
while d >= 1:
insert_sort_gap(li, d)
d //= 2
return li
import random
li = [i for i in range(16)]
random.shuffle(li)
print(li)
print(shell_sort(li))
>> [5, 0, 13, 2, 6, 14, 7, 12, 15, 3, 8, 9, 10, 11, 1, 4]
>> [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
整体实现算法
def shell_sort(li):
gap = len(li) // 2
while gap > 0:
for i in range(gap, len(li)): # i表示摸到的牌的下标
tmp = li[i]
j = i - gap # j 指的是手里的牌的下标
while j >= 0 and tmp < li[j]:
li[j+gap] = li[j]
j -= gap
li[j+gap] = tmp
gap //= 2
return li
import random
li = [i for i in range(16)]
random.shuffle(li)
print(li)
print(shell_sort(li))
>> [13, 1, 3, 6, 10, 2, 15, 12, 11, 0, 8, 9, 5, 7, 4, 14]
>> [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
- 时间复杂度：O(nlogn)
- 稳定性：虽然插入排序是稳定的，但是由于希尔排序是跳跃性插入的，有可能破坏稳定性，因此不稳定。
二、计数排序（Count Sort）
1、基本思路
对列表进行排序，已知列表中的数的范围都在0到100之间，设计时间复杂度为O(n)的算法。
(1)通过遍历统计每个数出现的次数
(2)按照统计结果依次添加到列表中
2、代码实现
def count_sort(li, max_count):
count = [0 for _ in range(max_count + 1)]
for val in li:
count[val] += 1 # 实现计数,索引为原列表的值
li.clear()
for ind, val in enumerate(count): # 此处的val为原列表值的个数
for i in range(val):
li.append(ind) # 按个数添加列表的值
return li
import random
li = [i for i in range(16)]
random.shuffle(li)
print(li)
print(count_sort(li, 15)) # 列表里面的最大值为15
[0, 4, 6, 11, 3, 1, 13, 5, 9, 8, 15, 14, 10, 2, 7, 12]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
3、计数排序的主要问题
当最大数很大时(1亿)，需要占用的空间太多
三、桶排序（Bucket Sort）
1、基本思路
(1)在计数排序中，如果元素范围比较大（比如在1到1亿之间，如何改善算法？）
(2)首先将元素进行分桶，然后对每个桶中的元素进行排序
(3)之后依次在桶中取数
2、代码实现
def bucket_sort(li, n, max_num):
buckets = [[] for _ in range(n)] # 分成 n 个桶
for var in li:
i = min(var//(max_num//n), n-1) # i 表示把var放到几号桶中
buckets[i].append(var) # 把 var 放到对应的桶中
# 保持桶内的顺序,使用冒泡排序
for j in range(len(buckets[i])-1, 0, -1):
if buckets[i][j] < buckets[i][j-1]:
buckets[i][j] , buckets[i][j-1] = buckets[i][j-1], buckets[i][j]
else:
break
# 按桶装入排序
sorted_li = []
for buc in buckets:
sorted_li.extend(buc)
return sorted_li
import random
li = [random.randint(0,5) for i in range(20)]
print(li)
li = bucket_sort(li, 5, 20)
print(li)
>>[2, 2, 5, 1, 3, 4, 0, 3, 3, 4, 4, 4, 1, 0, 5, 3, 0, 3, 2, 0]
>>[0, 0, 0, 0, 1, 1, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5]
3、复杂度讨论
（1）桶排序的表现取决于数据的分布，也就是需要对不同数据排序时采取不同的分桶策略
（2）平均情况复杂度（O(n+k)）；最欢情况时间复杂度（O(n^2*k)）
（3）空间复杂度：O(k)
四、基数排序（Radix Sort）
1、基本思路
（1）多关键字排序：一个员工表，要求按照年龄进行排序，年龄相同的员工按照薪资进行排序
（2）对32,13,94,52,17,54,93进行排序，个位数和十位数
2、代码实现
def radix_sort(li):
max_num = max(li) # 最大值 9->1, 99->2, 888->3, 10000->5
it = 0
while 10**it <= max_num: # 从低位到高位依次进行比较
buckets = [[] for _ in range(10)] # 分桶
for var in li:
# 当it=1时, 987//10 =98 ; 98 % 10 = 8
# 当it=2时，987//100=9; 9 % 10=9
digit = (var//10**it)%10
buckets[digit].append(var)
# 分桶完成
li.clear()
for buc in buckets:
li.extend(buc)
# 把数重新写回li
it += 1
return li
import random
li = [random.randint(0,5) for i in range(20)]
print(li)
li = radix_sort(li)
print(li)
>>[0, 2, 1, 4, 4, 4, 4, 5, 5, 5, 5, 1, 1, 3, 0, 5, 2, 1, 4, 1]
>>[0, 0, 1, 1, 1, 1, 1, 2, 2, 3, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5]
3、复杂度讨论
（1）时间复杂度：O(kn)
（2）空间复杂度：O(k+n)
（3）k表示数字位数
五、例题实战
1、给两个字符串s和t，判断t是否是s重新排列之后组成的单词
s = "anagram", t = "nagaram", return true
s = "rat", t = "car", return false
代码1：
def isAnagram(s, t):
return sorted(list(s)) == sorted(list(t))
print(isAnagram("car", "tar"))
print(isAnagram("arrand", "raarnd"))
>>False
>>True
代码2：
def isAnagram(s, t):
dict1 = {} # {'a':1, 'b':2}
dict2 = {}
for ch in s:
dict1[ch] = dict1.get(ch, 0) + 1
for ch in t:
dict2[ch] = dict2.get(ch, 0) + 1
return dict1 == dict2
print(isAnagram("car", "tar"))
print(isAnagram("arrand", "raarnd"))
>> True
2、给定一个m*n的二维列表，查找一个元素是否都存在
每一行的列表从左到右已经排序好
每一行第一个数比上一行最后一个数大
方法1：
def search(matrix, target):
for line in matrix:
print(line)
if target in line:
return True
return False
matrix = [
[1,2,3],
[5,7,8],
[10,12,14]]
print(search(matrix, 5))
>>[1, 2, 3]
>>[5, 7, 8]
>>True
方法2：有序列表的二分查找
def search(matrix, target):
h = len(matrix) # 行数
w = len(matrix[0]) # 列数
left = 0
right = w*h - 1
while left <= right:
mid = (left + right)//2
'''
[
[0, 1, 2, 3],
[4, 5, 6, 7], 5-->(1, 1)
[8, 9, 10 ,11]]
'''
i = mid // w # 元素的行下标
j = mid % w # 元素的列下标
if matrix[i][j] == target:
return True
elif matrix[i][j] > target:
right = mid - 1
else:
left = mid + 1
else:
return False
matrix = [
[1,2,3],
[5,7,8],
[10,12,14]]
print(search(matrix, 5))
>> True
3、给定一个列表和一个整数，设计算法找到两个数的下标，使得两个数的和为给定的整数。保证肯定仅有一个结果
例如，列表[1,2,5,4]与目标整数3，1+2=3，结果为(0,1)
方法1：
def search(li, target):
for i in range(len(li)-1):
for j in range(i+1, len(li)):
if li[i] + li[j] == target:
return (i,j)
li = [1,2,5,4]
print(search(li, 3))
>>(0, 1)
方法2：当列表是有序的
def binary_search(li, left, right, val):
while left <= right:
mid = (left+right)//2
if li[mid] == val:
return mid
elif li[mid] > val:
right = mid-1
else:
left = mid+1
else:
return None
def search(nums, target):
for i in range(len(nums)):
a = nums[i]
b = target - a
if b >= a:
j = binary_search(nums, i+1, len(nums)-1, b)
else:
j = binary_search(nums, 0, i-1, b)
if j:
break
return (i+1, j+1)
nums = [1,2,3,4,5,8,10]
print(search(nums, 9))
>> (1, 6)
方法3：当列表是无序的，先进行排序之后再二分查找
def binary_search(li, left, right, val):
while left <= right:
mid = (left+right)//2
if li[mid][0] == val:
return mid
elif li[mid][0] > val:
right = mid-1
else:
left = mid+1
else:
return None
def search(nums, target):
new_nums = [[num, i] for i, num in enumerate(nums)] # 将nums的下标和数放在同一个列表中
new_nums.sort(key=lambda x: x[0]) # 按照值进行排序
for i in range(len(new_nums)):
a = new_nums[i][0]
b = target - a
if b >= a:
j = binary_search(new_nums, i+1, len(new_nums)-1, b)
else:
j = binary_search(new_nums, 0, i-1, b)
if j:
break
return sorted([new_nums[i][1], new_nums[j][1]])
nums = [1,2,3,4,12,14,5,8,10]
print(search(nums, 9))
>> [0, 7]
几种排序方法的比较
