Python 关于下标的运用技巧（二分查找法 冒泡 选择 插入 归并 快速排序算法）

二分查找法（折半查找法）的递归实现

二分查找法（折半查找法）：用于预排序列表的查找问题，

再次强调，二分查找法要配合排序使用，只有排好序，才能使用二分查找法而且，待查找列表如果有重复值，只能查找到其中一个的位置时间复杂度：O(log2N)

我简单说一下下面代码中对于下标的使用，这样好理解

前提：

小括号()，不包含边界值中括号[]，包含边界值

举个例子：（2,6]表示的范围为下标2（不包含）到下标6（包含）

先看一下代码（列表长度为偶数，假定为10，待查找列表增序，返回待查找值的下标）

def _binarySearch(key, a, lo, hi):if lo >= hi:return -1mid = (lo + hi) // 2if(key < a[mid]):return _binarySearch(key, a, lo, mid)elif(key > a[mid]):return _binarySearch(key, a, mid+1, hi)else:return middef binarySearch(key, a):return _binarySearch(key, a, 0, len(a))if __name__ == '__main__':a = [1, 99, 101, 102, 203, 305, 415, 523, 666, 1000]key = int(input('请输入待查找关键字：'))print("关键字{0}位于列表索引（-1表示不存在）：{1}".format(key, binarySearch(key, a)))

再看上面代码中对于下标的玩法：

binarySearch()函数中对递归函数_binarySearch()的调用是这样的return _binarySearch(key, a, 0, len(a))

很明显下标范围为：[0, 10)

_binarySearch(key, a, lo, hi)中

lo代表左边界，包含

hi代表右边界，不包含

每次递归函数的调用中，下标范围：[lo, hi)_binarySearch()递归函数中关于中间下标mid = (lo + hi) // 2的取值是有含义的

如果列表长度是奇数，这个简单，mid取值为中间值，无需多说

如果列表长度是偶数，mid的取值其实是偏右的第一次调用递归函数

mid = (0+10)//2 = 5

此时，二分为三种情况，两种范围

待查找值 < a[5]，下标范围缩小为[0,5)待查找值 > a[5]，下标范围缩小为[6,10)待查找值 = a[5]，找到了呀，递归结束，返回待查找值的下标

假定待查找值为102

第二次递归：

mid = (0+5)//2 = 2，

(key = 102) > (a[2] = 101)

下标范围缩小为：[3,5)然后：

第三次递归：

mid = (3+5)//2 = 4，

(key = 102) < (a[4] = 203)

下标范围缩小为：[3,4)最后：

第四次递归：

mid = (3+4)//2 = 3，

key = 102，找到了呀，递归结束，返回待查找值的下标_binarySearch()递归函数的中止条件是左边界不小于右边界假如待查找值不是102，而是102.5呢？

继续上面的递归，第五次递归：

下标范围已缩小为[4,4)

出发终止递归的条件：lo >= hi

return -1意为没找到值所以每次递归（用下标把列表一分为二），左边界是包含值的，而右边界是不包含值的，这同时也影响了终止条件的判断条件（当左边界和右边界相等时，是查找不到值的）

二分查找法（折半查找法）的非递归实现

下面代码对于下标的玩法和上面的有一些不一样：

左边界low，右边界high都是包含值的

下标范围：[low, high]while循环的终止条件是low > high当列表长度为偶数时，mid = (low + high)//2，mid取值偏左

补充一嘴：mid其实也可以偏右的mid = (low + high)//2 + 1，不会影响代码的逻辑

列表长度为偶数，假定为10，待查找列表增序，返回待查找值的下标

def binarySearch(key, a):low = 0high = len(a) -1while low <= high:mid = (low + high)//2if(key > a[mid]):low = mid +1elif(key < a[mid]):high = mid -1else:return midreturn -1 if __name__ == '__main__':a = [1, 99, 101, 102, 203, 305, 415, 523, 666, 1000]key = int(input('请输入待查找关键字：'))print("关键字{0}位于列表索引（-1表示不存在）：{1}".format(key, binarySearch(key, a)))

