常见算法知识 一

常见算法知识 一

常用排序

名称|复杂度|说明|备注
—|—|—|—
冒泡排序Bubble Sort| O(NN)|将待排序的元素看作是竖着排列的“气泡”,较小的元素比较轻,从而要往上浮|
插入排序Insertion sort | O(N
N)|逐一取出元素,在已经排序的元素序列中从后向前扫描,放到适当的位置|起初,已经排序的元素序列为空
选择排序|O(N*N)|首先在未排序序列中找到最小元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小元素,然后放到排序序列末尾。以此递归。|
快速排序Quick Sort|O(n *log2(n))|先选择中间值,然后把比它小的放在左边,大的放在右边(具体的实现是从两边找,找到一对后交换)。然后对两边分别使用这个过程(递归)。|
堆排序HeapSort|O(n *log2(n))|利用堆(heaps)这种数据结构来构造的一种排序算法。堆是一个近似完全二叉树结构,并同时满足堆属性:即子节点的键值或索引总是小于(或者大于)它的父节点。|近似完全二叉树
希尔排序SHELL|O(n1+£)0<£<1|选择一个步长(Step),然后按间隔为步长的单元进行排序.递归,步长逐渐变小,直至为1.|
箱排序Bin Sort|O(n)|设置若干个箱子,把关键字等于 k 的记录全都装入到第k 个箱子里 ( 分配 ) ,然后按序号依次将各非空的箱子首尾连接起来 ( 收集 ) 。|分配排序的一种:通过" 分配 " 和 " 收集 " 过程来实现排序。

冒泡排序(Bubble Sort)

冒泡排序wiki

冒泡排序(Bubble Sort),是一种计算机科学领域的较简单的排序算法。

它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。
这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端,故名。

因为内部有两层循环因此效率较低

slist = [ 9,1,22,31,45,3,6,2,-11 ]
for j in range(len(slist)):
    for i in range(len(slist) - j- 1): # -1 是因为每次比对的都 是i 与i +1,不减1的话,最后一次对比会超出list 获取范围,-j是因为,每一次大loop就代表排序好了一个最大值,放在了列表最后面,下次loop就不用再运算已经排序好了的值 了
        if slist[i] > slist[i+1]: #switch
            tmp = slist[i]
            #假如大于则交换位置
            slist[i] = slist[i+1]
            slist[i+1] = tmp
    print(slist)
print(slist)

插入排序Insertion sort

插入排序wiki

插入排序(英语:Insertion Sort)是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,通常采用in-place排序(即只需用到 O(1)}的额外空间的排序),因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。

插入排序(Insertion Sort)的基本思想是:将列表分为2部分,左边为排序好的部分,右边为未排序的部分,循环整个列表,每次将一个待排序的记录,按其关键字大小插入到前面已经排好序的子序列中的适当位置,直到全部记录插入完成为止。

slist = [ 9,1,-22,9,31,-5,45,3,6,2,11 ]
for i in range(len(slist)):
    while i > 0 and slist[i] < slist[i-1]:# 右边小于左边相邻的值 如果一直成立则一直交换
        tmp = slist[i]
        slist[i] = slist[i-1]
        slist[i-1] = tmp
        i -= 1
print(slist)

选择排序

选择排序wiki

选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,一般来说人为认定列表第一个为最小。然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。

选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上,则它不会被移动。选择排序每次交换一对元素,它们当中至少有一个将被移到其最终位置上,因此对 n个元素的表进行排序总共进行至多n-1次交换。在所有的完全依靠交换去移动元素的排序方法中,选择排序属于非常好的一种。

slist = [ 9,1,22,31,45,3,6,2,11 ]
smallest_num_index = 0 #初始列表最小值,默认为第一个
for j in range(len(slist)):
    #外部循环取值 内部循环做交换
    for i in range(j,len(slist)):
        if slist[i] < slist[smallest_num_index]: #当前值 比之前选出来的最小值 还要小,那就把它换成最小值
            smallest_num_index = i
    else:
        print("smallest num is ",slist[smallest_num_index])
        tmp = slist[smallest_num_index]
        slist[smallest_num_index] =  slist[j]
        slist[j] = tmp
    print(slist)

发表评论

电子邮件地址不会被公开。 必填项已用*标注