排序算法.

排序算法是最常用的一种算法.它解决的主要问题是在一定的时间复杂度和空间复杂度的条件下,对n个数按照一定的顺序进行排序.排序算法主要分为四大类,即插入类,交换类,选择类和归并类,不同的排序算法的时间复杂程度和空间复杂程度差别很大.

排序算法主要有以下几种:

1.插入类排序算法

2.交换类排序算法

3.选择类排序算法

4.选择类排序算法

5.归并类排序算法

本节我们学习:直接插入排序法.

假设有一待排序集合A={a1,a2,a3...an},采用直接插入排序法过程如下:

1.从集合的起始位置出发,将a1视为只有一个元素的有序子集合B.

2.从a2开始,依次将a2到an按照一定顺序(正序或逆序)插入前面的有序子集合B中,最终得到的有序子集合B就是最终排序后的集合A

因此,插入的过程可以被视为一个不断比较的过程,元素ai与当前已有的有序自己和B中的元素逐个进行比较,找到ai应该插入的位置,每插入一个元素加入有序子集合B都要逐个比较.此算法虽然易懂但是复杂程度高.

若有一个集合A={50,36,66,76,95,12,25}采用直接插入排序法进行排序的过程如图所示:

图中,箭头表示的是排序过程中元素的移动及插入.

用python实现直接插入排序法,定义名为Insertsort的直接插入排序函数,变量如下:

1.nums变量:表示待排序组名,为list类型

2.key变量:表示当前正在向子集合插入的元素值.因为随着前面元素的向后运动,该元素会被覆盖,所以需要提前保存该元素的值

函数定义如下:

def insertsort(nums):
    # 遍历从第二个元素开始到最后一个元素
    for i in range(1, len(nums)):
        # key是当前要插入的元素
        key = nums[i]
        # j是key当前位置的前一个位置
        j = i - 1
        # 当j不小于0且key小于nums[j]时，将nums[j]向后移动一个位置
        while j >= 0 and key < nums[j]:
            nums[j + 1] = nums[j]
            j -= 1
        # 将key插入到正确的位置
        nums[j + 1] = key
    # 返回排序后的数组
    return nums

注意,这里接受的nums是列表类型.

测试:

x=[5,4,10,6,10]

输出:

[4, 5, 6, 10, 10]