目录

一、排序

1. 冒泡排序

2. 插入排序

3. 希尔排序

4. 选择排序

5. 快速排序

6. 堆排序

7. 归并排序

8. 计数、基数、桶排序（暂略）

二、递归/搜索

1. 递归练习A+B

1.1 一个整数，大于0，不用循环和本地变量，按照n，2n，4n，8n的顺序递增，当值大于5000时，把值按照指定顺序输出来。例：n=1237 则输出为： 1237， 2474， 4948， 9896， 9896， 4948， 2474， 1237。

1.2 第1个人10岁，第2个比第1个人大2岁，依次递推，请用递归方式计算出第8个人多大？

2. 栈的逆序操作，递归写法

3. 实现汉诺塔 [ LintCode 169 ]

4. 数组的全排列 [ LeetCode 46/47 ]

三、链表题

单链表翻转

四、二叉树

1. 前序遍历非递归实现  [ LeetCode 144 ]

2. 中序遍历非递归实现  [ LeetCode 094 ]

3. 后序遍历非递归实现  [ LeetCode 145 ]

4. 给前序和中序，求二叉树

五、二分法

本文主要使用Python语言来实现编程中的一些必知必会传统算法，其中可能夹杂少量C/C++语言的实现，可作参照观览用等。应熟练使用Python处理raw输入到程序中，也即使用Python来A更一般性的OJ题。

一、排序

一般而言掌握前七种排序就已经足够了，后三种非比较类排序因为受限，实际中应用的场合不够广泛；当然能掌握那是更好的。排序类算法的校验可去LintCode处提交校验。[ LintCode 463/464 ]就是其中的排序题目。

1. 冒泡排序

def bubbleSort(arr):
n = len(arr)
for i in range(n-1, 0, -1):
f = True
for j in range(i):
if a[j] > a[j+1]:
swap(a[j], a[j+1])
f = False
if f:
break

双端冒泡排序（鸡尾酒排序）实现如下。
def biBubbleSort(arr):
n = len(arr)
low = idx = 0
high = n – 1
while low < high:
for i in range(low, high):
if arr[i] > arr[i+1]:
swap(arr[i], arr[i+1])
idx = i
high = idx
for i in range(high, low, -1):
if arr[i] < arr[i-1]:
swap(arr[i], arr[i-1])
idx = i
low = idx

二者的时间复杂度均为O(N2)。

双端冒泡排序参考自：

https://blog.csdn.net/qq_35433716/article/details/83957847

2. 插入排序

以Python为例，代码如下；注意Python中的列表从下标0开始编号。

def insertSort(arr):
n = len(arr)
for i in range(1, n):
t = arr[i]
j = i – 1
while j >= 0 and arr[j] > t:
arr[j+1] = arr[j]
j -= 1
arr[j+1] = t

3. 希尔排序

void shell_sort(int arr[], int len) {
int gap, i, j;
int temp;
for (gap = len >> 1; gap > 0; gap >>= 1)
for (i = gap; i < len; i++) {
temp = arr[i];
for (j = i - gap; j >= 0 && arr[j] > temp; j -= gap)
arr[j + gap] = arr[j];
arr[j + gap] = temp;
}
}

使用Python的实现代码如下：
class Solution:
"""
@param A: an integer array
@return: nothing
"""
def shell_sort (self, A):
n = len(A)
gap = n >> 1
while gap > 0:
for i in range(gap, n):
tmp = A[i]
j = i - gap
while j >= 0 and A[j] > tmp:
A[j + gap] = A[j]
j -= gap
A[j + gap] = tmp
gap >>= 1

4. 选择排序

// 选择排序的通用算法框架（C/C++描述）如下：
void selectSort(int arr[])
{
for(int i = 0; i < arr.length; ++i)
// 选择第i小的记录，并交换到位
{
int j = selectMin(arr, i);
// 在arr[i.. arr.length]中选择key最小的记录
if(i != j) swap(arr[i], arr[j]);
// 与第i个记录交换
}
}
// 使用C/C++更详细的实现如下：
void selectSort(int *arr)
{
for(int i = 0; i < arr.length; ++i){
int minIdx = i;
for(int j = i + 1; j < arr.length; j++) {
if(arr[minIdx] > arr[j]) {
minIdx = j;
}
}
}
if(i != minIdx) swap(arr[i], arr[minIdx]);
}

