Day 10 排序算法

「爱情、让人受尽委屈。」 2021-12-11 01:29 175阅读 0赞

## 冒泡排序 ##

![560577-20190614164940878-2064356320.gif][]

规则，两两比较，如果前面的比后面的大，则交换位置， 时间复杂度O(n \*\* 2) 。 数组 【6, 5, 3, 1, 8, 7, 2, 4】

第一次遍历，可以找到最大的数8，并交换到了最后第八位。

第二次遍历，排除最后的数8，可以找到第二大的数7，并交换到第七位。

。。。

第七次遍历，只剩下前两位数1和2，比较一下，并将2放置到第二位。

def bubble_sort(arr):
        n = len(arr)
    
        # 数组元素交换位置
        def swap(i, j):
            if arr[i] > arr[j]:
                arr[i], arr[j] = arr[j], arr[i]
    
        while (n > 1):
            print("需要排序的元素数量%d" % n)
            for x in range(0, n-1):
                swap(x, x + 1)
            print("排序后的数组 ", end='')
            print(arr)
            n = n - 1
        return arr
    
    
    arr = [6, 5, 3, 1, 8, 7, 2, 4]
    print("待排序的数组 ", end='')
    print(arr)
    bubble_sort(arr)
    
    待排序的数组 [6, 5, 3, 1, 8, 7, 2, 4]
    需要排序的元素数量8
    排序后的数组 [5, 3, 1, 6, 7, 2, 4, 8]
    需要排序的元素数量7
    排序后的数组 [3, 1, 5, 6, 2, 4, 7, 8]
    需要排序的元素数量6
    排序后的数组 [1, 3, 5, 2, 4, 6, 7, 8]
    需要排序的元素数量5
    排序后的数组 [1, 3, 2, 4, 5, 6, 7, 8]
    需要排序的元素数量4
    排序后的数组 [1, 2, 3, 4, 5, 6, 7, 8]
    需要排序的元素数量3
    排序后的数组 [1, 2, 3, 4, 5, 6, 7, 8]
    需要排序的元素数量2
    排序后的数组 [1, 2, 3, 4, 5, 6, 7, 8]

##  选择排序 ##

![560577-20190617092300362-2114908270.gif][]

规则， 每次循环找到最小的值，并将值交换到循环的首位置。时间复杂度 O(n \*\* 2) 。数组【5 2 4 6 1 3】

第一次循环，默认最小值是第1位的值5，遍历元素，遇到比5小的更换最小值索引，直到遍历结束找到最小值1，将最小值与第一位5交换。 【1 2 4 6 5 3】

第二次循环，默认最小值是第2位的值2，遍历元素，没有找到比2小的值，不用交换元素。【1 2 4 6 5 3】

第三次循环，默认最小值是第3位的值4，遍历元素，遇到比4小的更换最小值索引，直到遍历结束找到最小值3，将最小值与第三位4交换。 【1 2 3 6 5 4】

第四次循环，默认最小值是第4位的值6，遍历元素，遇到比6小的更换最小值索引，直到遍历结束找到最小值4，将最小值与第四位6交换。 【1 2 3 4 5 6】

第五次循环，默认最小值是第5位的值5，遍历元素，没有找到比5小的值，不用交换元素。【1 2 3 4 5 6】

def select_sort(arr):
        n = len(arr)
    
        for i in range(n-1):
            mininum = i
    
            for j in range(i+1, n):
                if arr[j] < arr[mininum] :
                    mininum = j
    
            arr[i], arr[mininum] = arr[mininum], arr[i]
            print("排序后的数组 ", end='')
            print(arr)
    
        return arr
    
    
    arr = [5, 2, 4, 6, 1, 3]
    print("待排序的数组 ", end='')
    print(arr)
    select_sort(arr)
    
    待排序的数组 [5, 2, 4, 6, 1, 3]
    排序后的数组 [1, 2, 4, 6, 5, 3]
    排序后的数组 [1, 2, 4, 6, 5, 3]
    排序后的数组 [1, 2, 3, 6, 5, 4]
    排序后的数组 [1, 2, 3, 4, 5, 6]
    排序后的数组 [1, 2, 3, 4, 5, 6]

## 插入排序 ##

![560577-20190617095730201-570499657.gif][]

规则， 每次循环当前元素之前的元素是已经排序好的，找到适合当前元素的位置插入。 数组【6 5 3 1 8 7 2 4】

第一次循环，从元素5开始，与前面的元素组【6】比较，找到新位置0，6后移一位，5插入到6原来的位置。 【5 6 3 1 8 7 2 4】

