python排序算法

排序,就是使一串记录,按照其中的某个或某些关键字的大小,递增或递减的排列起来的操作。排序算法,就是如何使得记录按照要求排列的方法。

排序算法主要有冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、基数排序、堆排序、计数排序、桶排序。

冒泡排序(Bubble Sort)也是一种简单直观的排序算法。

它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。

走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。

这个算法的名字由来是因为越小的元素会经由交换慢慢”浮”到数列的顶端。

选择排序(Selection sort)是一种简单直观的排序算法。

它的工作原理如下。首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,

然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。

以此类推,直到所有元素均排序完毕。

插入排序(英语:Insertion Sort)是一种简单直观的排序算法。

它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。

python排序算法
python排序算法

代码如下:

#!/usr/bin/env python
# -*- coding: UTF-8 -*-
#                     _ooOoo_
#                   o8888888o
#                    88" . "88
#                 ( | -  _  - | )
#                     O\ = /O
#                 ____/`---'\____
#                  .' \\| |// `.
#                 / \\|||:|||// \
#               / _|||||-:- |||||- \
#                | | \\\ - /// | |
#              | \_| ''\---/'' | _/ |
#               \ .-\__ `-` ___/-. /
#            ___`. .' /--.--\ `. . __
#         ."" '< `.___\_<|>_/___.' >'"".
#       | | : `- \`.;`\  _ /`;.`/ - ` : | |
#          \ \ `-. \_ __\ /__ _/ .-` / /
#      ==`-.____`-.___\_____/___.-`____.-'==
#                     `=---='
'''
@Project :pythonalgorithms 
@File :datasort.py
@Author :不胜人生一场醉
@Date :2021/7/18 14:22 
'''


# import matplotlib.pyplot as plt
# def swapAndDraw(tempbar,data,x1,x2):
#     temp1height=tempbar[x1].get_height()
#     tempbar[x1].set_height(tempbar[x2].get_height())
#     tempbar[x2].set_height(temp1height)
#     tempbar[x2].set_fc("red")
#     plt.draw()
#     plt.pause(0.001)
#     tempbar[x2].set_fc("green")#记得颜色换回来

def bubblesort(list):
    length = len(list)
    k = 0
    print('----------------------bubble sort  ----------------------')
    print("orginal list=", list)
    for i in range(length):
        for j in range(1, length):
            if list[j - 1] > list[j]:
                k += 1
                list[j - 1], list[j] = list[j], list[j - 1]
                print("step {}".format(k), list)
    print("sorded list=", list)
    return list


def bubblesort1(list):
    length = len(list)
    k = 0
    print('----------------------bubble1 sort  ----------------------')
    print("orginal list=", list)
    for i in range(length):
        for j in range(1, length - i):
            if list[j - 1] > list[j]:
                k += 1
                list[j - 1], list[j] = list[j], list[j - 1]
                print("step {}".format(k), list)
    print("sorded list=", list)
    return list


def bubblesort2(list):
    length = len(list)
    k = 0
    print('----------------------bubble2 sort ----------------------')
    print("orginal list=", list)
    for i in range(length):
        flag = True
        for j in range(1, length - i):
            if list[j - 1] > list[j]:
                k += 1
                list[j - 1], list[j] = list[j], list[j - 1]
                flag = False
                print("step {}".format(k), list)
        if flag == True:
            return list
    print("sorded list=", list)
    return list


def selectionsort(list):
    length = len(list)
    k = 0
    print('----------------------selection sort ----------------------')
    print("orginal list=", list)
    for i in range(length):
        min = i
        for j in range(i + 1, len(list)):
            if list[min] > list[j]:
                min = j
        if i != min:
            k += 1
            list[i], list[min] = list[min], list[i]
            print("step {}".format(k), list)
    print("sorded list=", list)
    return list


def insertsort(list):
    length = len(list)
    k = 0
    print('----------------------insert sort ----------------------')
    print("orginal list=", list)
    for i in range(1, length):
        key = list[i]
        j = i - 1
        while j >= 0 and key < list[j]:
            list[j + 1] = list[j]
            j -= 1

        k += 1
        list[j + 1] = key
        print("step {}".format(k), list)
    print("sorded list=", list)
    return list


