排序

1. 冒泡排序(Bubble Sort)

基本原理
冒泡排序是一种简单的排序算法,它重复地遍历待排序的数列,一次比较两个元素,如果它们的顺序错误就把它们交换过来。遍历数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。

应用场景
适用于数据量较小且基本有序的数列排序。

优点

  • 实现简单。
  • 对基本有序的数列排序效率较高。

缺点

  • 时间复杂度较高,最坏情况下是O(n^2)。
  • 对于大数据集效率低下。

Python实现

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr

# 示例
arr = [64, 34, 25, 12, 22, 11, 90]
print("原始数组:", arr)
bubble_sort(arr)
print("排序后数组:", arr)

2. 选择排序(Selection Sort)

基本原理
选择排序是一种简单直观的排序算法。它的工作原理是,首先在未排序序列中找到最小(或最大)元素,存放到排序序列的起始位置,然后再从剩余未排序元素中继续寻找最小(或最大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。

应用场景
适用于数据量较小的情况,或用于解决特定问题,如查找第k小的元素。

优点

  • 实现简单。
  • 交换次数少,数据移动少。

缺点

  • 时间复杂度较高,为O(n^2)。
  • 对于大数据集排序效率低下。

Python实现

def selection_sort(arr):
    for i in range(len(arr)):
        min_index = i
        for j in range(i+1, len(arr)):
            if arr[j] < arr[min_index]:
                min_index = j
        arr[i], arr[min_index] = arr[min_index], arr[i]
    return arr

# 示例
arr = [64, 34, 25, 12, 22, 11, 90]
print("原始数组:", arr)
selection_sort(arr)
print("排序后数组:", arr)

3. 插入排序(Insertion Sort)

基本原理
插入排序的工作方式是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,通常采用in-place排序(即只需用到O(1)的额外空间的排序),因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。

应用场景
适用于数据量较小,且数据基本有序的情况。也常用于将数据插入到已排序的数组中。

优点

  • 实现简单。
  • 对基本有序的数据排序效率高。
  • 稳定排序。

缺点

  • 对于大数据集或无序数据集效率较低,时间复杂度最坏为O(n^2)。
  • 需要移动大量元素。

Python实现

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

# 示例
arr = [64, 34, 25, 12, 22, 11, 90]
print("原始数组:", arr)
insertion_sort(arr)
print("排序后数组:", arr)

4. 归并排序(Merge Sort)

基本原理
归并排序是一种分治策略的排序算法。它将一个大数组分割成两个小数组,分别对这两个小数组进行排序,然后将这两个已排序的小数组合并成一个大的有序数组。

应用场景
归并排序适用于对大量数据进行排序,尤其是外部排序(即数据太大,无法全部加载到内存中)。在数据库管理系统和文件系统中常用。

优点

  • 稳定排序算法。
  • 时间复杂度为O(n log n),效率较高。

缺点

  • 需要额外的空间来存储中间结果。

Python实现

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

def merge(left, right):
    merged = []
    left_index, right_index = 0, 0
    while left_index < len(left) and right_index < len(right):
        if left[left_index] <= right[right_index]:
            merged.append(left[left_index])
            left_index += 1
        else:
            merged.append(right[right_index])
            right_index += 1
    merged.extend(left[left_index:])
    merged.extend(right[right_index:])
    return merged



# 示例
arr = [64, 34, 25, 12, 22, 11, 90]
print("原始数组:", arr)
r = merge_sort(arr)
print("排序后数组:", r)

5. 快速排序(Quick Sort)

基本原理
快速排序也是一种分治策略的排序算法。它通过选取一个“基准值”(pivot),将数组分为两个子数组,一个包含比基准值小的元素,另一个包含比基准值大的元素,然后递归地对这两个子数组进行快速排序。

应用场景
快速排序在内存中对大数据集进行排序时非常高效,是许多编程语言和库中的默认排序算法。

优点

  • 平均时间复杂度为O(n log n),且常数因子较小。
  • 内部循环可以在大多数实际系统上高效实现。

缺点

  • 在最坏情况下,时间复杂度会退化为O(n^2)。
  • 不是稳定排序算法。

Python实现

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)

# 示例
arr = [5, 3, 7, 6, 2, 9, 1, 4, 8]
sorted_arr = quick_sort(arr)
print(sorted_arr)

6. 堆排序(Heap Sort)

基本原理
堆排序利用二叉堆(通常是大根堆)的性质来进行排序。首先构建一个最大堆,然后将堆顶元素(最大值)与最后一个元素交换,之后重新调整堆结构,使其仍然保持最大堆的性质。重复此过程,直到堆的大小变为1。

应用场景
堆排序适用于需要快速找到一系列数中的最大(或最小)值,并对其进行排序的场景。它也被用于实现优先级队列。

优点

  • 时间复杂度为O(n log n),且最坏情况与平均情况相同。
  • 可以在不完全有序的数据集上高效工作。

缺点

  • 不是稳定排序算法。
  • 由于元素交换的不确定性,缓存不命中的可能性较高。

Python实现

def heapify(arr, n, i):
    largest = i
    l = 2 * i + 1
    r = 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 heap_sort(arr):
    n = len(arr)
    for i in range(n, -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)
    return arr

# 示例
arr = [5, 3, 7, 6, 2, 9, 1, 4, 8]
sorted_arr = heap_sort(arr)
print(sorted_arr)

7. 希尔排序(Shell Sort)

基本原理
希尔排序是插入排序的一种优化版本。它首先将待排序的数组元素按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减少到1时,整个数组被分为一组,算法便终止。

应用场景
适用于中等大小的数据集排序,特别是当数据部分有序时表现较好。

优点

  • 相对于直接插入排序,希尔排序通过分组减少了比较和移动的次数,提高了效率。

