牛客网---排序算法（python实现）

绝地灬酷狼 2022-10-23 14:24 215阅读 0赞

### 冲 ###

*   *   *  1： 冒泡排序：
         *  2：选择排序：
         *  3：插入排序：
         *  4：希尔排序：
         *  5：快速排序：
         *  6：归并排序：
         *  7：堆排序：

### 1： 冒泡排序： ###

> 思想+ 时间复杂度：相邻两个进行排序，如果第一个比第二个大就交换。时间复杂度时O(N2)。
> 
> 实现：外层要排序n-1次（range(n-1)），内层要让j+1, 到达n-1，则需要range(n-i-1)

def demo_sort(alist):
        n = len(alist)
    
        # 一共需要排序n-1次
        for i in range(n-1):
            # 当i等于0时，j+1,必须到达n-1
            for j in range(n-1-i):
                if alist[j] > alist[j+1]:
                    alist[j], alist[j+1] = alist[j+1], alist[j]
    
        return alist
    
    if __name__ == '__main__':
        alist = [3, 5, 2, 7, 4, 7, 9]
        alist = demo_sort(alist)
        print(alist)

### 2：选择排序： ###

> 思想+时间复杂度：每次选择最大的/最小的，依次放在前面。时间复杂度(O(N2))
> 
> 实现：外层需要遍历n-1次，最后一个自动有序。先记录假设当前位置最小，然后从下一个位置开始遍历，如果有比当前位置更小的记录下边，以后更新最小的下标，最后获得最小的下标，进行交换。

def select_sort(alist):
        n = len(alist)
        # 外层需要n-1次，最后一个自动有序
        for i in range(n-1):
            # 假定当前位置数最小
            min_index = i
            # 从当前位置下一位到最后，寻找最小数的下标
            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]
        return alist
    
    if __name__ == '__main__':
        alist = [2, 5, 8, 9, 1, 4, 6, 7]
        alist = select_sort(alist)
        print(alist)

### 3：插入排序： ###

> 思想+时间复杂度：将一个列表逻辑上分成两部分，前面有序，后面无序，每次在无序列表中取出一个元素，插入到有序列表的合适的位置。 时间复杂度是O(N2)
> 
> 实现：外层是从1号位置开始到n-1号位置结束（range(1, n)）,内层是从有序列表最后向前依次遍历，如果当前位置小于有序位置，则交换，依次交换，到达自己的位置。

def demo_sort(alist):
        n = len(alist)
        for i in range(1, n):
            for j in range(i, 0, -1):
                if alist[j] < alist[j-1]:
                    alist[j-1], alist[j] = alist[j], alist[j-1]
        return alist
    
    if __name__ == '__main__':
        alist = [3, 5, 8, 2, 1, 9, 2, 0]
        alist = demo_sort(alist)
        print(alist)

### 4：希尔排序： ###

> 思想+时间复杂度：先根据gap进行分组，然后组内进行插入排序，最后缩小增量。时间复杂度
> 
> O(N2)
> 
> 实现：

def shell_sorrt(alist):
        n =len(alist)
        gap = n //2
        while gap >=1:
            # 从gap到n-1的所有元素都需要排序
            for i in range(gap, n):
                while i - gap >= 0:
                    # 如果后面的元素小于前面的元素就交换
                    if alist[i] < alist[i-gap]:
                        alist[i], alist[i-gap] = alist[i-gap], alist[i]
                        # 游标跟踪
                        i = i - gap
                    else:
                        break
            # 缩小增量
            gap //= 2
    
    if __name__ == '__main__':
        li = [54, 26, 93, 17, 77, 31, 44, 55, 20]
        shell_sorrt(li)

### 5：快速排序： ###

> 思想+时间复杂度：以基准值为分界，左面都是比他大的，右面都是比他小的。递归实现。
> 
> 时间复杂度： O(Nlog(N))
> 
> 实现方式：一个递归 + 一个两层while循环构成。
> 
> 一递归：递归终点，左递归和右递归。
> 
> 两层while循环：第一层保证两个指针没有相撞。第二层有两个while循环，先高位后低位，如果高位大于基准值，指针左移，循环结束后，将高位值赋给低位。

