什么是排序？

排序是指根据数据项之间的线性关系，以特定顺序（通常是升序或降序）排列数据的过程。

为什么我们需要排序？

处理结构化数据时排序至关重要，因为它可以实现高效的数据检索、简化数据分析并增强整体数据管理。

排序算法

这篇文章涵盖了以下排序算法：冒泡排序、选择排序、插入排序、合并排序和快速排序。

冒泡排序

冒泡排序重复遍历数组，比较相邻元素，如果顺序错误则交换它们。这个过程一直持续到数组被排序，较大的元素“冒泡”到末尾。

算法

第 1 步：开始
步骤 2：i = 0
步骤3：如果i 步骤 4：j = 0
步骤5：如果j 步骤6：如果array[j] > array[j 1]，则转至步骤7；否则转到步骤 8
步骤7：交换数组[j]和数组[j 1]
步骤8：递增j；转到步骤 5
步骤9：增加i；转到步骤 3
第10步：结束

代码

def bubble_sort(arr):
    print("Array Before Sorting: ", end='')
    print(arr)
    for i in range(len(arr)):
        for j in range(len(arr)-i-1):
            if arr[j] > arr[j 1]:
                arr[j], arr[j 1] = arr[j 1], arr[j]

    print("Array After Sorting: ", end='')
    print(arr)

# Main
bubble_sort([7, 4, 1, 3, 4, 7, 87, 9, 6, 4, 2, 2, 3, 5, 6])

时间复杂度

最佳情况：O(n)
平均情况：O(n^2)
最坏情况：O(n^2)

选择排序

选择排序查找数组未排序部分中的最小值，并将其放置在该部分的开头。

算法

第 1 步：开始
步骤 2：i = 0
步骤3：如果i 步骤4：minimum_value = i； j = i 1
步骤5：如果j 步骤6：如果array[minimum_value] > array[j]，则转至步骤7；否则转到步骤 8
步骤 7：最小值 = j
步骤8：递增j；转到步骤 5
步骤 9：交换 array[minimum_value] 和 array[i]
步骤10：增加i；转到步骤 3
第11步：结束

代码

def selection_sort(arr):
    print("Array Before Sorting: ", end='')
    print(arr)
    for i in range(len(arr) - 1):
        min_val = i
        for j in range(i   1, len(arr)):
            if arr[j] 




  
  
  时间复杂度


最佳情况：O(n^2)

平均情况：O(n^2)

最坏情况：O(n^2) 


  
  
  插入排序


插入排序通过从未排序部分取出每个元素并将其插入到已排序部分的正确位置来构建排序数组，一次一个元素。


  
  
  算法


第 1 步：开始

步骤 2：i = 1

步骤3：如果i 
第四步：key = arr[i]

步骤 5：j = i - 1

步骤6：如果j >= 0且arr[j] > key，则转至步骤7；否则转到步骤 10

步骤7：arr[j 1] = arr[j]

步骤 8：将 j 减 1

第 9 步：转到第 6 步

第10步：arr[j 1] = key

步骤11：i加1；转到步骤 3

第12步：结束


  
  
  代码




def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1

        while j >= 0 and arr[j] > key:
            arr[j   1] = arr[j]
            j -= 1

        arr[j   1] = key

# Main
arr = [7, 4, 1, 3, 4, 7, 87, 9, 6, 4, 2, 2, 3, 5, 6]
print("Array Before Sorting:", arr)
insertion_sort(arr)
print("Array After Sorting:", arr)





  
  
  时间复杂度


最佳情况：O(n)

平均情况：O(n^2)

最坏情况：O(n^2) 


  
  
  归并排序


合并排序是一种分而治之的算法，它递归地将数组划分为更小的子数组，对它们进行排序，然后将它们合并在一起。


  
  
  算法


归并排序算法


第 1 步：开始

步骤2：如果length(array) 
第三步：mid_point = length(array) // 2

步骤4：left_half =数组[:mid_point]

步骤5：right_half = array[mid_point:]

第6步：sorted_left = merge_sort(left_half)

步骤7：sorted_right = merge_sort(right_half)

步骤8：返回merge(sorted_left,sorted_right)

第9步：结束

合并函数


第 1 步：开始

步骤2：sorted_merge = []

步骤3：l = 0，r = 0

步骤4：若l 
步骤5：若left[l] 
第6步：将left[l]添加到sorted_merge中；将 l 加 1

步骤7：将right[r]添加到sorted_merge；将 r 加 1

第 8 步：转到第 4 步

步骤9：若l 
第10步：将left[l]添加到sorted_merge中；将 l 加 1 

第11步：转到第9步

步骤12：若r 
第13步：将right[r]添加到sorted_merge中；将 r 加 1

第14步：转到第12步

第15步：返回sorted_merge

第16步：结束


  
  
  代码




def merge(left, right):
    sorted_merge = []
    l = r = 0
    while l 




  
  
  时间复杂度


最佳情况：O(n log n)

平均情况：O(n log n)

最坏情况：O(n log n) 


  
  
  快速排序


快速排序是一种高效的就地排序算法，采用分而治之的方法。它选择一个枢轴元素并围绕该枢轴对数组进行分区，以便小于该枢轴的元素位于其左侧，大于该枢轴的元素位于其右侧。然后，此过程递归地应用于子数组。


  
  
  算法


快速排序


第 1 步：开始

步骤2：如果低
步骤3：pivot_index =partition(arr,low,high)

步骤 4：快速排序(arr, low, hub_index - 1)

步骤5：快速排序（arr，pivot_index 1，high）

第6步：结束

配分函数


第 1 步：开始

步骤2：pivot = arr[high]

步骤 3：左 = 低，右 = 高 - 1

步骤 4：如果 left 
步骤5：如果arr[left]>pivot且arr[right]
步骤 6：如果 arr[left] 
步骤 7：如果 arr[right] >= 枢轴，则递减 right

第 8 步：转到第 4 步

第9步：交换arr[left]和arr[high]

第10步：返回左

第11步：结束


  
  
  代码




def partition(arr, low, high):
    pivot = arr[high]
    left = low
    right = high - 1
    while left  pivot and arr[right] = pivot:
            right -= 1
    arr[left], arr[high] = arr[high], arr[left]
    return left

def quicksort(arr, low, high):
    if low 




  
  
  时间复杂度


最佳情况：O(n log n)

平均情况：O(n log n)

最坏情况：O(n^2)