python3--说简单也不简单的排序算法

　　在刚开始接触算法时,我们可能一脸懵,不知从何处下手,尤其是现在使用的语言五花八门,各种语言的实现又不尽相同,所以,在这种情况下,千万不能迷失了自己,掌握了算法的原理,就像解数学公式一样,定理给你了,仔细想想便可以用代码来实现它,前提要养成良好的解题思路.

下面我们来从入门的排序算法开始:

以下都是针对一个无序数组 A = [3,1,5,6,7,2,4,8] 进行排序

1.简单的冒泡排序

初进排序算法,那就来试一下冒泡吧,原理和暴力枚举法差不多,极尽可能的把所有元素都枚举出来,一个个对比,做法简单而又粗暴(很*很暴力).

下面上代码:

'''

冒泡排序算法

'''

def bubblesorft(A):

    for i in range(len(A)):#第一层循环,控制排序的次数

        for j in range(len(A)-i):#第二层循环,控制前一个元素与后一个元素比大小

            if j+1 < len(A):

                if A[j] > A[j+1]:

                    temp = A[j+1]

                    A[j+1] = A[j]

                    A[j] = temp

    return A

A = [3,1,5,6,7,2,4,8]

A = bubblesorft(A)

print(A)

[1, 2, 3, 4, 5, 6, 7, 8]

算法简单,清晰明了,如果看不懂,那就自己敲几遍代码,你很快就会悟了,哈哈

这都不算完,接下来上个简单而又不简单的归并排序算法,你再来悟一下:

2.简单而又不简单的归并排序

说简单是因为你悟透了,说不简单是递归很绕人,其实想明白了何时return,就想明白了此时递归的值.

归并排序在排序时先将数组分成两部分,并分别进行排序,然后再把排好序的两部分整合成一个排序数组.

下面上代码感受一下:

'''

归并排序算法

'''

def mangesorft(A):

    if len(A) <= 1:

        return A

    half = int(len(A) / 2)#把列表分成两份

    first = mangesorft(A[0:half])#使用了递归,使得最后分的元素越来越小,直至到一个元素,然后返回排序好的列表

    second = mangesorft(A[half:len(A)])#使用了递归,使得最后分的元素越来越小,直至到一个元素,然后返回排序好的列表

    i = 0

    j = 0

    newA = []

    while i < len(first) or j < len(second):#控制循环次数

        if i <len(first) and j < len(second):#归并排序的重点,控制归并的元素下标

            if first[i] <= second[j]:

                newA.append(first[i])

                i += 1

            else:

                newA.append(second[j])

                j += 1

        else:

            if i < len(first):

                newA.append(first[i])

                i += 1

            if j < len(second):

                newA.append(second[j])

                j +=1

    return newA

if __name__ == "__main__":

    A = [3,1,5,6,7,2,4,8]

    A = mangesorft(A)

    print(A)

[1, 2, 3, 4, 5, 6, 7, 8]

对比这两个算法,你有啥想法了没有,如果有,那么恭喜你,咱们可以一起拉着小手跳入算法的坑了,

有了这两个神器,以后遇到算法问题,对于无序的数组或列表,那咱就先来排个序吧,这可是解题的第一步,加油!

顺带讲两个列表和数组去重的小知识(有面试题考过):

A = [1,1,2,2,3,3,4,4,5,5,6,6,7,7]

#普通方法去重

newA = []

def deletequemnents(A):

    for i in A:

        if i in A:

            if i not in newA:

                newA.append(i)

    return newA

print(deletequemnents(A))

#使用python内置函数set去重

def deletequemn(A):

    for i in A:

        A = set(A)

    return A

print(deletequemn(A))

巴特西

python3--说简单也不简单的排序算法

1.简单的冒泡排序

2.简单而又不简单的归并排序

最新文章

热门文章