Engee 文档
Notebook

Engee中的排序算法：从理论到实践

排序是计算机科学的基本操作之一，具有许多实际应用。 在这篇文章中，我们将看到基本的排序算法，它们在Engee语言中的实现，并分析它们的时间复杂度和操作特性。
排序算法可以分为几类:

-比较排序（基于元素的两两比较）
-无与伦比的排序（使用特殊的数据属性）
-递归排序（使用"分而治之"的原则）
-迭代排序（按顺序遍历数据）

1. 泡沫排序

逻辑:

-成对比较相邻元素
-如果订单错误，请交换它们。
-该过程重复，直到数组被排序。

复杂性：O（n2）在最坏的情况下，O（n）在最好的（已经排序的数组）

In [ ]: 
function bubble_sort!(arr)
    n = length(arr)
    for i in 1:n-1
        swapped = false
        for j in 1:n-i
            if arr[j] > arr[j+1]
                arr[j], arr[j+1] = arr[j+1], arr[j]
                swapped = true
            end
        end
        !swapped && break  # 如果没有交易所，请退出
    end
    return arr
end

# 使用示例
arr = [64, 34, 25, 12, 22, 11, 90]
println("分类前: ", arr)
println("气泡排序后: ", bubble_sort!(copy(arr)))

До сортировки: [64, 34, 25, 12, 22, 11, 90]
После сортировки пузырьком: [11, 12, 22, 25, 34, 64, 90]

2. 插入排序

逻辑:

-数组有条件地分为排序部分和未排序部分
-每个新元素都插入到排序部分中的正确位置

难度：O（n2）在最坏的情况下，o（n）充其量

In [ ]: 
function insertion_sort!(arr)
    for i in 2:length(arr)
        key = arr[i]
        j = i - 1
        while j >= 1 && arr[j] > key
            arr[j+1] = arr[j]
            j -= 1
        end
        arr[j+1] = key
    end
    return arr
end

# 使用示例
println("按插入排序后: ", insertion_sort!(copy(arr)))

После сортировки вставками: [11, 12, 22, 25, 34, 64, 90]

3. 选择排序

逻辑:

-数组分为排序部分和未排序部分
-在每个步骤中，未排序部分中有一个最小元素。
-此元素被添加到排序部分的末尾。

难度：O（n2）无论如何

In [ ]: 
function selection_sort!(arr)
    n = length(arr)
    for i in 1:n-1
        min_idx = i
        for j in i+1:n
            if arr[j] < arr[min_idx]
                min_idx = j
            end
        end
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    end
    return arr
end

# 使用示例
println("按选择排序后: ", selection_sort!(copy(arr)))

После сортировки выбором: [11, 12, 22, 25, 34, 64, 90]

4. 快速排序

逻辑（递归）:

  1. 枢轴被选择
  2. 数组分为两部分：小于枢轴的元素和大于枢轴的元素
  3. 递归地应用于两个部分

难度：o（n log n）平均，O（n2）在最坏的情况下

In [ ]: 
function quick_sort!(arr, low=1, high=length(arr))
    if low < high
        pi = partition!(arr, low, high)  # 分区索引
        quick_sort!(arr, low, pi-1)
        quick_sort!(arr, pi+1, high)
    end
    return arr
end

function partition!(arr, low, high)
    pivot = arr[high]  # 支撑元件
    i = low - 1        # 较小元素的索引
    
    for j in low:high-1
        if arr[j] < pivot
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
        end
    end
    arr[i+1], arr[high] = arr[high], arr[i+1]
    return i + 1
end

# 使用示例
println("快速排序后: ", quick_sort!(copy(arr)))

После быстрой сортировки: [11, 12, 22, 25, 34, 64, 90]

5. 合并排序

逻辑（递归）:

  1. 阵列被分成两个近似相等的部分
  2. 每个部分都是递归排序的
  3. 排序后的部分合并为一个数组。

难度：O（n log n）在任何情况下

In [ ]: 
function merge_sort!(arr)
    if length(arr) > 1
        mid = length(arr) ÷ 2
        left = arr[1:mid]
        right = arr[mid+1:end]
        
        merge_sort!(left)
        merge_sort!(right)
        
        i = j = k = 1
        while i <= length(left) && j <= length(right)
            if left[i] < right[j]
                arr[k] = left[i]
                i += 1
            else
                arr[k] = right[j]
                j += 1
            end
            k += 1
        end
        
        # 添加其余元素
        while i <= length(left)
            arr[k] = left[i]
            i += 1
            k += 1
        end
        
        while j <= length(right)
            arr[k] = right[j]
            j += 1
            k += 1
        end
    end
    return arr
