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
    
    # Если правый дочерний больше largest
    if r <= n && arr[r] > arr[largest]
        largest = r
    end
    
    # Если largest не корень
    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("Сравнение времени сортировки для массива из 10000 элементов:")
@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排序是大多数实际案例的最佳选择

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