排序算法原理与实现[冒泡、选择、插入、快速、哈希、计数](

1. 冒泡排序:

原理

冒泡排序算法的基本原理就是比较相邻两个数字的大小。将两个数中比较大的那个数交换到靠后的位置，不断交换下去就可以将最大的那两个数放到队列的尾部。然后重头再次交换)(交换list.lenght-1次)，直到将数列排成有序数列。

代码实现

# -*- coding:utf-8 -*-
"""
Author: leadingme
Mail:leadingme@qq.com
MyWebsite:leadingme.top
"""
import timeit
List = [7, 5, 9, 3, 5, 1, 12, 10, 15, 9]
def bubbleSort(List):
    """
    冒泡排序
    :param List:
    :return:
    """
    if len(List) = List[j+1]:
                List[j], List[j+1] = List[j+1], List[j] # 如果前一个数比后一个数大，则调换位置
    return List
if __name__ == '__main__':
    print(List)
    print(bubbleSort(List))
    runtime = timeit.timeit("bubbleSort(List)","from __main__ import bubbleSort, List",number=1000)
    print(runtime)

原理

简单来说，选择排序只做了一件事件，那就是从数列中选择最大(最小)的那个数，将这个数放到合适的位置。然后抛开这个数的子序列中找最大(最小)的那个数放到合适的位置。然后一直到子序列为空。

代码实现

# -*- coding:utf-8 -*-
"""
Author: leadingme
Mail:leadingme@qq.com
MyWebsite:leadingme.top
"""
from timeit import timeit
List = [7, 5, 9, 3, 5, 1, 12, 10, 15, 9]
"""
# 这个虽简洁易懂，但有重复数字会有有Bug，原因为相同数下标无法确定
def selectSort(List):
    if len(List) = min(List[i+1:]): # 如果对应下标数的值大于剩余部分的最小值，交换位置
            minIndex = List.index(min(List[i+1:])) # 求剩余部分的最小值小标
            List[i], List[minIndex] = List[minIndex], List[i] #满足条件, 交换位置
    return List
"""
def selectSort(List):
    if len(List) <= 1:   # 如果长度小于等于1，直接返回
        return List
    for i in range(len(List)-1):
        min_index = i
        for j in range(i+1,len(List)):
            if List[j] < List[min_index]:
                min_index = j
        List[i], List[min_index] = List[min_index], List[i]    return List
if __name__ == '__main__':
    print(List)
    print(selectSort(List))
    print(timeit('selectSort(List)','from __main__ import selectSort, List',number=1000))

原理

插入排序首先将数列分为两部分，数列的第一数为left，其余数位right部分。然后将right部分中的数逐一取出，插入到left部分的适当位置。当right部分为空时，left部分就成了一个有序的序列。

 1/4    1 2 3 4 下一页 尾页