Python基本的排序算法比较，sorted的实现方法

算法与数据结构基础

查找算法：

二分查找法：

简介：二分查找法又被称为折半查找法，用于预排序的查找问题

过程：

1. 如果在列表a中查找元素t，先将列表a中间位置的项与查找关键字t比较，如果两者相等，则成功。
2. 否则，将表分为前后两个子表
3. 如果中间位置大于t，则进一步查找前一子表，否则，查找后一子表
4. 重复上述过程

优劣：

1. 时间复杂度为O(log2N),比较快
2. 缺点就是必须是有序列表

排序算法：

冒泡排序

简介：两两比较大小，如果不满足升序关系，则交换

过程：略

优劣：：

1. 时间复杂度为O(N2)，速度较慢
2. 稳定

选择排序

简介：找出最小值，然后放入一个新的列表中

过程：略

优劣：：

1. 时间复杂度为O(N2)，速度较慢
2. 稳定

插入排序法

简介：依次检查需要排序的列表，每次取出一个元素放入另一个排好序的列表中的适当位置。

过程：略

优劣：：

1. 时间复杂度为O(N2)
2. 速度不稳定，最佳情况为线性增长，最差情况为N2,所以速度实际上比前两种快

归并排序

简介：分而制之的思想

过程：

1. 将包含N个元素的列表分为两个含N/2元素的子列表.
2. 对两个子列表递归调用归并排序(最后将两个子列表分解为N个子列表)。
3. 合并已排序好的列表。

劣：：速度较快且稳定，时间复杂度为O(Nlog2N)

实现代码:

def merge(left,right):
    merged = []
    i,j = 0,0
    left_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 += 1
        else:
            merged.append(right[j])
            j += 1
        merged.extend(left[i:])
        merged.extend(right[j:])        return mergeddef mergeSort(a):    if len(a) <= 1:        return a    else:        mid = len(a) // 2
        left = mergeSort(a[:mid])        right = mergeSort(a[mid:])        merge(left,right)        return merge(left,right)def main():
    a = [59,12,77,64,72,69,46,89,31,9]
    a1 = mergeSort(a)
    print(a1)if __name__ == '__main__':    main()

快速排序 #：

简介：对冒泡排序的改进

过程：

1. 设置两个变量i和j，作为列表首末两端的下标，即i=0，j=N-1
2. 设置列表的第一个元素作为关键数据，即key=A[0]
3. 从j开始向前搜索，找到第一个小于key的值A[j],将A[j]和A[i]互换
4. 从i开始向后搜索，找到第一个大于key的值A[i],将A[i]和A[j]互换
5. 重复3~4步，直到i = j

优劣：：

1. 平均情况时间复杂度为O(Nlog2N),比较快。
2. 最差情况下时间复杂度为O(N2)

Python语言中提供的排序算法

内置数据类型list的方法sort()，内置函数sorted()

这个的底层实现就是归并排序，只是使用了Python无法编写的底层实现，从而避免了Python本身附加的大量开销,速度比我们自己写的归并排序要快很多（10~20倍）,所以说我们一般排序都尽量使用sorted和sort