如若待查找列表是降序，也并不难：

def binarySearch(key, a):low = 0high = len(a) -1while low <= high:mid = (low + high)//2if(key < a[mid]):low = mid +1elif(key > a[mid]):high = mid -1else:return midreturn -1 if __name__ == '__main__':a = [1000, 900, 800, 700, 600, 500, 400, 300, 200, 100]while 1:key = int(input('请输入待查找关键字：'))print("关键字{0}位于列表索引（-1表示不存在）：{1}".format(key, binarySearch(key, a)))

冒泡排序法

时间复杂度：O(N2)虽然最坏情况是n的平方，但是这种算法不仅仅适合于排序数组，还适用于链表，并且是稳定的 增序排序，方法一

def bubbleSort(a):for i in range(len(a)-1, -1, -1):for j in range(i):if a[j] > a[j+1]:a[j],a[j+1] = a[j+1],a[j]def main():a = [2, 97, 86, 64, 50, 80, 3, 71, 8, 76]bubbleSort(a)print(a)if __name__ == '__main__':main()

分析：

列表长度：10

外层循环i : [9, 0]，实际上i的范围可以缩小为[9, 1]，减

内存循环j : [0, i)，增

当 i 为 9 时，内层循环中的条件交换，将最大值像冒泡泡一样（j：从下标小处向下标大处），冒到下标最大的位置

当 i 为 8 时，将第二大值像冒泡泡一样，冒到下标第二大的位置

依此类推

降序排序，方法二

（将方法一中的内存循环的判断条件语句改一下即可，改为a[j] < a[j+1]）

def bubbleSort(a):for i in range(len(a)-1, 0, -1):for j in range(i):if a[j] < a[j+1]:a[j],a[j+1] = a[j+1],a[j]def main():a = [2, 97, 86, 64, 50, 80, 3, 71, 8, 76]bubbleSort(a)print(a)if __name__ == '__main__':main()

增序排序，方法三

def bubbleSort(a):for i in range(0, len(a)):for j in range(len(a)-1, i, -1):if a[j-1] > a[j]:a[j],a[j-1] = a[j-1],a[j]def main():a = [2, 97, 86, 64, 50, 80, 3, 71, 8, 76]bubbleSort(a)print(a)if __name__ == '__main__':main()

分析：

列表长度：10

外层循环i : [0, 9]，增

内存循环j : [9, i)，减

当 i 为 0 时，内层循环中的条件交换，将最小值像冒泡泡一样（j：从下标大处向下标小处），冒到下标最小的位置

当 i 为 1 时，将第二小值像冒泡泡一样，冒到下标第二小的位置

依此类推

降序排序，方法四

（将方法三中的内存循环的判断条件语句改一下即可，改为a[j] < a[j+1]）

def bubbleSort(a):for i in range(0, len(a)):for j in range(len(a)-1, i, -1):if a[j-1] < a[j]:a[j],a[j-1] = a[j-1],a[j]def main():a = [2, 97, 86, 64, 50, 80, 3, 71, 8, 76]bubbleSort(a)print(a)if __name__ == '__main__':main()

多说一嘴，与本文主题无关，不过，可以多了解一下嘛

冒泡和插入排序的效率都和逆序对的个数有关，每次相邻元素交换，刚好消去一对逆序对如果序列基本有序，则插入排序简单高效定理：任何仅以交换相邻两元素来排序的算法，其平均时间复杂度都是n的平方所以要提高算法效率，我们可以：每次消去不止一对逆序对——>每次交换相隔较远的两个元素于是：希尔排序（有插入排序的优点，又解决了插入排序每次交换只能消去一个逆序对的缺点，适用于上万数据的排序，但希尔排序还存在一个问题：增量元素不互质，则小增量可能根本不起作用，所以诞生了 Hibbard增量序列和 Sedgewick增量序列。本文不涉及这个算法…）