第二次循环，从元素3开始，与前面的元素组【5 6】比较，找到新位置0，5 6均后移一位。 【3 5 6 1 8 7 2 4】

.。。。。

def insert_sort(arr):
        n = len(arr)
    
        for i in range(1, n):
            current = arr[i]
    
            # 在已经排序的部分range(0, i) 找到 i 元素应该的位置
            cursor = 0
            for j in range(0, i+1):
                if current <= arr[j]:
                    cursor = j
                    break
    
            # 将元素i 插入到 range(0, i+1) 中
            start = i
            while start > cursor:
                arr[start] = arr[start-1]
                start = start -1
            arr[cursor] = current
    
            print("排序后的数组 ", end='')
            print(arr)
    
    
    arr = [6, 5, 3, 1, 8, 7, 2, 4]
    print("待排序的数组 ", end='')
    print(arr)
    insert_sort(arr)
    
    待排序的数组 [6, 5, 3, 1, 8, 7, 2, 4]
    排序后的数组 [5, 6, 3, 1, 8, 7, 2, 4]
    排序后的数组 [3, 5, 6, 1, 8, 7, 2, 4]
    排序后的数组 [1, 3, 5, 6, 8, 7, 2, 4]
    排序后的数组 [1, 3, 5, 6, 8, 7, 2, 4]
    排序后的数组 [1, 3, 5, 6, 7, 8, 2, 4]
    排序后的数组 [1, 2, 3, 5, 6, 7, 8, 4]
    排序后的数组 [1, 2, 3, 4, 5, 6, 7, 8]

## 快速排序 ##

![Image 1][]![560577-20190618132959632-160495862.jpg][]

规则， 每次循环 先选取基准数，遍历，将小于基准数的元素放入一个集合a, 大于基准数的元素放入另外一个集合b。再使用递归方式分别对集合,a ,b 进行排序，当a, b元素个数小于2时跳出递归，反向将集合a, b组合。

例如 \[6, 5, 3, 1, 8, 7, 2, 4\]

第一次循环，以6为基准数，将小于6的数放入集合的左侧， 大于6的数放入集合的右侧。\[5, 3, 1, 2, 4, 6, 8, 7\]。 再分别对6左侧的集合和右侧的的集合分别排序

第二次循环，对集合左侧的集合排序，以5为基准数，将小于5的数放入集合的左侧， 大于5的数放入集合的右侧。\[3, 1, 2, 4, 5\]。 再分别对5左侧的集合和右侧的的集合分别排序

....

def quick_sort(arr):
        if len(arr) < 2: # 数组元素个数小于2时，不需要再分子数组
            return arr
        else:
            pivot = arr[0] # 基准数
            smaller = []
            bigger = []
            print("待排序的数组 ", end='')
            print(arr)
            for x in range(1, len(arr)):
                if arr[x] <= pivot:
                    smaller.append(arr[x])
                else:
                    bigger.append(arr[x])
            print("排序后的数组 ", end='')
            print(smaller + [pivot] + bigger)
            return quick_sort(smaller) + [pivot] + quick_sort(bigger)
    
    
    arr = [6, 5, 3, 1, 8, 7, 2, 4]
    arr = quick_sort(arr)
    print("最后排序后的数组 ", end='')
    print(arr)
    
    待排序的数组 [6, 5, 3, 1, 8, 7, 2, 4]
    排序后的数组 [5, 3, 1, 2, 4, 6, 8, 7]
    待排序的数组 [5, 3, 1, 2, 4]
    排序后的数组 [3, 1, 2, 4, 5]
    待排序的数组 [3, 1, 2, 4]
    排序后的数组 [1, 2, 3, 4]
    待排序的数组 [1, 2]
    排序后的数组 [1, 2]
    待排序的数组 [8, 7]
    排序后的数组 [7, 8]
    最后排序后的数组 [1, 2, 3, 4, 5, 6, 7, 8]

转载于:https://www.cnblogs.com/greatX/p/11024456.html

[560577-20190614164940878-2064356320.gif]: /images/20211210/90a4f76c473741108724bf6f1a823110.png
[560577-20190617092300362-2114908270.gif]: /images/20211210/8cf88ae0279a43bbb2139a1f433dabb8.png
[560577-20190617095730201-570499657.gif]: /images/20211210/382e2b3f305447fca91fe5b3f246d6ff.png
[Image 1]: 
[560577-20190618132959632-160495862.jpg]: /images/20211210/768c97d348204919844df6128d9f44cd.png