关于Python的排序算法

　　各类排序对比

　　排序方法　　稳定性　　最好复杂度　　最坏复杂度　　期望复杂度

　　冒泡排序　　稳定　　O(n)O(n)O(n)　　O(n2)O(n^2)O(n2)　　O(n2)O(n^2)O(n2)

　　选择排序　　稳定　　O(n2)O(n^2)O(n2)　　O(n2)O(n^2)O(n2)　　O(n2)O(n^2)O(n2)

　　插入排序　　稳定　　O(n)O(n)O(n)　　O(n2)O(n^2)O(n2)　　O(n2)O(n^2)O(n2)

　　快速排序　　不稳定　　O(n)O(n)O(n)　　O(n2)O(n^2)O(n2)　　O(nlogn)O(nlogn)O(nlogn)

　　归并排序　　稳定　　O(nlogn)O(nlogn)O(nlogn)　　O(nlogn)O(nlogn)O(nlogn)　　O(nlogn)O(nlogn)O(nlogn)

　　冒泡排序

　　核心思路是与相邻的元素比较大小，交换位置。

　　具体步骤可分为外循环和内循环：

　　外循环每一步将数组中最大的元素“沉”到数组末尾(升序排列的情况下);

　　内循环每一步按照大小交换相邻元素的位置。

　　原数组： [1,2,9,9,4,5,6,6,3,9,4]

　　内循环第一步：将元素1与元素2进行比较，不交换位置(升序);

　　内循环第二步：将元素2与元素9进行比较，不交换位置;

　　内循环第三步：将元素9与元素9进行比较，不交换位置;

　　内循环第四步：将元素9与元素4进行比较，交换位置为 [1,2,9,4,9,5,6,6,3,9,4];

　　内循环第五步：将元素9与元素5进行比较，交换位置为 [1,2,9,4,5,9,6,6,3,9,4];

　　内循环第六步：将元素9与元素6进行比较，交换位置为 [1,2,9,4,5,6,9,6,3,9,4];

　　...

　　内循环最后一步：将元素9与元素6进行比较，交换位置为 [1,2,9,4,5,6,6,3,9,4,9];

　　外循环第一步即为内循环的结果，将元素9沉到末尾，为[1,2,9,4,5,6,6,3,9,4,9];

　　外循环第二步：将第二个元素9沉到末尾，为[1,2,4,5,6,6,3,9,4,9,9];

　　外循环第三步：将第三个元素9沉到末尾，为[1,2,4,5,6,3,6,4,9,9,9];

　　外循环第四步：将第三个元素9沉到末尾，为[1,2,4,5,3,6,4,6,9,9,9];

　　...

　　外循环最后一步：得到最终结果[1,2,3,4,4,5,6,6,9,9,9]。

　　算法实现

　　冒泡排序是一种稳定排序;

　　最优情况下，数组都为正序，时间复杂度为O(n)O(n)O(n);

　　最坏情况为逆序，时间复杂度为O(n2)O(n^2)O(n2)。

　　def bubbleSort(nums):

　　if len(nums) < 2:

　　return nums

　　# 因为后面index要加1进行比较，所以这里是len(nums) - 1

　　for i in range(len(nums)-1):

　　# -i是已经将i个元素沉到末尾

　　for j in range(len(nums)-i-1):

　　if nums[j] > nums[j+1]:

　　nums[j], nums[j+1] = nums[j+1], nums[j]

　　return nums

　　选择排序

　　核心思想是将剩余元素中最小(最大)的元素取出来，放在首位(末尾)。

　　具体步骤为：

　　遍历n个元素，找到其中最小的元素放在首位;

　　遍历剩下的n-1个元素，找到其中最小的元素放在首位;

　　重复上述步骤，直到数组有序。

　　算法实现

　　选择排序的时间复杂度跟初始状态无关，为O(n2)O(n^2)O(n2)。

　　def selectionSort(nums):

　　if len(nums) < 2:

　　return nums

　　for i in range(len(nums)-1):

　　min_index = i

　　for j in range(i+1,len(nums)):

　　if nums[j] < nums[min_index]:

　　min_index = j

　　nums[min_index], nums[i] = nums[i], nums[min_index]

　　return nums

　　插入排序

　　核心思想是在已经部分有序的数组中，寻找合适的位置并插入新元素。

　　具体步骤如下：

　　从数组的第二个元素开时，判断与前一个元素的大小，进行位置交换;

　　到第三个元素，前两个元素已经有序了，按大小寻找合适的位置，插入第三个元素;

　　如此类推，直到所有的元素都处于合适的位置。