选择排序法

时间复杂度：O(N2) 增序排序，方法一

def selectionSort(a):for i in range(0, len(a)-1):for j in range(i+1, len(a)):if(a[j] < a[i]):a[i],a[j] = a[j],a[i]def main():a = [2, 97, 86, 64, 50, 80, 3, 71, 8, 76]selectionSort(a)print(a)if __name__ == '__main__':main()

分析：

列表长度：10

外层循环i : [0, 9)，增

内存循环j : [i+1, 9]，增

当 i 为 0 时，内存循环就是将[1, 9]范围内的数值全部与a[0]比较，小则交换（即：选择出最小值，给到下标最小处：这就是选择）

当 i 为 1 时，内存循环就是将[2, 9]范围内的数值全部与a[0]比较…

降序排序，方法二

def selectionSort(a):for i in range(0, len(a)-1):for j in range(i+1, len(a)):if(a[j] > a[i]):a[i],a[j] = a[j],a[i]def main():a = [2, 97, 86, 64, 50, 80, 3, 71, 8, 76]selectionSort(a)print(a)if __name__ == '__main__':main()

增序排序，方法三

def selectionSort(a):for i in range(len(a)-1, 0, -1):for j in range(0, i):if(a[j] > a[i]):a[i],a[j] = a[j],a[i]def main():a = [2, 97, 86, 64, 50, 80, 3, 71, 8, 76]selectionSort(a)print(a)if __name__ == '__main__':main()

分析：

列表长度：10

外层循环i : [9, 1]，减

内存循环j : [0, i-1]，增

当 i 为 9 时，内存循环就是将[0, 8]范围内的数值全部与a[9]比较，大则交换（即：选择出最大值，给到下标最大处）

当 i 为 8 时，内存循环就是将[0, 7]范围内的数值全部与a[8]比较…

降序排序，方法四

def selectionSort(a):for i in range(len(a)-1, 0, -1):for j in range(0, i):if(a[j] < a[i]):a[i],a[j] = a[j],a[i]def main():a = [2, 97, 86, 64, 50, 80, 3, 71, 8, 76]selectionSort(a)print(a)if __name__ == '__main__':main()

插入排序法

时间复杂度：O(N2)无论如何都是n的平方的情况，本算法效率的瓶颈在如何快速找到最小元，堆排序（这个算法本文不涉及）因此而生 增序排序，先给一个稍逊的法子，用来理解插入排序法（内层循环用的是for循环，会产生不必要的比较，浪费系统资源）

def insertSort(a):for i in range(1, len(a)):for j in range(i, 0, -1):if(a[j-1] > a[j]):a[j-1],a[j] = a[j],a[j-1]def main():a = [2, 97, 86, 64, 50, 80, 3, 71, 8, 76]insertSort(a)print(a)if __name__ == '__main__':main()

分析：

上面的代码不是插入排序哦！！！，用来理解过渡的

列表长度：10

外层循环i : [1, 9]，增

内存循环j : [i, 1]，减

增序排序，方法一（正确的方法：内层循环使用while循环语句）

def insertSort(a):for i in range(1, len(a)):j = iwhile (j > 0) and (a[j-1] > a[j]):a[j-1],a[j] = a[j],a[j-1]j -= 1def main():a = [2, 97, 86, 64, 50, 80, 3, 71, 8, 76]insertSort(a)print(a)if __name__ == '__main__':main()

分析：

列表长度：10

外层循环i : [1, 9]，增

内层循环，有两个判断条件，减（减多少次，不定次，这就是比上面代码的更优化处）

就像玩扑克牌时，我们手动将扑克牌增序排序：从左到右，看到小的就插在前面的合适位置

降序排序，方法二

def insertSort(a):for i in range(1, len(a)):j = iwhile (j > 0) and (a[j-1] < a[j]):a[j-1],a[j] = a[j],a[j-1]j -= 1def main():a = [2, 97, 86, 64, 50, 80, 3, 71, 8, 76]insertSort(a)print(a)if __name__ == '__main__':main()

