文章目录

• 一、一些比较常用的方法
• 二、二分查找以及几种经典的排序算法
• • 二分查找
  • 冒泡排序
  • 选择排序
  • 快速排序
  • 堆排序
  • 有关堆排序的topk问题
  • 归并排序

一、一些比较常用的方法

一、列表
1、li.append() #添加元素到末尾，返回none
2、li.clear() #一个比较危险的方法(QAQ)
3、li.copy() #复制 不是同一个对象（内存地址不一样）
4、li.count() #计算列表里的元素出现的次数
5、li.extend([]) #可迭代的参数
6、li.index() #默认返回元素第一次出现的位置，可以添加查找范围
7、liinsert() #指定索引插入元素
8、li.pop() #默认删除最后一个元素，可以指定索引删除
9、li.remove() #指定删除
10、li.reverse() #反向列表元素
11、li.sort() #默认ASCII码排序，按照首字母大小排序
按长度排序
li.sort(key=len) 由短到长
li.sort(key=len,reverse=True) 由长到短
归纳总结
与增加元素有关的方法
1、li.append #添加元素到末尾，返回none
2、li.extend([]) #可迭代的参数
3、liinsert() #指定索引插入元素
与减少元素有关的方法
1、li.clear() #一个比较危险的方法(QAQ)
2、li.pop() #默认删除最后一个元素，可以指定索引删除
3、li.remove() #指定删除
与查找，统计，调整列表有关的方法
1、li.count() #计算列表里的元素出现的次数
2、li.index() #默认返回元素第一次出现的位置，可以添加查找范围
3、li.reverse() #反向列表元素
4、li.sort() #默认ASCII码排序，按照首字母大小排序
5、li.copy() #复制 不是同一个对象（内存地址不一样）

二、二分查找以及几种经典的排序算法

二分查找

二分查找只适用于排好序的列表，对于无序列表不适用，可以先进行排序再进行查找，（当然如果需要的话）

def binary_search(li, val):left = 0right = len(li) - 1while left <= right:mid = (left + right) // 2if li[mid] == val:return midelif li[mid] < val:left = mid + 1else:right = mid - 1else:return Noneli = [1, 2, 3, 4, 5, 6, 7, 8, 9]
print(binary_search(li, 6))

在这些排序中，冒泡排序、选择排序、插入排序相对来说就比较low，通常时间复杂度比较高；相比而言，堆排序、归并排序、快速排序的时间复杂都就比较小，而且这三种也比较常用；当然还有几种排序算法，比如桶排序、希尔排序、计数排序、基数排序，这四种一般都不是很常用；
对于常见的六种排序算法来说，冒泡排序、归并排序、插入排序是比较稳定的，其他三种都不太稳定（这里的稳定性判定是由是否跳跃式的排序来判断）

冒泡排序

import randomdef bubble_sort(li):for i in range(len(li) - 1):exchange = Falsefor j in range(len(li) - 1 - i):if li[j] > li[j + 1]:li[j], li[j + 1] = li[j + 1], li[j]exchange = Trueprint(li)if not exchange:returnli = [random.randint(0, 100) for i in range(10)]
print(li)
bubble_sort(li)

选择排序

def select_sort(li):for i in range(len(li) - 1):min_loc = ifor j in range(i + 1, len(li)):if li[j] < li[min_loc]:min_loc = jli[i], li[min_loc] = li[min_loc], li[i]li = [3, 1, 4, 7, 9, 2, 6, 8, 5]
select_sort(li)
print(li)

快速排序

def partition(li, left, right):tmp = li[left]while left < right:while left < right and li[right] > tmp:right -= 1li[left] = li[right]while left < right and li[left] < tmp:left += 1li[right] = li[left]li[left] = tmpreturn leftdef quick_sort(li, left, right):if left < right:mid = partition(li, left, right)quick_sort(li, left, mid - 1)quick_sort(li, mid + 1, right)print(li)li = [5, 3, 9, 8, 6, 2, 7, 4, 1]
print(li)
quick_sort(li, 0, len(li) - 1)

堆排序

def sift(li, low, high):i = lowj = 2 * i + 1tmp = li[low]while j <= high:if j + 1 <= high and li[j + 1] > li[j]:j = j + 1if tmp < li[j]:li[i] = li[j]i = jj = 2 * i + 1else:li[i] = tmpbreakelse:li[i] = tmpdef heap_sort(li):n = len(li)for i in range((n - 2) // 2, -1, -1):sift(li, i, n - 1)for i in range(n - 1, -1, -1):li[0], li[i] = li[i], li[0]sift(li, 0, i - 1)li = [2, 4, 7, 1, 3, 9, 0, 6, 5, 8]
print(li)
heap_sort(li)
print(li)

有关堆排序的topk问题

import randomfrom 算法.sift import siftdef topk(li, k):heap = li[0:k]for i in range((k - 2) // 2, -1, -1):sift(heap, i, k - 1)for i in range(k, len(li) - 1):if li[i] > heap[0]:heap[0] = li[i]sift(heap, 0, k - 1)for i in range(k - 1, -1, -1):heap[0], heap[i] = heap[i], heap[0]sift(heap, 0, i - 1)return heapli = list(range(100))
random.shuffle(li)
print(li)
print(topk(li, 10))

归并排序

def merge(li, low, mid, high):i = lowj = mid + 1ltmp = []while i <= mid and j <= high:if li[i] < li[j]:ltmp.append(li[i])i += 1else:ltmp.append(li[j])j += 1while i <= mid:ltmp.append(li[i])i += 1while j <= high:ltmp.append(li[j])j += 1li[low:high + 1] = ltmpdef merge_sort(li, low, high):if low < high:mid = (low + high) // 2merge_sort(li, low, mid)merge_sort(li, mid + 1, high)merge(li, low, mid, high)li = list(range(1000))
import randomrandom.shuffle(li)
print(li)
merge_sort(li, 0, len(li) - 1)
print(li)