end

# 使用示例
println("合并排序后: ", merge_sort!(copy(arr)))

После сортировки слиянием: [11, 12, 22, 25, 34, 64, 90]

6. 金字塔排序（堆排序）

逻辑:

  1. 从数组构建最大堆
  2. 最大元素（根）随最后一个元素而变化。
  3. 减少堆的大小并重复该过程

难度：O（n log n）在任何情况下

In [ ]: 
function heap_sort!(arr)
    n = length(arr)
    
    # 构建堆（重新排列数组）
    for i in n÷2:-1:1
        heapify!(arr, n, i)
    end
    
    # 从堆中提取项目
    for i in n:-1:2
        arr[1], arr[i] = arr[i], arr[1]  # 将当前根移动到末尾
        heapify!(arr, i-1, 1)            # 在减少的堆上调用heapify
    end
    return arr
end

function heapify!(arr, n, i)
    largest = i  # 将最大的一个初始化为根
    l = 2i       # 左边的孩子
    r = 2i + 1    # 正确的孩子
    
    # 如果左边的孩子大于根
    if l <= n && arr[l] > arr[largest]
        largest = l
    end
    
    # 如果合适的孩子比最大的孩子大
    if r <= n && arr[r] > arr[largest]
        largest = r
    end
    
    # 如果最大不是根
    if largest != i
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify!(arr, n, largest)  # 递归变换受影响的子树
    end
end

# 使用示例
println("金字塔排序后: ", heap_sort!(copy(arr)))

После пирамидальной сортировки: [11, 12, 22, 25, 34, 64, 90]

性能比较

让我们比较一下不同算法在一个大阵列上的运行时间。:

In [ ]: 
# 连接图书馆
neededLibs = ["Random", "BenchmarkTools"]
for lib in neededLibs
    try
        eval(Meta.parse("using $lib"))
    catch ex
        Pkg.add(lib)
        eval(Meta.parse("using $lib"))
    end
end
In [ ]: 
# 生成大量随机数
Random.seed!(123)
big_arr = rand(1:1000, 1000)

println("10,000个元素数组的排序时间比较:")
@time bubble_sort!(copy(big_arr))     # 很慢！
@time insertion_sort!(copy(big_arr))  # 比泡沫更快，但仍然很慢
@time selection_sort!(copy(big_arr))  # 同样地
@time quick_sort!(copy(big_arr))      # 快！
@time merge_sort!(copy(big_arr))      # 快！
@time heap_sort!(copy(big_arr))       # 快！
@time sort!(copy(big_arr));           # 内置排序

Сравнение времени сортировки для массива из 10000 элементов:
  0.001370 seconds (346 allocations: 122.703 KiB)
  0.000199 seconds (3 allocations: 7.883 KiB)
  0.000579 seconds (3 allocations: 7.883 KiB)
  0.000080 seconds (3 allocations: 7.883 KiB)
  0.000224 seconds (4.00 k allocations: 202.836 KiB)
  0.000095 seconds (3 allocations: 7.883 KiB)
  0.000042 seconds (8 allocations: 16.078 KiB)

在Engee中内置排序

Engee提供内置优化排序功能 sort!()，这在大多数情况下使用快速排序和插入排序的组合（对于小数组）。

In [ ]: 
# 使用内置排序
arr = [64, 34, 25, 12, 22, 11, 90]
println("内置排序: ", sort!(copy(arr)))

Встроенная сортировка: [11, 12, 22, 25, 34, 64, 90]

选择排序算法

  1. 小数组(n<50)：插入排序
  2. 中等数组：快速排序或合并排序
  3. 大型数组：金字塔排序或内置排序！()
  4. 特殊情况:
    -几乎排序的数据：插入排序
    -数值范围有限：计数排序
    -不适合内存的非常大的数据：外部排序

结论

我们已经回顾了主要的排序算法，它们在Engee上的实现，以及它们工作的细节。:

  1. 简单排序（O（n2））：冒泡，插入，选择-适合训练和小数组
  2. 高效排序（O（n log n））：快速，合并，金字塔-在现实世界的任务中使用
  3. 内置Engee排序是大多数实际案例的最佳选择

选择正确的排序算法会显着影响程序的性能，特别是在处理大量数据时。