集中汇总常见的排序算法（冒泡排序，选择排序，插入排序，希尔排序，归并排序，快速排序，堆排序，计数排序，桶排序）和搜索算法（顺序搜索，二分搜索，插值搜索，跳跃搜索，快速搜索，哈希搜索）的算法原理，算法复杂度的分析，以及算法实现。
学习目标：
- 理解算法是如何实现的
- 掌握算法的原理
-
判断算法的优越性
排序算法
排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。排序算法，就是如何使得记录按照要求排列的方法。——百度百科
冒泡排序
冒泡排序重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
-
算法原理
- 比较相邻的元素，如果第一个比第二个大，就交换他们；
- 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
- 针对所有的元素重复以上步骤，除了最后一个；
- 重复步骤 1~3，直到排序完成。
-
复杂度分析
最坏复杂度: 时间复杂度为 \(O(n^2)\)
最好复杂度：时间复杂度为 \(O(n)\)
平均复杂度: 时间复杂度为 \(O(n^2)\) 算法实现
def bubble_sort(sequence):
for i in range(1, len(sequence)):
for j in range(0, len(sequence) - i):
if sequence[j] > sequence[j+1]:
sequence[j],sequence[j+1] = sequence[j+1],sequence[j]
return sequence选择排序
选择排序是一种简单直观的排序算法，无论什么数据进去都是 \(O(n^2)\) 的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间。
-
算法原理
- 首先在未排序序列中找到最小(大)元素，存放到排序序列的起始位置；
- 再从剩余未排序元素中继续寻找最小(大)元素，然后放到已排序序列的末尾；
- 重复第二步，直到所有元素均排序完毕。
-
复杂度分析
最坏复杂度: 时间复杂度为 \(O(n^2)\)
最好复杂度：时间复杂度为 \(O(n^2)\)
平均复杂度: 时间复杂度为 \(O(n^2)\) 算法实现
def select_sort(sequence):
for i in range(len(sequence)-1):
minIndex = i #记录最小数的索引
for j in range(i+1,len(sequence)):
if sequence[j] < sequence[minIndex]:
minIndex = j
sequence[minIndex], sequence[i] = sequence[i], sequence[minIndex] #将该数放到已排序序列的末尾
return sequence插入排序
插入排序是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入
-
算法原理
- 从第一个元素开始，该元素可以认为已经被排序；
- 取出下一个元素，在已经排序的元素序列中从后向前扫描；
- 如果该元素(已排序)大于新元素，将该元素移到下一位置；
- 重复步骤 3，直到找到已排序的元素小于或者等于新元素的位置；
- 将新元素插入到该位置后；
- 重复步骤 2-5。
-
复杂度分析
最坏复杂度: 时间复杂度为 \(O(n^2)\)
最好复杂度：时间复杂度为 \(O(n^2)\)
平均复杂度: 时间复杂度为 \(O(n^2)\) 算法实现
def insertion_sort(sequence):
for index in range(1, len(sequence)):
while(index > 0 and sequence[index - 1] > sequence[index]):
sequence[index], sequence[index - 1] = sequence[index - 1], sequence[index]
index = index-1
return sequence希尔排序
希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。
希尔排序是基于插入排序的以下两点性质而提出改进方法的：
* 插入排序在对几乎已经排好序的数据操作时，效率高，既可以达到线性排序的效率。
* 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位。
-
算法原理
希尔排序基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。- 选择一个增量序列$ t1,t2,...,tk$,其中 \(ti>tj\),\(tk=1\)；
- 按增量序列的个数 k，对序列进行 k 趟排序；
- 每趟排序，根据对应的增量 \(ti\),将待排序序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
- 复杂度分析
最坏复杂度: 时间复杂度为$ O(n(logn)^2)$
最好复杂度：时间复杂度为 \(O(nlogn)\)
平均复杂度: 取决于间隔序列 算法实现
def shell_sort(sequence):
gap = len(sequence)
while gap > 1:
gap = gap//2
for i in range(gap, len(sequence)):
for j in range(i%gap, i, gap):
if sequence[i] < sequence[j]:
sequence[i], sequence[j] = sequence[j], sequence[i]
return sequence归并排序
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为 2-路归并。
-
算法原理
- 把长度为 n 的输入序列分成两个长度为 n/2 的子序列；
- 对这两个子序列分别采用归并排序；
- 将两个排序好的子序列合并成一个最终的排序序列。
- 复杂度分析
最坏复杂度: 时间复杂度为 \(O(nlogn)\)
最好复杂度：时间复杂度为 \(O(nlogn)\)
平均复杂度: 时间复杂度为 \(O(nlogn)\) - 算法实现
import math
def merge_sort(sequence):
if(len(sequence) <2):
return sequence
mid = math.floor(len(sequence)/2)
left, right = sequence[0:mid], sequence[mid:]
return merge(merge_sort(left), merge_sort(right))
def merge(left, right):
result = []
while left and right:
if left[0] < right[0]:
result.append(left.pop(0))
else:
result.append(right.pop(0))
while left:
result.append(left.pop(0))
while right:
result.append(right.pop(0))
return result快速排序
快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
- 算法原理
归并排序基本思想是：使用分治法来把一个串（list）分为两个子串（sub-lists）
1. 从数列中挑出一个元素，称为"基准"(pivot)。
2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
-
复杂度分析
最坏复杂度: 时间复杂度为 \(O(n^2)\)
最好复杂度：时间复杂度在 \(O(n)\) 和 \(O(nlogn)\) 中间
平均复杂度: 时间复杂度为 \(O(nlogn)\) 算法实现
def quick_select(sequence):
def recursive(begin, end):
if begin > end:
return
left, right = begin, end
pivot = sequence[left]
while left < right:
while left < right and sequence[right] > pivot:
right = right-1
while left < right and sequence[left] <= pivot:
left = left+1
sequence[left], sequence[right] = sequence[right], sequence[left]
sequence[left], sequence[begin] = pivot, sequence[left]
recursive(begin, left-1)
recursive(right+1, end)
recursive(0,len(sequence)-1)
return sequence堆排序
堆排序（Heapsort）的基本思想：是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子节点的键值或索引总是小于（或者大于）它的父节点。
- 算法原理
堆排序基本思想是：
1. 将初始待排序关键字序列(R1,R2...Rn)构建成大顶堆，此堆为初始的无序区。
2. 将堆顶元素 R[1]与最后一个元素 R[n]交换，此时得到新的无序区(R1,R2,...Rn-1)和新的有序区(Rn)，且满足 R[1,2...n-1]<=R[n]。
3. 由于交换后新的堆顶 R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,...Rn-1)调整为新堆，然后再次将 R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2...Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为 n-1，则整个排序过程完成。
-
复杂度分析
最坏复杂度: 时间复杂度为 \(O(nlogn)\)
最好复杂度：时间复杂度在 \(O(nlogn)\)
平均复杂度: 时间复杂度为 \(O(nlogn)\) 算法实现
import random
def heap_sort(sequence):
def heap_adjust(parent):
child = 2*parent +1 #left child
while child < len(heap):
if child + 1 < len(heap):
if heap[child + 1] > heap[child]:
child = child +1 #right child
if heap[parent] >= heap[child]:
break
heap[parent], heap[child] = \
heap[child], heap[parent]
parent, child = child, 2*child +1
heap, sequence = sequence.copy(), []
for i in range(len(heap)):
heap_adjust(i)
while len(heap) != 0:
heap[0], heap[-1] = heap[-1], heap[0]
sequence.insert(0, heap.pop())
heap_adjust(0)
return sequence计数排序
计数排序(Counting Sort)不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。
- 算法原理
计数排序基本思想是：
1. 找出待排序的数组中最大和最小的元素；
2. 统计数组中每个值为 i 的元素出现的次数，存入数组 C 的第 i 项；
3. 对所有的计数累加（从 C 中的第一个元素开始，每一项和前一项相加）；
4. 反向填充目标数组：将每个元素 i 放在新数组的第 C(i)项，每放一个元素就将 C(i)减去 1。
-
复杂度分析
最坏复杂度: 时间复杂度为 \(O(n+k)\)
最好复杂度：时间复杂度在 \(O(n+k)\)
平均复杂度: 时间复杂度为 \(O(n+k)\)
算法实现
import random
def counting_sort(sequence):
if sequence == []:
return []
sequence_len = len(sequence)
sequence_max = max(sequence) #找出待排序数组中最大的元素
sequence_min = min(sequence)
counting_arr_length = sequence_max - sequence_min + 1
counting_arr = [0]*counting_arr_length
for number in sequence:
counting_arr[number - sequence_min] += 1 #统计数组中元素出现次数
for i in range(1, counting_arr_length): #计算累加
counting_arr[i] = counting_arr[i] + counting_arr[i - 1]
ordered = [0]*sequence_len
for i in range(sequence_len - 1, 0, -1):
ordered[counting_arr[sequence[i] - sequence_min] - 1] = sequence[i]
counting_arr[sequence[i] - sequence_min] -= 1
return ordered桶排序
桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。桶排序 (Bucket sort)的工作原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）。
- 算法原理
计数排序基本思想是：
1. 设置一个定量的数组当作空桶；
2. 遍历输入数据，并且把数据一个一个放到对应的桶里去；
3. 对每个不是空的桶进行排序；
4. 从不是空的桶里把排好序的数据拼接起来。
-
复杂度分析
最坏复杂度: 时间复杂度为 \(O(n+k)\)
最好复杂度：时间复杂度在 \(O(n)\)
平均复杂度: 时间复杂度为 \(O(n)\) 算法实现
import math
import random
DEFAULT_BUCKET_SIZE = 5
def insertion_sort(sequence):
for index in range(1, len(sequence)):
while(index > 0 and sequence[index - 1] > sequence[index]):
sequence[index], sequence[index - 1] = sequence[index - 1], sequence[index]
index = index - 1
return sequence
def bucket_sort(sequence, bucketSize = DEFAULT_BUCKET_SIZE):
if(len(sequence) == 0):
return []
minValue = sequence[0]
maxValue = sequence[0]
for i in range(0, len(sequence)):
if sequence[i] < minValue:
minValue = sequence[i] #寻找最小值
elif sequence[i] > maxValue:
maxValue = sequence[i] #寻找最大值
bucketCount = math.floor((maxValue - minValue) / bucketSize) + 1 #桶的初始化
buckets = []
for i in range(0, bucketCount):
buckets.append([])
for i in range(0, len(sequence)): #遍历数据 将数据依次放进桶中
buckets[math.floor((sequence[i] - minValue) / bucketSize)].append(sequence[i])
sortedArray = []
for i in range(0, len(buckets)): #将每一个不是空的桶进行排序
insertion_sort(buckets[i])
for j in range(0, len(buckets[i])):
sortedArray.append(buckets[i][j])
return sortedArray搜索算法
搜索算法是利用计算机的高性能来有目的的穷举一个问题解空间的部分或所有的可能情况，从而求出问题的解的一种方法。——百度百科
顺序搜索
顺序搜索也称为线性搜索，属于无序查找算法。
算法原理：从数据结构线性表的一端开始，顺序扫描，依次将扫描到的结点关键字与给定值 k 相比较，若相等则表示查找成功；若扫描结束仍没有找到关键字等于 k 的结点，表示查找失败。
适用性：顺序搜索适合于存储结构为顺序存储或链接存储的线性表。
-
复杂度分析
最坏复杂度: 从一个线性表依次查找对应项，需要做 n 次查找，在最后一项才查找到对应项或者查找失败（仍然未查找到对应项），时间复杂度为 \(O(n)\)。
最好复杂度: 从一个线性表依次查找对应项，第一项就查找到对应项,时间复杂度为 \(O(1)\) 。
平均复杂度: 假设每个数据元素的概率相等（1/n),1/n(1+2+3+...+n)=(n+1)/2，所以时间复杂度为 \(O(n)\) 。 算法实现
思路：从顺序表的头部依次遍历元素，判断是否匹配，若匹配则查找成功，若不匹配则遍历下一个元素。
def sequencesearch(sequence, target):
for i in range(len(sequence)):
if target == sequence[i]:
return i
return None二分搜索
二分搜索也称折半搜索（Binary Search），它是一种效率较高的搜索方法。但是，二分搜索要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列
算法原理：用给定值 k 先与中间结点的关键字比较，中间结点把线性表分成两个子表，若相等则查找成功；若不相等，再根据 k 与该中间结点关键字的比较结果确定下一步查找哪个子表，这样递归进行，直到查找到或查找结束发现表中没有这样的结点
适用性：二分查找的前提是有序表存储，如果是无序的则先要进行排序操作。对于静态查找表，一次排序后不再变化，折半查找能得到不错的效率。但对于需要频繁执行插入或删除操作的数据集来说，维护有序的排序会带来不小的工作量，那就不建议使用。——《大话数据结构》
-
复杂度分析
最坏复杂度:上述分析可以得到时间复杂度为 \(O(logn)\)。
最好复杂度：第一次折半就查找到中间元素,时间复杂度为 \(O(1)\)。
平均复杂度:时间复杂度为 \(O(logn)\)。 算法实现
思路：每次查询查找范围内的"中间位置"的结点，若该节点不是所需，则缩小查找范围为前半部分或后半部分。
def binarysearch(sorted_sequence, target):
left = 0
right = len(sorted_sequence) - 1
while(left <= right):
midpoint = (left+right)//2
current_item = sorted_sequence[midpoint]
if current_item == target:
return midpoint
elif target < current_item:
right = midpoint-1
else:
left = midpoint+1
return None三分搜索：就是在二分搜索的基础上，将区间分为三个区间做判断，因此存在 5 个条件判断。
def ternary_search(sorted_sequence, target):
left = 0
right = len(sorted_sequence) - 1
while(left <= right):
Third1 = (right-left)//3+left
Third2 = 2*(right - left)//3+left
if(sorted_sequence[Third1] == target):
return Third1
elif(sorted_sequence[Third2] == target):
return Third2
elif(target < sorted_sequence[Third1]):
right = Third1 - 1
elif(target > sorted_sequence[Third2]):
left = Third2 + 1
else:
left = Third1 +1
right = Third2 - 1
return None插值搜索
由二分搜索可以看出，折半查找这种查找方式，不是自适应的（也就是说是傻瓜式的）。二分查找中查找点计算如下：mid=(left+right)/2, 即 mid=left+1/2(right-left)。将查找的点改进为如下： mid=left+(key-a[left])/(a[right]-a[left])(right-left)，也就是将上述的比例参数 1/2 改进为自适应的，根据关键字在整个有序表中所处的位置，让 mid 值的变化更靠近关键字 key，这样也就间接地减少了比较次数。这就得出了插值搜索。
算法原理：基于二分搜索算法，只是在取"中点"的时候把比例参数 1/2 修改为自适应参数，可以提高搜索效率。当然，插值搜索也属于有序搜索。
适用性：对于表长较大，而关键字分布又比较均匀的查找表来说，插值搜索算法的平均性能比折半搜索要好的多。反之，数组中如果分布非常不均匀，那么插值搜索未必是很合适的选择。
-
复杂度分析
最坏复杂度:时间复杂度为 \(O(logn)\)，最坏的情况就是二分搜索的情况，时间复杂度和二分搜索的时间复杂度相同。
最好复杂度：时间复杂度为 \(O(1)\)。
平均复杂度:时间复杂度为 \(O(loglogn)\) 算法实现
def insert_search(sorted_sequence, target):
left = 0
right = len(sorted_sequence) - 1
while(left <= right):
midpoint=left+((target-sorted_sequence[left])*(right-left))//(sorted_sequence[right]-sorted_sequence[left])
if midpoint < 0 or midpoint >= len(sorted_sequence):
return None
current_item = sorted_sequence[midpoint]
if current_item == target:
return midpoint
elif target < current_item:
right = midpoint - 1
else:
left = midpoint +1
return None跳跃搜索
跳跃搜索(Jump search)，按照固定步长，从有序表的首项步进，直到匹配到符合目标元素的区间，然后在该区间使用线性搜索，找到目标元素的确切位置。
算法原理：基于二分搜索算法，采用固定间隔进行跳跃，直到找到一个符合目标元素的区间，然后在该区间使用线性搜索，找到目标元素的确切位置。
适用性： 跳跃搜索的前提是有序表存储。相比于二分搜索，跳跃搜索仅遍历一次，而二分搜索最多需要 O(logn)，如果向后跳跃比向前跳跃花费更多时间，考虑要搜索的元素是最小元素或小于最小的，我们一般选用跳跃搜索。
-
复杂度分析
最坏复杂度:时间复杂度为 \(O(n^(1/2))\)
最好复杂度：时间复杂度为 \(O(n^(1/2))\)
平均复杂度:时间复杂度为 \(O(n^(1/2))\) 算法实现
思路：采用固定间隔进行跳跃，直到找到一个符合目标元素的区间，然后在该区间使用线性搜索，找到目标元素的确切位置
import math
def jumpsearch(sorted_sequence, target):
n = len(sorted_sequence)
step = int(math.floor(math.sqrt(n)))
prev = 0
while sorted_sequence[min(step, n) - 1] < target: #按照固定步长跳跃
prev = step
step = step + int(math.floor(math.sqrt(n)))
if prev >= n:
return None
while sorted_sequence[prev] < target: #线性搜索
prev = prev+1
if prev == min(step, n):
return None
if sorted_sequence[prev] == target:
return prev
else:
return None快速搜索
快速搜索(quick search)，快速选择是一种选择算法，用于查找无序列表中的第 k 个最小元素，它与快速排序算法有关。
算法原理：基于二分搜索算法，采用固定间隔进行跳跃，直到找到一个符合目标元素的区间，然后在该区间使用线性搜索，找到目标元素的确切位置。
适用性：用于查找无序列表中的第 k 个最小元素或最大元素。
-
复杂度分析
最坏复杂度:时间复杂度为 \(O(n^2)\)。
最好复杂度：时间复杂度为 \(O(n)\)。
平均复杂度:时间复杂度为 \(O(n)\)。 算法实现
思路：和快速排序相同，设置一个对应的分区函数，其作用是对给定元素，对列表执行分为两部分的操作：小于指定元素的部分，大于或等于指定元素的部分
import random
def partition(sequence, left, right, pivot_index):
pivot_value = sequence[pivot_index]
sequence[pivot_index], sequence[right] = sequence[right], sequence[pivot_index] #交换两个元素 使pivot_index与最右边元素置换位置，即现将pivot移动到最右边
store_index = left
for i in range(left, right):
if sequence[i] < pivot_value:
sequence[store_index], sequence[i] = sequence[i], sequence[store_index] #交换两个元素 使当前遍历元素(小于pivot_value的元素)与store_index元素置换位置
store_index = store_index + 1 #store_index 索引增加1
sequence[store_index], sequence[right] = sequence[right], sequence[store_index] #交换两个元素 使store_index与最后边元素置换位置，即交换回来pivot最终应该在的位置
return store_index
def quick_search(sequence, left, right, k):
if left == right: #如果只有一个元素
return sequence[left] #返回该元素
pivot_index = left+random.randint(0, right-left+1) #初始pivot_index 使pivot_index 在无序表随机
pivot_index = partition(sequence, left, right, pivot_index) #pivot在已经排好序的位置
if k==pivot_index:
return sequence[k] #返回该位置
elif k < pivot_index:
return quick_search(sequence, left, pivot_index-1, k) #继续在[left, pivot_index-1]区间快速检索
else:
return quick_search(sequence, pivot_index+1, right, k) #继续在[pivot_index+1, right]区间快速检索
哈希搜索
哈希表就是一种以键-值(key-indexed) 存储数据的结构，只要输入待查找的键即 key，即可查找到其对应的值。哈希表是一个在时间和空间上做出权衡的经典例子。如果没有内存限制，那么可以直接将键作为数组的索引。那么所有的查找时间复杂度为 O(1)；如果没有时间限制，那么我们可以使用无序数组并进行顺序查找，这样只需要很少的内存。哈希表使用了适度的时间和空间来在这两个极端之间找到了平衡。只需要调整哈希函数算法即可在时间和空间上做出取舍。
算法原理：哈希的思路很简单，如果所有的键都是整数，那么就可以使用一个简单的无序数组来实现：将键作为索引，值即为其对应的值，这样就可以快速访问任意键的值。这是对于简单的键的情况，我们将其扩展到可以处理更加复杂的类型的键。
适用性：一个简单无序数组即可实现索引关系。
-
复杂度分析
最坏复杂度:时间复杂度为 \(O(1)\) ,对于无冲突的哈希表而言。
最好复杂度：时间复杂度为 \(O(1)\) ,对于无冲突的哈希表而言。
平均复杂度:时间复杂度为 \(O(1)\) ,对于无冲突的哈希表而言。 算法实现
思路：建立哈希表，完成索引结构，即实现哈希搜索的功能。注： 代码忽略了数据类型，元素溢出等问题的判断
class HashTable:
def __init__(self, size):
self.elem = [None for i in range(size)] #使用list数据结构作为哈希表元素保存方法
self.count = size #最大表长
def hash(self, key):
return key%self.count #散列函数采用除留余数法
def insert_hash(self, key): #插入关键字到哈希表内
address = self.hash(key) #求散列地址
while self.elem[address]: #当前位置已经有数据 发生冲突
address = (address+1)%self.count #线性探测下一地址是否可用
self.elem[address] = key #没有冲突则直接保存
def search_hash(self, key): #查找关键字 返回布尔值
star = address = self.hash(key)
while self.elem[address] != key:
address = (address+1)%self.count
if not self.elem[address] or address == star: #表示没找到或循环到了开始位置
return False
return True, address #返回索引值