选择排序

算法速度：通过大O表示法表示，O(n)，n是操作数，表示算法执行的次数；

数组：是有序的元素序列；若将有限个类型相同的变量的集合命名，那么这个名称为数组名；

链表：是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的；

两者特点：数组容易读取，根据索引位置直接获取元素，但如果要向数组增加或删除元素，那么需要改变部分数组位置对应的元素（中间插入或删除）；

链表在删除与增加元素时会根据上一个元素的位置进行，但读取内容的只能按照顺序读取；

所以数组可用于随机访问，链表是顺序访问，在运行时间上可以表示数组为O(1),链表为O(n);

1.升降序实现

通过Python实现数组的降序或者升序排列，如下：

def data_sort(arr,dim): #dim = 0:升序；dim = 1：降序

    ultimate = arr[0] #0位置用来存储最值

    ultimate_index = 0 #变量声明，存储当前最值的索引

    if dim == 0:

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

                if arr[i] < ultimate:

                    ultimate = arr[i]

                    ultimate_index = i

        return ultimate_index

    if dim == 1:

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

                if arr[i] > ultimate:

                    ultimate = arr[i]

                    ultimate_index = i

        return ultimate_index

def selectionSrot(arr,dim):

    newarr = []

    if dim == 0 or dim == 1:

        for i in range(len(arr)):

            ultimate = data_sort(arr,dim)

            newarr.append(arr.pop(ultimate))

        return newarr

    else:

        print('Please Verify the value of "dim"')

data = list(range(1,101))

print (selectionSrot(data,1))

2.注意事项

通过dim设置升序或者降序，同时要考虑这两种情况之外的冗余处理；
数组升序或者降序排序要完成这个功能，首先需要确定数组n中的最值索引，最坏情况（最大算法运行时间）即O(n),对数组中的n个数采用for轮询比较确定（数组的读取），再通过该索引通过pop进行新的数组构建（新数组的写入），同时也删除了原数组的元素（原数组的写删除），新数组的写入运行时间也是O(n),算法总运行时间是O(n*n);
采用list(range())函数用法创建一个有序的数组；
空数组定义采用如：newarr = []；
运用到的变量声明如：ultimate_index = 0；

巴特西

[02]Sort选择排序

选择排序

1.升降序实现

2.注意事项

最新文章

热门文章