使用Python的实现代码如下：
class Solution:
def selectSort(self, A):
n = len(A)
for i in range(n):
minIdx = i
for j in range(i+1, n):
if A[minIdx] > A[j]:
minIdx = j
if i != minIdx:
A[i], A[minIdx] = A[minIdx], A[i]

5. 快速排序

快排递归版Python实现如下：

def quick_sort(arr, left, right):
if left >= right: return
low = left
high = right
key = arr[low]
while left < right:
while left < right and arr[right] >= key:
right -= 1
arr[left] = arr[right]
while left < right and arr[left] <= key:
left += 1
arr[right] = arr[left]
arr[right] = key
quick_sort(arr, low, left-1)
quick_sort(arr, left+1, high)

快排非递归版C/C++实现如下：

int partition(int *a, int low, int high){
int p = a[low];
while(low < high){
while(low < high && a[high] >= p) --high;
a[low] = a[high];
while(low < high && a[low] <= p) ++low;
a[high] = a[low];
}
a[low] = p;
return low;
}
void quicksort(int *a, int left, int right){
stack<int> temp;
int i, j;
temp.push(right);
temp.push(left);
while(!temp.empty()){
i = temp.top();
temp.pop();
j = temp.top();
temp.pop();
if(i >= j) continue;
int k = partition(a, i, j);
if(k > i){
temp.push(k-1);
temp.push(i);
}
if(k < j){
temp.push(j);
temp.push(k+1);
}
}
}

快排非递归版Python实现如下：

class Solution:
def partition(self, a, low, high):
p = a[low]
while low < high:
while low < high and a[high] >= p:
high -= 1
a[low] = a[high]
while low < high and a[low] <= p:
low += 1
a[high] = a[low]
a[low] = p
return low
def quicksort(self, a, left, right):
tmp = []
tmp.append(right)
tmp.append(left)
while tmp != []:
i = tmp.pop(-1)
j = tmp.pop(-1)
if i >= j:
continue
k = self.partition(a, i, j)
if k > i:
tmp.append(k-1)
tmp.append(i)
if k < j:
tmp.append(j)
tmp.append(k+1)
def sortIntegers2(self, A):
self.quicksort(A, 0, len(A)-1)

思考：如何直接在（单）链表上实现快排？（对应练习OJ题为：LeetCode 148）

6. 堆排序

完美二叉树（即：满二叉树），定义从略。完全二叉树：除了最后一层之外的其他每一层都被完全填充，并且所有结点都保持向左对齐。完满二叉树（Full Binary Tree/Strictly Binary Tree）：所有非叶结点的度都是2。

堆排序算法借用了完全二叉树结点编号的一个特征，假设根节点编号为0，这也契合数组的第一个元素下标为0，则左子树编号为2*0+1，右子树编号为2*0+2，一般地，设父结点编号为A，则左子树根节点编号为2*A+1，右子树根结点编号为：2*A+2。

下述代码中，a为待排序数组，在heapAdjust()函数中，数组a[s..m]中除s结点之外均满足堆的定义。

