经典排序算法python实现 – Python量化投资

经典排序算法python实现

最近在复习经典排序算法,自己用python也实现了一下,这里不会涉及到原理(因为网上方法已经很详细啦),就把函数贴上来,可以让大家自己试着运行下,再结合别处的原理也可以更好地理解它们的实现。
如果有错误请指出,或者优化的地方,谢谢啦。(´▽`)

1. 冒泡排序

冒泡排序是实现起来最简单的排序算法,时间复杂度是O(n^2),它的代码核心是两层嵌套的for循环,循环里一个判断数组相邻两个元素大小,如果不满足就交换。
冒泡排序有一个小的优化的点:如果在外层循环的一趟里没有交换任何元素,就说明排序完成了,就不需要再继续排了。所以也设置了一个flag判断。
代码如下:

"""
bubble sorting
"""
 def bubble_sorting(array):
    for i in range(len(array)-1):
        flag = False
        for j in range(len(array)-i-1):
            if array[j]>array[j+1]:
                flag = True
                tmp = array[j]
                array[j] = array[j+1]
                array[j+1] = tmp
        if not flag:
            break
    return array
array = [0,1,0,7,9,8,5,4,2,0]
print(bubble_sorting(array))

运行结果就是[0, 0, 0, 1, 2, 4, 5, 7, 8, 9]

2. 选择排序

选择排序也是一种时间复杂度是O(n^2)的稳定排序算法,它的核心思想就是每次遍历数组选出最小的放在左边 ,这样右边无序区越来越小,左边有序区越来越大。也是两层循环嵌套。
代码如下:

def select_sorting(array):
    for i in range(len(array)):
        min = array[i]
        min_index = i
        for j in range(i,len(array)):
            if array[j]<min:
                min = array[j]
                min_index = j
        array[min_index] = array[i]
        array[i] = min
    return array
print(select_sorting(array))

运行结果 也是[0, 0, 0, 1, 2, 4, 5, 7, 8, 9]

3. 插入排序

插入排序跟上面两种排序算法比起来就算有点点绕了,它虽然也是需要两层循环,但是内层不再是遍历。插入排序要注意的是外层循环从第二个值开始,把第一个值当作是有序区。这样每一个新的值都会跟前面的有序区进行比较,如果小于前一个数就插到前面,一直到合适的位置为止。

def insert_sorting(array):
    for i in range(2,len(array)):
        j = i-1
        while j >= 0 and array[j]>array[j+1]:
            tmp = array[j+1]
            array[j+1] = array[j]
            array[j] = tmp
            j -= 1
    return array
print(insert_sorting(array))

我个人觉得写成i,j比较好理解,但是也可以就用i表示就成了(跟上面一回事):

def insert_sorting(array):
    for i in range(2,len(array)):
        while i>= 1 and array[i-1]>array[i]:
            tmp = array[i]
            array[i] = array[i-1]
            array[i-1] = tmp
            i -= 1
    return array
print(insert_sorting(array))

4. 快速排序

快速排序……卡了我很久很久,因为我一直在尝试用循环递推做,我……失败了。快排本身是一种很常用(超重要,面试也经常考的排序算法),它是一种“分治”的思想,就是要用递归的意思,接受了这一点再来写,就不会自己难为自己了。它始终选一个基准,一般是左边第一个,然后从右往左推,找到比他更小的就放左边空格,然后从左往右推,找到比他更大的就放在右边空格,我这里用的是挖坑填数法。直到左右相会,就把挖出来的基准放在相会的位置上。此时左边都比基准小,右边都比基准大。再对左右两个子列表分别用这个方法,直到整个列表都有序。
接下来献上我很丑的代码:

def quick_sorting(array,left,right):
   if left >= right:
       return
   pivot = array[left]
   low = left
   high = right
   while left <right:
       while left < right:
           if array[right]<pivot:
               break
           else:
               right -= 1
       array[left] = array[right]
       print('pivot:',pivot,array)
       while left < right:
           if array[left]>pivot:
               break
           else:
               left += 1
       array[right] = array[left]
       print('pivot:',pivot,array)
   array[left] = pivot
   quick_sorting(array,low,left-1) #调用自身-左子列
   quick_sorting(array,left+1,high) # 右子列
   return array

假如你并不需要保留重复的项,或者需要排序的列表没有重复项,那么可以用一个真正简单美丽的递归解决问题,其实这个就是刚才的算法的简化:

def quick_sort(array):
    if len(array)<2:
        return array
    pivot = array[0]
    left = [i for i in array if i < pivot]
    right = [i for i in array if i > pivot]
    return quick_sort(left)+[pivot]+quick_sort(right)
print(quick_sort(array))

以后有机会可能还会补上堆排序啦~就先写到这里,希望可以和大家多多交流!谢谢(鞠躬)

你或许想:《去原作者写文章的地方

「点点赞赏,手留余香」

    还没有人赞赏,快来当第一个赞赏的人吧!
Python
0 条回复 A 作者 M 管理员
    所有的伟大,都源于一个勇敢的开始!
欢迎您,新朋友,感谢参与互动!欢迎您 {{author}},您在本站有{{commentsCount}}条评论