增序排序，方法三

def insertSort(a):for i in range(len(a)-2, -1, -1):j = iwhile (j < len(a)-1) and (a[j+1] < a[j]):a[j+1],a[j] = a[j],a[j+1]j += 1def main():a = [2, 97, 86, 64, 50, 80, 3, 71, 8, 76]insertSort(a)print(a)if __name__ == '__main__':main()

分析：

列表长度：10

外层循环i : [8, 0]，减

内层循环，增

从右向左手动将扑克牌增序排序，看到大的就插在后面的合适位置

降序排序，方法四

def insertSort(a):for i in range(len(a)-2, -1, -1):j = iwhile (j < len(a)-1) and (a[j+1] > a[j]):a[j+1],a[j] = a[j],a[j+1]j += 1def main():a = [2, 97, 86, 64, 50, 80, 3, 71, 8, 76]insertSort(a)print(a)if __name__ == '__main__':main()

归并排序法

时间复杂度：O(N·log2N)

def merge(left, right):merged = []i, j = 0, 0left_len, right_len = len(left), len(right)while i < left_len and j < right_len:if left[i] <= right[j]:merged.append(left[i])i += 1else:merged.append(right[j])j += 1merged.extend(left[i:])merged.extend(right[j:])return mergeddef mergeSort(a):if len(a) <= 1:return amid = len(a) // 2left = mergeSort(a[:mid])right = mergeSort(a[mid:])return merge(left, right)def main():a = [59, 12, 77, 64, 72, 69, 46, 89, 31, 9]print(mergeSort(a))if __name__ == '__main__':main()

思路很存粹，

运用递归将待排序列表进行二分，分到只剩一个数据（即：mergeSort()）

然后，到了一个临界点，

mergeSort()递归开始回溯的时候，执行merge()（作用：将两个相同排序的序列，进行排序）

补充：这三句这么理解

mid = len(a) // 2left = mergeSort(a[:mid])right = mergeSort(a[mid:])

（例子）倘若序列长度为偶数：

>>> a = [0,1,2,3,4,5,6,7,8,9]>>> a[:5][0, 1, 2, 3, 4]>>> a[5:][5, 6, 7, 8, 9]

（例子）倘若序列长度为奇数：

>>> a = [0,1,2,3,4]>>> a[:2][0, 1]>>> a[2:][2, 3, 4]

快速排序法

时间复杂度：O(N·log2N)

最好情况：每次正好中分，为NlogN

最糟糕的情况是：主元刚好是最小值，为n的平方快速排序是对冒泡排序的改进（在传说中：在现实应用领域中最快的一种排序算法。其实在现实生活中没有任何一种算法在任何情况下都是最好的）快速排序用的是分而治之的策略，难点在于选择主元和分子集

主元不适合随机取（因为random() 函数要花费时间的，不值得）

主元可以取头、中、尾的中位数快速排序的问题：它要用递归，所以对于小规模的数据（例如N不到100）可能还不如插入排序快

递归很消耗资源怎么解决这个问题呢（当递归的数据规模充分小，则停止递归，直接调用简单排序（例如插入排序））

def quickSort(a, low , high):i = lowj = highif i >= j:return akey = a[i]while i < j:while i < j and a[j] >= key:j -= 1a[i] = a[j]while i < j and a[i] <= key:i += 1a[j] = a[i]a[i] = keyquickSort(a, low, i-1)quickSort(a, j+1, high)def main():a = [59, 12, 77, 64, 72, 69, 46, 89, 31, 9]quickSort(a, 0, len(a)-1)print(a)if __name__ == '__main__':main()

简单理解：使用一个待排序序列中选取的key，将待排序序列分割为两部分，一部分的数据都比另一部分的数据大，中间即为选取的key

呈左右夹击之势来进行数据的交换依次递归，顺序就排好了