　　算法实现

　　插入排序是一种稳定排序，最优情况下，数组都为正序，时间复杂度为O(n)O(n)O(n)。最坏情况为逆序，时间复杂度为O(n2)O(n^2)O(n2)。

　　def insertSort(nums):

　　if len(nums) < 2:

　　return nums

　　for i in range(1,len(nums)):

　　value = nums[i]

　　j = i - 1

　　while j >= 0 and nums[j] > value:

　　nums[j+1] = nums[j]

　　j -= 1

　　nums[j+1] = value

　　return nums

　　if __name__ == "__main__":

　　nums = [1,2,9,9,4,5,6,6,3,9,4]

　　print(insertSort(nums))

　　输出：[1, 2, 3, 4, 4, 5, 6, 6, 9, 9, 9]

　　快速排序

　　核心思想是分而治之。具体步骤如下：

　　在数组中选择一个元素作为基准，可以取任意值，但一般取中值帮助理解;

　　数组中所有的数组都与基准进行比较，比基准小就移动基准的左边，比基准大就移动到基准右边;

　　以基准两边的子数组作为新数组，重复第一二步，直到子数组剩下一个元素。

　　分治思想的排序在处理大数据集的效果比较好，小数据性能差一些，规模达到一定小时改用插入排序。

　　算法实现

　　快排是一种不稳定排序，其期望时间复杂度为O(nlogn)O(nlogn)O(nlogn)，最坏情况时间复杂度为O(n2)O(n^2)O(n2)。

　　快排的实现多种多样，选取一个最好理解的：分治+递归。

　　def quickSort(nums):

　　if len(nums) < 2:

　　return nums

　　mid = nums[len(nums)//2]

　　left, right = [], []

　　nums.remove(mid)

　　for num in nums:

　　if num >= mid:

　　right.append(num)

　　else:　无锡妇科医院 http://www.bhnnk120.com/

　　left.append(num)

　　return quickSort(left) + [mid] + quickSort(right)

　　if __name__ == "__main__":

　　nums = [1,2,9,9,4,5,6,6,3,9,4]

　　print(quickSort(nums))

　　输出：[1, 2, 3, 4, 4, 5, 6, 6, 9, 9, 9]

　　归并排序

　　归并排序也应用了分治的思想，主要步骤如下：

　　把初始序列的n个元素都看作是有序的子序列;

　　进行两两归并，有序序列的长度增加一倍;

　　重复上述步骤，直到得到一个长度为n的有序序列。

　　可以结合下图观察：

　　一开始将序列[38, 27, 43, 3, 9, 82, 10]分为7个长度为1的序列;

　　进行两两归并，得到4个有序序列[27,38]，[3,43]，[9,82]，[10];

　　再次进行两两归并，得到两个有序序列[3,27,38,43]，[9,10,82];

　　直到最后归并为一个长度为7的有序序列[3,9,10,27,38,43,82]

　　算法实现

　　归并排序是一种稳定排序，最好最差时间复杂度均为O(nlogn)O(nlogn)O(nlogn)，因此期望复杂度也为O(nlogn)O(nlogn)O(nlogn)。

　　def merge(left, right):

　　res = []

　　i, j = 0, 0

　　while i < len(left) and j < len(right):

　　if left[i] <= right[j]:

　　res.append(left[i])

　　i += 1

　　else:

　　res.append(right[j])

　　j += 1

　　if i == len(left):

　　res += right[j:]

　　else:

　　res += left[i:]

　　return res

　　def mergeSort(nums):

　　if len(nums) <= 1: return nums

　　mid = len(nums)//2

　　left = mergeSort(nums[:mid])

　　right = mergeSort(nums[mid:])

　　return merge(left, right)

　　简化写法

　　以.pop代替两个指针的操作(.pop时间复杂度为O(1)O(1)O(1));

　　返回不判断 left 还是 right 为空，因为必然一个为空，另一个不为空;

　　left 和 right 有序，所以直接拼接起来即可。

　　def merge(left, right):

　　res = []

　　while left and right:

　　if left[0] <= right[0]:

　　res.append(left.pop(0))

　　else:

　　res.append(right.pop(0))

　　return res + left + right

　　def mergeSort(nums):

　　if len(nums) <= 1: return nums

　　mid = len(nums)//2

　　left = mergeSort(nums[:mid])

　　right = mergeSort(nums[mid:])

　　return merge(left, right)

　　2019.7.15 补充插入排序

　　2019.7.16 补充冒泡排序，选择排序，增加对比表格

　　2019.7.30 补充归并排序