根据步长gap的不同将数列分成n/gap个子序列，然后把子序列进行插入排序，然后不断缩小gap,直到gap=1.
初始gap=n/2
然后每次gap/2直到=1
gap的取值和缩小方法可以自定义！！！
实现1:完全按照希尔的思路来做，先确定gap 然后分子序列，然后插入排序！！（4个循环）但是最坏时间复杂度是O(n2)
# 比较拙略的方法，但是也是用希尔排序实现了
def shell_sort_my_bad(items):
len_items = len(items)
gap = len_items // 2
while gap > 0:
# 首先要根据gap，分出来gap个子序列
for i in range(0, gap):
# 子序列的表示方法是：(i,i+gap,i+2gap.....) 0:
if items[b] < items[b - gap]:
items[b], items[b - gap] = items[b - gap], items[b]
else:
break
b -= gap
j += gap
gap = gap // 2
print(items)
实现2：比较简洁的写法，把分子序列和插入排序的外部大循环结合到一起（因为分完子序列以后，每个子序列的每个元素也需要进行-gapd 插入的操作，分完再插和每个元素直接插效果是一样的,不如直接写在一起）
def shell_sort(items):
len_items = len(items)
gap = len_items // 2
while gap > 0:
# 不分子序列了，反正i=gap之后的元素都要在自己的子序列里面沉底，不如一起操作，把所有子序列放在一个遍历里面操作
for i in range(gap, len_items):
j = i
# 而且每个序列，排回去的最后一个元素其实不用操作，所以大于等于gap就可以了
while j >= gap:
if items[j] < items[j - gap]:
items[j], items[j - gap] = items[j - gap], items[j]
else:
break
# 得到新的步长
gap = gap // 2
print(items)
最优时间复杂度：根据步长序列的不同而不同
最坏时间复杂度：O(n2)
稳定想：不稳定
双指针+递归思路
关于快速排序的思路有很多，比如：
（1）在无序序列中取第一个数为mid_value，即这个值会把左右序列完全划分出来（即 数组变成：[[min],mid_value,[max]]），min里面所有值比mid_value小，max里面所有元素比mid_value大。但是min和max数组都是无序的
（2）如何划分min和max呢
（3）这样以后以52为界限的两个数组生成了，然后以递归方式对左右数组进行操作，直到数组长度=1.
由于设计到递归，所以输入参数中，需要标记递归的数组的起始点和终点：
方法1：完全按照上述思想，用一个flag指示low空还是high空
def quick_sort(items, start, end):
# 为什么要大于呢，比如到最后一次的时候，low=0了，（0, low - 1）=（0，-1）这时候需要跳出去，想的简单一点就是只有start= end:
return
low = start
high = end
mid_value = items[start]
low_empty = True
while low < high:
# 由于取出的mid在low的位置，所以现在low是空的，先对high操作
if low_empty:
if items[high] >= mid_value:
high -= 1
else:
items[low] = items[high]
low += 1
low_empty = False # 此时High是空的了
else:
# High是空的，对low操作
if items[low] <= mid_value:
low += 1
else:
items[high] = items[low]
high -= 1
low_empty = True
items[low] = mid_value
# 然后就是递归时刻
quick_sort(items, 0, low - 1) # 左边数列递归
quick_sort(items, low + 1, end - 1) # 右边数列递归
if __name__ == "__main__":
items1 = [54, 226, 93, 17, 77, 31, 44, 55, 20]
quick_sort(items1, 0, len(items1) - 1)
print(items1)
方法2：简单一点不用flag判断，在用循环找，直到找到items[high] 最优时间复杂度：O(nlogn) 为啥是nlogn? （1）在到达大小为一的数列前，我们只要作log n次嵌套的调用。这个意思就是调用树的深度是O(log n)。—即用一个logn的树去理解递归 （2）程序调用的每一层次结构总共全部仅需要O(n)的时间（每个调用有某些共同的额外耗费，但是因为在每一层次结构仅仅只有O(n)个调用，这些被归纳在O(n)系数中）。 （3） 快速排序通常比其他排序算法快得多，因为它在原地运行，而不需要创建任何辅助数组来保存临时值。 归并排序是采用分治法的一个非常典型的应用。归并排序的思想就是先递归分解数组，再合并数组。 （1）将数组分解最小之后 如此合并后：然后得到如上图4个数组，然后合并[26,54]和[17，93]然后如下操作： 实现：用两个函数实现，一个用来拆分，一个用来合并排序 递归=O(logn),归并=O(n)相乘得到O(nlogn) 二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。 折半查找方法适用于不经常变动而查找频繁的有序列表。 首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功； 否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功 方法1：非递归方法 方法2：递归（有两种形式，一种给起始和终止下标，一种不给，后一种更简洁）def quick_sort_opt(items, start, end):
if start >= end:
return
low = start
high = end
mid_value = items[start]
while low < end:
while low < end and items[high] > mid_value:
high -= 1
items[low] = items[high]
while low < end and items[low] < mid_value:
low += 1
items[high] = items[low]
items[low] = mid_value
# 然后就是递归时刻
quick_sort(items, 0, low - 1) # 左边数列递归
quick_sort(items, low + 1, end - 1) # 右边数列递归
2.3 快速排序的时间复杂度
最坏时间复杂度：O(n2)
稳定性：不稳定
在最好的情况，每次我们运行一次分区，我们会把一个数列分为两个几近相等的片段。这个意思就是每次递归调用处理一半大小的数列。
然后递归*单次循环=O(log n)*O(n)=O(n log n)
结果是这个算法仅需使用O(n log n)时间。
（2）然后开始合并两个有序数组
比如54和26合并，一个指针指向54 一个指向26，小的一项取出放最前面，然后直到两个数组剩最后一项，放新数组最后面。操作四次
（3）基本思路是比较两个数组的最前面的数，谁小就先取谁，取了后相应的指针就往后移一位。然后再比较，直至一个数组为空，最后把另一个数组的剩余部分复制过来即可。def merge_sort(items):
# 用递归思路拆分
len_items = len(items)
if len_items <= 1:
return items
# 拆分一半
mid = len_items // 2
# 一层层递归结束的时候，每层递归left和right返回的内容表示采用归并排序后得到的有序列表，然后我们需要把这两个再合并成一个更新的有序列表并返回，用merge实现
left = merge_sort(items[:mid]) # 切片不会包含尾部即[0，mid）
right = merge_sort(items[mid:])
return merge(left, right)
def merge(left, right):
ll, lr = len(left), len(right)
s1, s2 = 0, 0 # s1=left的头指针 s2=right的头指针
new = []
while s1 < ll and s2 < lr:
if left[s1] < right[s2]:
new.append(left[s1])
s1 += 1
else:
new.append(right[s2])
s2 += 1
# 剩下S2
if s1 >= ll and s2 < lr:
new += right[s2:]
if s2 >= lr and s1 < ll: # 剩下S1
new += left[s1:]
return new
if __name__ == "__main__":
items1 = [54, 226, 93, 17, 77, 31, 44, 55, 20]
sorted_items = merge_sort(items1)
print(sorted_items)
3.3 归并排序时间复杂度
最优时间复杂度：O(nlogn)
最坏时间复杂度：O(nlogn)
稳定性：稳定
但是归并好像用了很多的空间！！def binary_search(items, value):
len_items = len(items)
mid = 0
low = 0
high = len_items - 1
# 从mid开始查找
while low <= high:
mid = low + (high - low) // 2
if items[mid] == value:
return mid
else:
if items[mid] > value:
high = mid - 1
else:
low = mid + 1
return -1
def binary_search_rec(items, value, low, high):
mid = low + (high - low) // 2
if low > high:
return -1
if items[mid] == value:
return mid
else:
if items[mid] > value:
high = mid - 1
else:
low = mid + 1
result = binary_search_rec(items, value, low, high)
return result
def binary_search_rec_opt(items, value):
mid = len(items) // 2
if len(items) == 0:
return -1
if items[mid] == value:
return mid
else:
if items[mid] > value:
result = binary_search_rec_opt(items[:mid], value)
else:
result = binary_search_rec_opt(items[mid + 1:], value)
return result