缺点

  • 算法性能受增量序列的选择影响较大。
  • 不是稳定排序算法,即可能改变相等元素的相对顺序。

Python实现

def shell_sort(arr):
    n = len(arr)
    gap = n // 2
    while gap > 0:
        for i in range(gap, n):
            temp = arr[i]
            j = i
            while j >= gap and arr[j - gap] > temp:
                arr[j] = arr[j - gap]
                j -= gap
            arr[j] = temp
        gap //= 2
    return arr

# 示例
arr = [9, 8, 3, 7, 5, 6, 4, 1]
print(shell_sort(arr))  # 输出: [1, 3, 4, 5, 6, 7, 8, 9]

8. 计数排序(Counting Sort)

基本原理
计数排序是一种非比较的排序算法,适用于一个特定范围内的整数排序。它使用一个额外的数组来统计每个整数出现的次数,然后根据计数的结果将输入的数组排序。

应用场景
适用于一定范围内的整数排序,特别是当数据范围较小且数据量大时效率很高。

优点

  • 时间复杂度为O(n+k),其中k是整数的范围,当k不是很大时,算法效率很高。
  • 是一种稳定排序算法。

缺点

  • 当整数的范围k很大时,需要较大的额外空间,造成空间浪费。
  • 只能用于整数排序。

Python实现

def counting_sort(arr):
    max_val = max(arr)
    count = [0] * (max_val + 1)
    for num in arr:
        count[num] += 1
    output = []
    for i in range(len(count)):
        output.extend([i] * count[i])
    return output

# 示例
arr = [4, 2, 2, 8, 3, 3, 1]
print(counting_sort(arr))  # 输出: [1, 2, 2, 3, 3, 4, 8]

9. 桶排序(Bucket Sort)

基本原理
桶排序是将数组分到有限数量的桶中,每个桶再分别排序(通常使用其他排序算法或是以递归方式继续使用桶排序进行排序)。最后,将各个桶中的数据合并起来。

应用场景
适用于数据均匀分布在一个范围较大的区间内,且数据量较大的情况。

优点

  • 当数据量很大且分布均匀时,桶排序的效率很高,时间复杂度可以接近O(n)。
  • 可以并行处理多个桶,进一步提高效率。

缺点

  • 当数据分布不均匀时,可能会导致某些桶的数据过多,从而降低效率。
  • 需要额外的空间来存储桶。
  • 不是稳定排序算法。

Python实现

def bucket_sort(arr):
    max_val = max(arr)
    bucket_range = 10  # 假设每个桶的范围是10,这个值可以根据实际情况调整
    num_buckets = (max_val // bucket_range) + 1
    buckets = [[] for _ in range(num_buckets)]
    for num in arr:
        index = num // bucket_range
        buckets[index].append(num)
    sorted_arr = []
    for bucket in buckets:
        # 这里为了简单起见,使用了内置的sorted函数,实际应用中可以替换为其他排序算法
        sorted_arr.extend(sorted(bucket))
    return sorted_arr

# 示例
arr = [9, 2, 0, 17, 4, 31, 13, 8, 6]
print(bucket_sort(arr))  # 输出一个排序后的数组

10.基数排序(Radix Sort)

基本原理
基数排序是一种非比较型整数排序算法,它的原理是将整数按位数切割成不同的数字,然后按每个位数进行排序。通常,基数排序会从最低位开始,对每一位进行排序,然后再按更高位排序,直到最高位。对于每一位,可以使用稳定的排序算法(如计数排序或桶排序)来确保相同位数的数字按原始顺序排列,从而保证整体排序的稳定性。

应用场景
基数排序特别适用于对大量整数进行排序,尤其是当这些整数的位数相对固定且不太长时。例如,在处理大量的手机号、身份证号或其他具有固定格式的数字序列时,基数排序能表现出很高的效率。

优点

  • 稳定性好:基数排序是稳定的排序算法,即相同值的元素在排序后保持其原有的顺序。
  • 效率较高:对于大量整数排序,尤其是位数不多的情况,基数排序的性能通常优于比较型排序算法。

缺点

  • 局限性大:基数排序主要用于整数排序,对于非整数类型的数据,如字符串或对象,需要额外的转换步骤。
  • 空间消耗:基数排序需要额外的空间来存储临时排序结果,这可能会增加内存消耗。

Python实现

def radix_sort(arr):
    # 找到最大数的位数
    max_val = max(arr)
    max_digit = len(str(max_val))
    
    # 从最低位到最高位依次排序
    for k in range(max_digit):
        # 使用计数排序作为子排序算法
        bucket = [[] for _ in range(10)]
        for i in arr:
            # 获取当前位的数字
            digit = (i // (10**k)) % 10
            bucket[digit].append(i)
        
        # 重新组合数组
        arr = [j for i in bucket for j in i]
    
    return arr

# 示例
arr = [121, 432, 564, 23, 1, 45, 788]
print("原始数组:", arr)
sorted_arr = radix_sort(arr)
print("排序后数组:", sorted_arr)

在这个Python示例中,我们实现了基数排序算法,使用了计数排序作为子排序过程。算法首先确定最大数的位数,然后从最低位开始,对每一位进行排序。这个过程会重复进行,直到处理完最高位。注意,这里的实现是基于整数的排序,并且假设了所有数都是非负的。如果需要处理负数或浮点数,算法将需要额外的处理步骤。

注意:在实际应用中,为了提高效率,通常会对这些基本算法进行一些优化和改进。上面的Python实现主要是为了展示算法的基本原理,可能不是最优的实现方式。

点赞(0) 打赏

评论列表 共有 0 条评论

暂无评论

微信公众账号

微信扫一扫加关注

发表
评论
返回
顶部