def quit_sort(alist, start, end):
        if start >= end:
            return
        # 记录基准值
        mid = alist[start]
        low = start
        hight = end
        # 两个指针没有相撞
        while low < hight:
            #只要高位值大于基准值，就向左移，然后将地位值，移动到左面
            while alist[hight] > mid and low < hight:
                hight -= 1
            alist[low] = alist[hight]
    
            while alist[low] <= mid and low < hight:
                low += 1
            alist[hight] = alist[low]
    
        # 将基准值，赋予中间值。
        alist[hight] = mid
        # 递归：
        quit_sort(alist, start, low-1)
        quit_sort(alist, low+1, end)
    
    if __name__ == '__main__':
        alist = [1, 4, 5, 2, 3, 7, 8]
        quit_sort(alist, 0, len(alist)-1)
        print(alist)

### 6：归并排序： ###

> 思想+ 时间复杂度：分治思想，向将元素拆分成单个的，然后在合并的过程中排好序。
> 
> 时间复杂度是O(N\*log(N))
> 
> 思想：
> 
> 递归拆分：递归终点是长度是1，然后左边递归，右边递归。
> 
> 递归合并：两个指针分别指向两个数组的起始位置，初始化一个新数组，循环遍历两个数组，如果谁的值小谁加入新数组。循环结束后，将剩余的合并到新数组中。

def merge_sort(alist):
        n = len(alist)
        # 拆分成单个元素作为递归出口
        if n == 1:
            return alist
        mid = n//2
    
        # 1：递归拆分
        # 左边递归拆分，不包含mid
        left_sorted_list = merge_sort(alist[:mid])
        # 2：右边递归拆分，包括mid位置
        right_sorted_list = merge_sort(alist[mid:])
    
        # 2：合并
        left, right  = 0, 0
        merge_sorted_list = []
        left_n = len(left_sorted_list)
        right_n = len(right_sorted_list)
    
        while left < left_n and right < right_n:
            if left_sorted_list[left] <= right_sorted_list[right]:
                merge_sorted_list.append(left_sorted_list[left])
                left += 1
            else:
                merge_sorted_list.append(right_sorted_list[right])
                right += 1
        merge_sorted_list += left_sorted_list[left:]
        merge_sorted_list += right_sorted_list[right:]
    
        return merge_sorted_list
    
    if __name__ == '__main__':
        alist = [3, 4, 5, 2, 6, 1, 9]
        alist = merge_sort(alist)
        print(alist)

### 7：堆排序： ###

*  时间复杂度是O(Nlog(N))
 *  生大降小（升序采用大根堆，降序采用小跟堆）
 *  https://www.cnblogs.com/chengxiao/p/6129630.html
 *  堆排序思想：
    
    **a.将无需序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆;**
    
    **b.将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端;**
    
    **c.重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。**

# 构建大根堆：
    def heapify(arr, n, i):
        largest = i
        l = 2 * i + 1  # left = 2*i + 1
        r = 2 * i + 2  # right = 2*i + 2
    
        if l < n and arr[i] < arr[l]: # 根节点小于左节点
            largest = l # 左节点是最大结点
    
        if r < n and arr[largest] < arr[r]: # 右节点大于最大结点，则右节点是最大结点
            largest = r
    
        if largest != i: # 如果最大结点不是根节点
            arr[i], arr[largest] = arr[largest], arr[i]  # 交换根节点和最大结点
            heapify(arr, n, largest) # 调换完了，我看看换完了之后是不是还是大根堆。
    
    
    def heapSort(arr):
        n = len(arr) # 堆长度
        for i in range(n - 1, -1, -1): # 从后向前递归创建大根堆
            heapify(arr, n, i)
        for i in range(n - 1, 0, -1):
            arr[i], arr[0] = arr[0], arr[i]  # 交换
            heapify(arr, i, 0) # 调整大根堆
    
    
    arr = [5, 5, 6, 2, 1, 4 ,7, 9, 0]
    heapSort(arr)
    print(arr)