快速排序 模板
def sortIntegers2(self, A):
self.quickSort(A, 0, len(A) - 1)
def quickSort(self, A, start, end):
if start >= end:
return
left, right = start, end
pivot = A[(start + end) / 2];
while left <= right:
while left <= right and A[left] < pivot:
left += 1
while left <= right and A[right] > pivot:
right -= 1
if left <= right:
A[left], A[right] = A[right], A[left]
left += 1
right -= 1
self.quickSort(A, start, right)
self.quickSort(A, left, end)
Python变量值交换
声明变量
a=50
b=10
开始交换，先把其中一个值赋给临时变量，然后才能实现交换变量。
tmp = a
a = b
b = tmp
在Python中，实现两个变量值交换非常方便
声明变量
a=50
b=10
开始交换变量
a,b = b,a
归并排序
Python一切皆对象
Python一切皆对象举例
python函数传参是传值还是传引用？
def sortIntegers2(self, A):
n = len(A)
if n <= 1:
return A
return self.sort(A, 0, n - 1)
def sort(self, A, low, high):
if low > high:
return []
elif low == high:
return [A[low]]
mid = (low + high) / 2
left = self.sort(A, low, mid)
right = self.sort(A, mid + 1, high)
return self.merge(left, right)
def merge(self, left, right):
n = len(left)
m = len(right)
if n == 0:
return list(right)
if m == 0:
return list(left)
i, j = 0, 0
result = []
while i < n and j < m:
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
if i <= n - 1:
for k in range(i, n):
result.append(left[k])
if j <= m - 1:
for k in range(j, m):
result.append(right[k])
return result
堆排序
堆排序就是把最大堆堆顶的最大数取出，将剩余的堆继续调整为最大堆，再次将堆顶的最大数取出，这个过程持续到剩余数只有一个时结束。在堆中定义以下几种操作：
最大堆调整（Max-Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点
创建最大堆（Build-Max-Heap）：将堆所有数据重新排序，使其成为最大堆
堆排序（Heap-Sort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算
常见排序算法 - 堆排序 (Heap Sort)
def adjust_heap(lists, i, size):
lchild = 2 * i + 1
rchild = 2 * i + 2
max = i
if i < size / 2:
if lchild < size and lists[lchild] > lists[max]:
max = lchild
if rchild < size and lists[rchild] > lists[max]:
max = rchild
if max != i:
lists[max], lists[i] = lists[i], lists[max]
adjust_heap(lists, max, size)
def build_heap(lists, size):
for i in range(0, (size/2))[::-1]:
adjust_heap(lists, i, size)
def heap_sort(lists):
size = len(lists)
build_heap(lists, size)
for i in range(0, size)[::-1]:
lists[0], lists[i] = lists[i], lists[0]
adjust_heap(lists, 0, i)
