Python-数据结构-最全六种排序代码实现

1.冒泡排序

def bubble_sort(alist):

    """冒泡排序"""

    n = len(alist)

    for j in range(n - 1):

        """j=0,1,2,n-2"""

        count = 0

        """内层循环控制从头到尾的遍历"""

        for i in range(0, n - 1 - j):

            if alist[i] > alist[i + 1]:

                alist[i], alist[i + 1] = alist[i + 1], alist[i]

                count += 1

        if 0 == count:

            break

1.1冒泡排序的测试

if __name__ == '__main__':

    li = [54, 26, 77, 17, 77, 31, 44, 55, 20]

    print(li)

    bubble_sort(li)

    print(li)

2.选择排序

def selection_sort(alist):

    n = len(alist)

    """    需要进⾏n-1次选择操作"""

    for i in range(n - 1):

        """记录最⼩位置"""

        min_index = i

        """从i+1位置到末尾选择出最⼩数据"""

        for j in range(i + 1, n):

            if alist[j] < alist[min_index]:

                min_index = j

                # 如果选择出的数据不在正确位置，进⾏交换

        if min_index != i:

            alist[i], alist[min_index] = alist[min_index], alist[i]

2.2选择排序的测试

alist = [54, 226, 93, 17, 77, 31, 44, 55, 20]

selection_sort(alist)

print(alist)

3.插入排序

def insert_sort(alist):

    n = len(alist)

    for j in range(1, n):

        for i in range(j, 0, -1):

            if alist[i] < alist[i - 1]:

                alist[i], alist[i - 1] = alist[i - 1], alist[i]

            else:

                break

        print(alist)

3.3插入排序的测试

if __name__ == '__main__':

    li = [54, 26, 93, 17, 77, 31, 44, 55, 20]

    print(li)

    insert_sort(li)

4.快速排序

def quick_sort(alist, start, end):

    if start >= end:

        return

    mid = alist[start]

    left = start

    right = end

    """left与right未重合，就向中间移动"""

    while left < right:

        while left < right and alist[right] >= mid:

            right -= 1

        alist[left] = alist[right]

        while left < right and alist[left] <= mid:

            left += 1

        alist[right] = alist[left]

    """循环退出来后，left与right相遇，即left=right"""

    alist[left] = mid

    print(alist)

    quick_sort(alist, start, left - 1)

    quick_sort(alist, left + 1, end)

4.4快速排序测试

if __name__ == '__main__':

    li = [54, 26, 93, 1, 7, 31, 44, 55, 20]

    quick_sort(li, 0, len(li) - 1)

    # print(li)

5.希尔排序

def shell_sort(alist):

    n = len(alist)

    gap = n // 2  # 4

    while gap >= 1:

        "j是从间隔gap到序列末尾的值"

        for j in range(gap, n):  # j=4 ，5，6，7，8

            i = j  # i=4 ，5，6，7，8

            while (i - gap) >= 0:  # i-gap=4-4,5-4,6-4,7-4,8-4

                if alist[i] < alist[i - gap]:  # 下标为i的和下标为i-gap的比较(alist[4]<alist[0])

                    alist[i], alist[i - gap] = alist[i - gap], alist[i]  # 如果小于交换位置

                else:

                    break  # 如果大于，不交换位置

        gap = gap // 2  # 减小间隔

5.5希尔排序测试

if __name__ == '__main__':

    li = [54, 26, 93, 17, 77, 31, 44, 55, 20]

    print(li)

    shell_sort(li)

    print(li)

6.归并排序

def merge_sort(alist):

    """归并排序"""

    n = len(alist)

    if 1 == n:

        return alist

    mid = n // 2

    """对左半部分进行归并排序"""

    left_sorted_li = merge_sort(alist[:mid])

    """对右半部分进行归并排序"""

    right_sorted_li = merge_sort(alist[mid:])

    """合并两个有序集合"""

    left, right = 0, 0  # 设定两个游标，让其初始值为0

    merge_sortted_li = []  # 设定一个空列边用于添加合并元素

    left_n = len(left_sorted_li)

    right_n = len(right_sorted_li)

    while left < left_n and right < right_n:

        if left_sorted_li[left] <= right_sorted_li[right]:

            merge_sortted_li.append(left_sorted_li[left])

            left += 1

        else:

            merge_sortted_li.append(right_sorted_li[right])

            right += 1

    merge_sortted_li += left_sorted_li[left:]

    merge_sortted_li += right_sorted_li[right:]

    return merge_sortted_li

6.6归并排序测试

if __name__ == '__main__':

    alist = [54, 26, 93, 17, 77, 31, 44, 55, 20]

    print("before sort: %s" % alist)

    sorted_alist = merge_sort(alist)

    print("after sort: %s" % alist)

    print("sorted new list: %s" % sorted_alist)

巴特西

Python-数据结构-最全六种排序代码实现

最新文章

热门文章