排序算法总结

简单总结一下几种常见的排序算法,包括冒泡排序、选择排序、插入排序、快速排序和堆排序

冒泡排序

  • 平均时间复杂度O(n^2);最坏时间复杂度O(n^2);空间复杂度O(1);稳定
  • 算法原理
    从后往前,相邻两个数中较小的数放在前面,一次遍历下来,第一个就是最小的数;
    如此往复,数组前头就一直是有序数组,只需要冒泡后面的无序数组就行
  • python实现
    1
    2
    3
    4
    5
    6
    7
    def bubble_sort(arr):
    # 总共执行 总长-1 次
    for i in xrange(len(arr)-1):
    # 从最后开始 相邻两个较小的数放在前面
    for j in range(len(arr)-1 , i, -1):
    if arr[j] < arr[j-1]:
    arr[j], arr[j-1] = arr[j-1], arr[j]

选择排序

  • 平均时间复杂度O(n^2);最坏时间复杂度O(n^2);空间复杂度O(1);不稳定
  • 算法原理
    找出数组中最小的与第一位替换;
    这样数组前面就形成了有序数组,后面则是无序数组;
    再找出无序数组中最小的与第二位替换,以此类推
  • python实现
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    def select_sort(arr):
    for i in xrange(len(arr)):
    #记录最小值的索引
    index = i
    #找到最小值
    for j in range(i+1, len(arr)):
    if arr[j] < arr[index]:
    index = j
    #替换最小值
    if index != i:
    arr[i],arr[index] = arr[index],arr[i]

插入排序

  • 平均时间复杂度O(n^2);最坏时间复杂度O(n^2);空间复杂度O(1);稳定
  • 算法原理
    先把数组第一个元素看作有序数组;
    同样的,数组前面就形成了有序数组,后面则是无序数组;
    从第二个元素开始,找到该元素应该插入到有序数组的位置,并插入,以此类推
  • python实现
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    def insert_sort(arr):
    for i in range(1, len(arr)):
    j = i - 1
    #把准备插入的这个元素值先存起来
    temp = arr[i]
    #把比这个元素大的元素后移一位
    while j >= 0 and temp < arr[j]:
    arr[j+1] = arr[j]
    j -= 1
    #插入
    arr[j+1] = temp

快速排序

  • 平均时间复杂度O(nlogn);最坏时间复杂度O(n^2);空间复杂度O(logn);不稳定
  • 算法原理
    以一个值位中间点,一开始就以数组的第一个元素作为中间点,把数组分为小于这个数的数组和大于这个数的数组;
    再把分开的这两个数组分别重复上面的操作,直到全部完成,该操作一般用递归完成;
  • python实现
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    def quick_sort(arr):
    if len(arr) <= 1:
    return arr
    # 小数组
    less = []
    # 大数组
    greater = []
    # 取第一个值作为中间值
    pivot = arr.pop()
    # 判断元素并加入大小数组
    for item in arr:
    if item < pivot:
    less.append(item)
    else:
    greater.append(item)
    arr.append(pivot)
    # 递归结果
    return quick_sort(less) + [pivot] + quick_sort(greater)

堆排序

  • 平均时间复杂度O(nlogn);最坏时间复杂度O(nlogn);空间复杂度O(1);不稳定
  • 算法原理
    首先,我。。太难用文字解释了,先看下这个视频吧,传送门;
    ok,然后堆就是指视频里的二叉堆,上图:
    那么堆的存储结构就是这样的,上图:

    以上两个结构之间的对应是有这样的关系的:一个节点的子节点的索引就是2*i+12*i+2,反过来,父节点的下标就为子节点的(i-1)/2,此为后面编程的理论基础;
    有了这些概念以后,才是算法步骤啦;
    首先,如视频里的步骤,把整个数组先变成最大堆;
    然后,堆顶肯定是最大的数吧~那就和最后一位交换一下,那么数组末尾就是有序数组啦;
    此时那个最大值已经踢出堆了,那就再把剩下的堆变成最大堆,堆顶就又是最大值,重复上面的操作即可;
    文字真的很难懂,还是建议看上面那个视频,对程序员来说没有“墙”这回事吧?
  • python实现
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    def heap_sort(arr):
    def sift_down(start, end):
    root = start
    while True:
    child = 2 * root + 1
    if child > end:
    break
    if child + 1 <= end and arr[child] < arr[child + 1]:
    child += 1
    if arr[root] < arr[child]:
    arr[root], arr[child] = arr[child], arr[root]
    root = child
    else:
    break

    for start in xrange((len(arr) - 2) // 2, -1, -1):
    sift_down(start, len(arr) - 1)

    for end in xrange(len(arr) - 1, 0, -1):
    arr[0], arr[end] = arr[end], arr[0]
    sift_down(0, end - 1)

    return arr

TODO

其实还有其他排序算法的,比如并规排序、希尔排序、二叉树排序等等,以后有机会再总结