class Solution:
def heapAdjust(self, a, s, m):
t = a[s]
i = 2*s + 1
while i <= m:
if i < m and a[i] < a[i+1]: i += 1 # 找到左右子树根节点的最大值
if t >= a[i]: break
# 已满足堆定义，无需再向下筛。
a[s] = a[i]
# 使s结点满足堆定义
s = i
# 使s结点满足堆定义
i = i*2 + 1
a[s] = t
def heapsort(self, a):
n = len(a)
for i in range(n//2 - 1, -1, -1): # 初始建堆，从最后一个非叶节点开始
self.heapAdjust(a, i, n – 1)
for i in range(n-1, 0, -1):
a[0], a[i] = a[i], a[0]
# 将堆顶值(数组首元素)交换至数组尾部
self.heapAdjust(a, 0, i-1)
# 大顶/根堆调整算法递归版
def heapAdjust2(self, a, s, m):
t = a[s]
i = 2*s + 1
if i > m: return
if i < m and a[i] < a[i+1]: i += 1
if t >= a[i]: return
else:
a[s] = a[i]
a[i] = t
self.heapAdjust2(a, i, m)

7. 归并排序

本实现给出递归版与非递归版两种，非递归版归并排序仅仅是mergeSort函数的不同，以C/C++语言为例。Python实现待加。

void merge(int *a, int low, int mid, int high){
int i, j, k;
int b[high - low + 1]; // 中间过程数组
i = low; j = mid + 1;
for(k=0; i <= mid && j <= high; k++){
if(a[i] < a[j]) b[k] = a[i++];
else b[k] = a[j++];
}
while(i<=mid) b[k++] = a[i++];
while(j<=high) b[k++] = a[j++];
for(i=low, j=0; i <= high; i++, j++)
a[i] = b[j];
}
void mergeSort(int a[], int low, int high){
if(low < high){
int mid = (low + high) / 2;
mergeSort(a, low, mid);
mergeSort(a, mid + 1, high);
merge(a, low, mid, high);
}
}
// 非递归版的mergeSort()函数如下
void mergeSort2(int a[], int n){
int step = 1; // 步长分别为1，2，4，8…
while(step <= n){
int low = 0;
while(low+step <= n){
int mid = low + step - 1;
int high = mid + step;
if(high > n) high = n;
merge(a, low, mid, high);
low = high + 1;
}
step *= 2
}
}
当int a[8] = {1, 6, 3, 2, 9, 8, 7, 5}; 此时，int n = 8;
递归版调用方式为：mergeSort(a, 0, n-1);
非递归调用方式为：mergeSort2(a, n-1);

单链表归并排序Python语言AC版代码如下：

class Solution:
def sortList(self, head: ListNode) -> ListNode:
if head is None or head.next is None:
return head
return self.mergeSort(head)
def mergeSort(self, node):
if node is None or node.next is None:
return node
slow = fast = node
while fast.next and fast.next.next:
fast = fast.next.next
slow = slow.next
fast = slow
slow = slow.next
fast.next = None
fast = self.mergeSort(node)
slow = self.mergeSort(slow)
return self.merge(fast, slow)
def merge(self, l1, l2):
if l1 is None: return l2
if l2 is None: return l1
res = ListNode(-1)
p = res
while l1 and l2:
if l1.val < l2.val:
p.next = l1
l1 = l1.next
else:
p.next = l2
l2 = l2.next
p = p.next
if l1:
p.next = l1
if l2:
p.next = l2
return res.next

8. 计数、基数、桶排序（暂略）

二、递归/搜索

递归题目相当多，有些也挺有意思的，可以称作递归类型题中的“hello world”“冒泡排序”“A+B”等。以下记录几则，聊供一乐。

假如你现在正在排队买票，前面有很多人，怎么才能知道你现在是第几号呢？这个时候就可以用递归了，你可以问你前面的人是多少号，在他的号数上加一即为你的号数。但是，前面的人也不知道自己是多少号啊，所以他再问他前面的人，这样一个一个的向前面问，直到问到队头的人，他说他现在是1号，然后这样就可以一个一个向后把数字传回来，直到你前面的人告诉你他是多少号，这样你就知道了你的位置了。

这个例子就是一个标准的递归求解问题的分解过程，一个一个向前问的过程就是"递"，一个一个向后传回来的过程就是"归"。基本上所有的递归问题都可以用公式表示出来。如上述例子的递归推导公式为：

f(n) = f(n-1) + 1，其中f(1) = 1

f(n)表示你现状所在的位置（多少号），f(n-1)表示你前面一个人所在的位置（多少号），f(1) = 1表示第一个人直到自己为1号。有了这个递推公式，我们就可以很轻松的将它改写为递归代码，如下所示：

public int f(int n){
if(n == 1)
return 1;
else
return f(n-1) + 1;
}

【注：上例非原创，感谢原创者提供的简洁明晰的例子。】

1. 递归练习A+B

1.1 一个整数，大于0，不用循环和本地变量，按照n，2n，4n，8n的顺序递增，当值大于5000时，把值按照指定顺序输出来。例：n=1237 则输出为： 1237， 2474， 4948， 9896， 9896， 4948， 2474， 1237。

1.2 第1个人10岁，第2个比第1个人大2岁，依次递推，请用递归方式计算出第8个人多大？

2. 栈的逆序操作，递归写法

在考虑递归解法的时候，需要铭记的一点是：发现原问题中的子问题。就本问题而言，子问题就是可以考虑成以下两种形式：

(1) 取出栈顶元素后，将栈进行逆序，最后将取出的栈顶元素插入到栈底；

(2) 取出栈底元素后，将栈进行逆序，最后将取出的栈底元素压入到栈顶。

class Solution:
def reverseStack(self, stack):
if stack == []:
return
top = stack.pop(-1)
self.reverseStack(stack)
self.insert2StackBottom(stack, top)
def insert2StackBottom(self, stack, bottom):
if stack == []:
stack.append(bottom)
top = stack.pop(-1)
self.insert2StackBottom(stack, bottom)
stack.append(top)

方法insert2StackBottom的子问题为：将栈顶元素取出，将待插入元素插入到栈的栈底，将取出的栈顶元素压入。

本题参考自：https://blog.csdn.net/dm_vincent/article/details/8008238

另有相类似的递归练习题：字符串逆序，逆序打印单链表 等等。

3. 实现汉诺塔 [ LintCode 169 ]

非常经典的递归应用练习题，应深刻理解、掌握、应用。一般而言掌握递归的写法已经足够了。

更进一步地，汉诺塔还有使用栈或队列的非递归实现，更有限制使用栈或队列的非递归格雷编码实现，还是有挺多内涵在里面的，有些意思。

class Solution:
"""
@param n: the number of disks
@return: the order of moves
"""
def __init__(self):
self.ans = []
def hanoi(self, n, x, y, z):
if n == 1:
t = "from " + x + " to " + z
self.ans.append(t)
else:
self.hanoi(n-1, x, z, y)
t = "from " + x + " to " + z
self.ans.append(t)
self.hanoi(n-1, y, x, z)
def towerOfHanoi(self, n):
self.hanoi(n, "A", "B", "C")
return self.ans

4. 数组的全排列 [ LeetCode 46/47 ]

求数组全排列有递归与迭代两种解法，数组中含与不含重复数字时解法有所不同，这里当前仅辑录递归解法，迭代解法待加。

数组中不含重复数字的解法如下：

class Solution:
def __init__(self):
self.ans = []
def getPermutation(self, arr, n, idx):
if idx == n:
self.ans.append(arr[::])
else:
for i in range(idx, n):
arr[i], arr[idx] = arr[idx], arr[i]
self.getPermutation(arr, n, idx+1)
arr[i], arr[idx] = arr[idx], arr[i]
def permute(self, nums: List[int]) -> List[List[int]]:
self.getPermutation(nums, len(nums), 0)
return self.ans

数字中含重复数字的解法如下：

class Solution:
def __init__(self):
self.ans = []
def getPermutation(self, arr, n, idx):
if idx == n:
self.ans.append(arr[::])
else:
for i in range(idx, n):
f = False
for j in range(i+1, n):
if arr[i] == arr[j]:
f = True
break
if f:
continue
arr[i], arr[idx] = arr[idx], arr[i]
self.getPermutation(arr, n, idx+1)
arr[i], arr[idx] = arr[idx], arr[i]
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
self.getPermutation(nums, len(nums), 0)
return self.ans

三、链表题

单链表翻转

本题有多种解法，至少有四种解法，修改指针法，栈储存节点法，递归法、修改链表节点值法。这里仅给出递归法。[ LeetCode 206/LintCode 35 ]

优雅版递归解法如下：

class Solution:
def reverseList(self, head: ListNode) -> ListNode:
if head is None or head.next is None:
return head
newhead = self.reverseList(head.next)
head.next.next = head
head.next = None
return newhead

四、二叉树

1. 前序遍历非递归实现  [ LeetCode 144 ]

class Solution(object):
def preorderTraversal(self, root):
if root is None:
return []
ans = []
s = []
cur = root
while cur != None or s != []:
if cur:
s.append(cur)
ans.append(cur.val)
cur = cur.left
else:
t = s.pop(-1)
cur = t.right
return ans

2. 中序遍历非递归实现  [ LeetCode 094 ]

class Solution(object):
def inorderTraversal(self, root):
if root is None:
return []
ans = []
s = []
cur = root
while s != [] or cur != None:
if cur:
s.append(cur)
cur = cur.left
else:
t = s.pop(-1)
ans.append(t.val)
cur = t.right
return ans

3. 后序遍历非递归实现  [ LeetCode 145 ]

class Solution(object):
def postorderTraversal(self, root):
if root is None:
return []
ans = []
s = []
cur = root
lastVisited = None
while s != [] or cur != None:
if cur != None:
s.append(cur)
cur = cur.left
else:
t = s[-1]
if t.right != None and lastVisited != t.right:
cur = t.right
else:
ans.append(t.val)
s.pop(-1)
lastVisited = t
return ans

4. 给前序和中序，求二叉树

已知：前序 + 中序 => 后序 [LeetCode 105/LintCode 73]；

后序 + 中序 => 前序 [LeetCode 106/LintCode 72]。

给前序与中序，求二叉树，代码如下：

class Solution:
def buildTree(self, preorder, inorder) -> TreeNode:
if preorder == [] or inorder == []:
return None
tmp = preorder[0]
root = TreeNode(tmp)
mid = inorder.index(tmp)
root.left = self.buildTree(preorder[1:mid+1], inorder[0:mid])
root.right = self.buildTree(preorder[mid+1:], inorder[mid+1:])
return root

给中序和后序，求二叉树，代码如下：

class Solution:
def buildTree(self, inorder, postorder: List[int]) -> TreeNode:
if postorder == [] or inorder == []:
return None
tmp = postorder[-1]
root = TreeNode(tmp)
mid = inorder.index(tmp)
root.left = self.buildTree(inorder[0:mid],postorder[0:mid])
root.right = self.buildTree(inorder[mid+1:],postorder[mid:-1])
return root

五、二分法

二分查找的条件，复杂度。返回目标元素的位置，不存在返回-1。

整数的二分查找，如果元素类型任意 [C++而言] 。

旋转数组的二分查找。

假设要查找的元素为key，则拢共有以下6种查找情况，第一个=key的元素，第一个>=key的元素，第一个>key的元素；最后一个=key的元素，最后一个<=key的元素，最后一个<key的元素。

二分查找的条件是数组/列表中的元素具备某种顺序，查找的时间复杂度为O(logN)，普通的二分查找(递归/非递归)模板如下，其中查找区间为闭区间[L, R]。其中可以有多个等于key的元素，但只需返回任意一个位置。[ LintCode 457 ]

迭代版二分查找模板如下：

def biSearch(arr, key):
L, R = 0, len(arr) - 1
while L <= R:
mid = L + (R-L) // 2
# 防止直接相加后的溢出，Python3无需考虑
if arr[mid] > key:
R = mid - 1
elif arr[mid] < key:
L = mid + 1
else:
return mid
return -1

递归版二分查找模板如下：

def biSearch(arr, key, L, R):
if L > R:
return -1
mid = L + (R - L) // 2
if arr[mid] > key:
return biSearch(arr, key, L, mid-1)
elif arr[mid] < key:
return biSearch(arr, key, mid+1, R)
else:
return mid

第一个=key的元素的下标：
def firstEqual(arr, key):
L, R = 0, len(arr) – 1
while L <= R:
mid = L + (R-L) // 2
if arr[mid] >= key:
R = mid – 1
else:
L = mid + 1
if L < len(arr) and arr[L] == key:
return L
return -1
第一个>=key的元素的下标：
def firstLargeEqual(arr, key):
L, R = 0, len(arr) – 1
while L <= R:
mid = L + (R – L) // 2
if arr[mid] >= key:
R = mid – 1
else:
L = mid + 1
return L
第一个>key的元素的下标：
def firstLarge(arr, key):
L, R = 0, len(arr) – 1
while L <= R:
mid = L + (R - L) // 2
if arr[mid] > key:
R = mid – 1
else:
L = mid + 1
return L
最后一个=key的元素的下标，不存在返回-1：
def lastEqual(arr, key):
L, R = 0, len(arr) – 1
while L <= R:
mid = L + (R – L) // 2
if arr[mid] <= key:
L = mid + 1
else:
R = mid – 1
if R >= 0 and arr[R] == key:
return R
return -1
最后一个<=key的元素的下标：
def lastSmallEqual(arr, key):
L, R = 0, len(arr) – 1
while L <= R:
mid = L + (R – L) // 2
if arr[mid] <= key:
L = mid + 1
else:
R = mid – 1
return R
最后一个<key的元素的下标：
def lastSmall(arr, key):
L, R = 0, len(arr) – 1
while L <= R:
mid = L + (R – L) // 2
if arr[mid] < key:
L = mid + 1
else:
R = mid – 1
return R

最后

以上就是爱笑大门为你收集整理的必知必会：传统算法【Python】一、排序二、递归/搜索三、链表题四、二叉树五、二分法的全部内容，希望文章能够帮你解决必知必会：传统算法【Python】一、排序二、递归/搜索三、链表题四、二叉树五、二分法所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。