if __name__ == "__main__":
    array1 = [3, 2, 5, 1, 4]
    array2 = [3, 2, 5, 1]
    bubblesort(array1)
    bubblesort(array2)
    array1 = [3, 2, 5, 1, 4]
    array2 = [3, 2, 5, 1]
    bubblesort1(array1)
    bubblesort1(array2)
    array1 = [3, 2, 5, 1, 4]
    array2 = [3, 2, 5, 1]
    bubblesort2(array1)
    bubblesort2(array2)
    array1 = [3, 2, 5, 1, 4]
    array2 = [3, 2, 5, 1]
    selectionsort(array1)
    selectionsort(array2)
    array1 = [3, 2, 5, 1, 4]
    array2 = [3, 2, 5, 1]
    insertsort(array1)
    insertsort(array2)

结果如下:

C:\python\pyproject\pythonalgorithms\venv\Scripts\python.exe C:/python/pyproject/pythonalgorithms/datasort.py
----------------------bubble sort  ----------------------
orginal list= [3, 2, 5, 1, 4]
step 1 [2, 3, 5, 1, 4]
step 2 [2, 3, 1, 5, 4]
step 3 [2, 3, 1, 4, 5]
step 4 [2, 1, 3, 4, 5]
step 5 [1, 2, 3, 4, 5]
sorded list= [1, 2, 3, 4, 5]
----------------------bubble sort  ----------------------
orginal list= [3, 2, 5, 1]
step 1 [2, 3, 5, 1]
step 2 [2, 3, 1, 5]
step 3 [2, 1, 3, 5]
step 4 [1, 2, 3, 5]
sorded list= [1, 2, 3, 5]
----------------------bubble1 sort  ----------------------
orginal list= [3, 2, 5, 1, 4]
step 1 [2, 3, 5, 1, 4]
step 2 [2, 3, 1, 5, 4]
step 3 [2, 3, 1, 4, 5]
step 4 [2, 1, 3, 4, 5]
step 5 [1, 2, 3, 4, 5]
sorded list= [1, 2, 3, 4, 5]
----------------------bubble1 sort  ----------------------
orginal list= [3, 2, 5, 1]
step 1 [2, 3, 5, 1]
step 2 [2, 3, 1, 5]
step 3 [2, 1, 3, 5]
step 4 [1, 2, 3, 5]
sorded list= [1, 2, 3, 5]
----------------------bubble2 sort ----------------------
orginal list= [3, 2, 5, 1, 4]
step 1 [2, 3, 5, 1, 4]
step 2 [2, 3, 1, 5, 4]
step 3 [2, 3, 1, 4, 5]
step 4 [2, 1, 3, 4, 5]
step 5 [1, 2, 3, 4, 5]
----------------------bubble2 sort ----------------------
orginal list= [3, 2, 5, 1]
step 1 [2, 3, 5, 1]
step 2 [2, 3, 1, 5]
step 3 [2, 1, 3, 5]
step 4 [1, 2, 3, 5]
----------------------selection sort ----------------------
orginal list= [3, 2, 5, 1, 4]
step 1 [1, 2, 5, 3, 4]
step 2 [1, 2, 3, 5, 4]
step 3 [1, 2, 3, 4, 5]
sorded list= [1, 2, 3, 4, 5]
----------------------selection sort ----------------------
orginal list= [3, 2, 5, 1]
step 1 [1, 2, 5, 3]
step 2 [1, 2, 3, 5]
sorded list= [1, 2, 3, 5]
----------------------insert sort ----------------------
orginal list= [3, 2, 5, 1, 4]
step 1 [2, 3, 5, 1, 4]
step 2 [2, 3, 5, 1, 4]
step 3 [1, 2, 3, 5, 4]
step 4 [1, 2, 3, 4, 5]
sorded list= [1, 2, 3, 4, 5]
----------------------insert sort ----------------------
orginal list= [3, 2, 5, 1]
step 1 [2, 3, 5, 1]
step 2 [2, 3, 5, 1]
step 3 [1, 2, 3, 5]
sorded list= [1, 2, 3, 5]

Process finished with exit code 0

发表评论

登录后才能评论
服务中心
联系客服