[Перевод] Python реализует алгоритм сортировки

задняя часть Python алгоритм Программа перевода самородков Алгоритм сортировки

Python реализует алгоритм сортировки

Введение

Иногда данные, которые мы храним или извлекаем в нашем приложении, могут быть не в порядке. Нам может потребоваться изменить порядок данных, если мы хотим правильно их обработать или использовать эффективно. За прошедшие годы компьютерщики создали множество алгоритмов сортировки для обработки данных.

В этой статье мы рассмотрим некоторые популярные алгоритмы сортировки, посмотрим, как они работают, и реализуем их на Python. Они также будут сравнивать, насколько быстро они сортируют элементы в списке.

Для простоты эти алгоритмы будут сортировать числа в списке в порядке возрастания. Конечно, вы можете настроить его в соответствии с вашими потребностями.

Пузырьковая сортировка

Этот простой алгоритм сортировки сравнивает элементы списка попарно, перебирая список и меняя их местами до тех пор, пока больший элемент не «поднимется» в конец списка, а меньший элемент не останется «внизу».

вводить

Сначала мы сравниваем первые два элемента списка. Если первый элемент больше второго, мы меняем их местами. Если они уже отсортированы, мы оставляем их как есть. Затем мы переходим к следующей паре элементов, сравниваем их значения и при необходимости меняем местами. Этот процесс продолжается до последней пары элементов в списке.

Когда он достигает конца списка, он повторяет этот процесс для каждой пары элементов. Однако этот процесс малоэффективен. Что, если нам нужно сделать только один обмен внутри массива? Почему мы все еще повторяемn^2раз, хотя массив уже отсортирован?

Очевидно, что для оптимизации алгоритма нам нужно остановить его, когда сортировка будет выполнена.

Итак, как мы узнаем, что сортировка выполнена? Если элементы в порядке, то нам не нужно продолжать менять местами. Поэтому всякий раз, когда значения меняются местами, мы будем устанавливать значение флага какTrueчтобы повторить процесс сортировки. Если обмен не происходит, значение флага останется таким же, какFalse, алгоритм остановится.

выполнить

После оптимизации мы можем реализовать пузырьковую сортировку с помощью следующего кода Python:

def bubble_sort(nums):
    # 我们将标志值 swapped 设为 True，以便循环能够执行至少一次
    swapped = True
    while swapped:
        swapped = False
        for i in range(len(nums) - 1):
            if nums[i] > nums[i + 1]:
                # 交换元素
                nums[i], nums[i + 1] = nums[i + 1], nums[i]
                # 把标志值设为 True 以便我们能再次循环
                swapped = True

# 检查是否能够正确执行
random_list_of_nums = [5, 2, 1, 8, 4]
bubble_sort(random_list_of_nums)
print(random_list_of_nums)

Этот алгоритм находится вwhileВыполняется внутри цикла и выходит из цикла только тогда, когда элементы нельзя поменять местами. Мы начнем сswappedустановить какTrue, чтобы гарантировать, что алгоритм может быть выполнен хотя бы один раз.

временная сложность

В худшем случае (когда списки идут в обратном порядке) алгоритму приходится менять местами каждый элемент массива. На каждой итерации значение флагаswappedбудет установлен наTrue. Итак, если у нас есть в спискеnэлементы, мы будем перебирать каждый элементnраз, поэтому временная сложность пузырьковой сортировки составляет O (n ^ 2).

сортировка выбором

Алгоритм делит список на две части: отсортированную часть и несортированную часть. Мы продолжаем удалять наименьший элемент из несортированной части списка и добавлять его в отсортированную часть.

вводить

На самом деле нам не нужно создавать новый список для отсортированных элементов, мы делаем самую левую часть списка отсортированной частью. Затем мы ищем во всем списке наименьший элемент и меняем его местами с первым элементом.

Теперь, когда мы знаем, что первый элемент списка в порядке, мы приступим к поиску наименьшего элемента из оставшихся элементов и заменим его вторым элементом. Это будет повторяться до тех пор, пока проверяемый элемент не станет последним элементом в оставшемся списке.

выполнить

def selection_sort(nums):
    # i 的值对应于已排序值的数量
    for i in range(len(nums)):
        # 我们假设未排序部分的第一项是最小的
        lowest_value_index = i
        # 这个循环用来迭代未排序的项
        for j in range(i + 1, len(nums)):
            if nums[j] < nums[lowest_value_index]:
                lowest_value_index = j
        # 将未排序元素的最小的值与第一个未排序的元素的值相交换
        nums[i], nums[lowest_value_index] = nums[lowest_value_index], nums[i]

# 检验算法是否正确
random_list_of_nums = [12, 8, 3, 20, 11]
selection_sort(random_list_of_nums)
print(random_list_of_nums)

можно увидеть сiувеличивается, нам нужно исследовать все меньше и меньше элементов.

временная сложность

В алгоритме сортировки выбором мы можем проверитьforКоличество циклов, чтобы легко получить временную сложность. дляnсписок элементов, внешний цикл повторяетсяnВторосортный. когдаiКогда значение равно 1, внутренний цикл повторяетсяn-1Второсортный,iПовторить, когда значение равно 2n-2раз и так далее.

Сумма количества сравнений алгоритма равна(n - 1) + (n - 2) + ... + 1, временная сложность алгоритма сортировки выбором составляет O (n ^ 2).

Сортировка вставками

Как и сортировка выбором, этот алгоритм делит список на отсортированную и несортированную части. Он вставит пройденный элемент в правильную позицию в отсортированном списке, перебирая несортированную часть.

вводить

Предположим, что первый элемент списка отсортирован. Затем мы переходим к следующему элементу, который мы называемx. еслиxЗначение больше, чем у первого элемента, и мы продолжим обход. еслиxзначение меньше, мы копируем значение первого элемента во второе место, затем устанавливаем значение первого элемента равнымx.

По мере обработки других элементов несортированной части мы продолжаем перемещаться вверх по большим элементам в отсортированной части, пока не встретим элемент меньшего размера, чемx, или элемент, который достигает конца отсортированной части, тоxпоставить его в нужное место.

выполнить

def insertion_sort(nums):
    # 我们假设第一个元素已经排好序，然后从第二个元素开始遍历
    for i in range(1, len(nums)):
        item_to_insert = nums[i]
        # 同时保留上一个元素的下标的索引
        j = i - 1
        # 如果排序段的所有项大于要插入的项，则将其向前移动
        while j >= 0 and nums[j] > item_to_insert:
            nums[j + 1] = nums[j]
            j -= 1
        # 插入的元素
        nums[j + 1] = item_to_insert

# 验证算法是否正确
random_list_of_nums = [9, 1, 15, 28, 6]
insertion_sort(random_list_of_nums)
print(random_list_of_nums)

временная сложность

В худшем случае массив будет отсортирован в обратном порядке. Внешний слой функции сортировки вставкамиforЦикл всегда повторяетсяn-1Второсортный.

В худшем случае внутренняяforЦикл будет меняться один раз, затем два раза и так далее. Количество обменов будет1 + 2 + ... + (n - 3) + (n - 2) + (n - 1), что делает временную сложность сортировки вставками O(n^2).

сортировка кучей

Этот популярный алгоритм сортировки, такой как сортировка вставками и сортировка выбором, делит список на отсортированную и несортированную части. Он преобразует несортированный сегмент списка в кучу структур данных, чтобы мы могли эффективно определить самый большой элемент.

вводить

Сначала мы преобразуем список в max-heap — бинарное дерево с наибольшим элементом в корне. Тогда поместим этот узел в конец списка. Затем мы перестраиваем этот с одним значением меньшемаксимальная куча, помещая новое максимальное значение перед последним элементом в списке.

Затем мы повторяем этот процесс построения кучи, пока все узлы не будут удалены.

выполнить

Создаем вспомогательную функциюheapifyчтобы помочь реализовать этот алгоритм:

def heapify(nums, heap_size, root_index):
    # 设最大元素索引为根节点索引
    largest = root_index
    left_child = (2 * root_index) + 1
    right_child = (2 * root_index) + 2

    # 如果根节点的左子节点是有效索引，并且元素大于当前最大元素，则更新最大元素
    if left_child < heap_size and nums[left_child] > nums[largest]:
        largest = left_child

    # 对根节点的右子节点执行相同的操作
    if right_child < heap_size and nums[right_child] > nums[largest]:
        largest = right_child

    # 如果最大的元素不再是根元素，则交换它们
    if largest != root_index:
        nums[root_index], nums[largest] = nums[largest], nums[root_index]
        # 调整堆以确保新的根节点元素是最大元素
        heapify(nums, heap_size, largest)

def heap_sort(nums):
    n = len(nums)

    # 利用列表创建一个最大堆
    # range 的第二个参数表示我们将停在索引值为 -1 的元素之前，即列表中的第一个元素
    # range 的第三个参数表示我们朝反方向迭代
    # 将 i 的值减少1
    for i in range(n, -1, -1):
        heapify(nums, n, i)

    # 将最大堆的根元素移动到列表末尾
    for i in range(n - 1, 0, -1):
        nums[i], nums[0] = nums[0], nums[i]
        heapify(nums, i, 0)

# 验证算法是否正确
random_list_of_nums = [35, 12, 43, 8, 51]
heap_sort(random_list_of_nums)
print(random_list_of_nums)

временная сложность

давайте сначала посмотримheapifyВременная сложность функции. В худшем случае самый большой элемент никогда не является корневым, что приводит к рекурсивным вызовам.heapifyфункция. Хотя рекурсивные вызовы могут показаться очень дорогими, имейте в виду, что здесь мы используем двоичное дерево.

Визуализируйте бинарное дерево с 3 элементами высоты 2. Теперь визуализируйте бинарное дерево с 7 элементами и высотой 3. Дерево растет логарифмически доn.heapifyФункция проходит дерево за время O(log(n)).

heap_sortфункция для перебора массиваnВторосортный. Таким образом, общая временная сложность алгоритма пирамидальной сортировки составляет O(nlog(n)).

Сортировка слиянием

Этот алгоритм «разделяй и властвуй» делит список на две части и продолжает делить оставшийся список пополам, пока в списке не останется только один элемент.

Смежные элементы становятся отсортированными парами, которые затем объединяются и сортируются с другими отсортированными парами. Этот процесс продолжается до тех пор, пока мы не получим отсортированный список со всеми отсортированными элементами в несортированном списке ввода.

вводить

Мы рекурсивно делим список пополам, пока не получим список длины 1. Затем мы объединяем каждую часть, которая была разделена, сортируя их в процессе.

Сортировка выполняется путем сравнения наименьшего элемента каждой половины. Первый элемент каждого списка является первым элементом для сравнения. Если первая половина начинается с меньшего значения, то мы добавляем ее в отсортированный список. Затем сравниваем второй минимум первой половины с первым минимумом второй половины.

Каждый раз, когда мы выбираем меньшее значение в начале половины, мы перемещаем элемент, который необходимо сравнить.

Введение

def merge(left_list, right_list):
    sorted_list = []
    left_list_index = right_list_index = 0

    # 我们经常使用列表长度，因此将它创建为变量方便使用
    left_list_length, right_list_length = len(left_list), len(right_list)

    for _ in range(left_list_length + right_list_length):
        if left_list_index < left_list_length and right_list_index < right_list_length:
            # 我们检查每个列表开头的哪个值较小
            # 如果左列表开头的项较小，将它添加到已排序列表
            if left_list[left_list_index] <= right_list[right_list_index]:
                sorted_list.append(left_list[left_list_index])
                left_list_index += 1
            # 如果右列表开头的项较小，将它添加到已排序列表
            else:
                sorted_list.append(right_list[right_list_index])
                right_list_index += 1

        # 如果已到达左列表的末尾，则添加右列表中的元素
        elif left_list_index == left_list_length:
            sorted_list.append(right_list[right_list_index])
            right_list_index += 1
        # 如果已到达右列表的末尾，则添加左列表中的元素
        elif right_list_index == right_list_length:
            sorted_list.append(left_list[left_list_index])
            left_list_index += 1

    return sorted_list

def merge_sort(nums):
    # 如果列表中只有一个元素，则返回它
    if len(nums) <= 1:
        return nums

    # 使用向下取整获取中点，索引必须是整数
    mid = len(nums) // 2

    # 对每一半进行排序和合并
    left_list = merge_sort(nums[:mid])
    right_list = merge_sort(nums[mid:])

    # 将已排序的列表合并为新列表
    return merge(left_list, right_list)

# 验证算法是否正确
random_list_of_nums = [120, 45, 68, 250, 176]
random_list_of_nums = merge_sort(random_list_of_nums)
print(random_list_of_nums)

Пожалуйста, обрати внимание,merge_sort()Функция отличается от предыдущих алгоритмов сортировки тем, что возвращает новый отсортированный список вместо сортировки существующего списка.

Таким образом, сортировка слиянием требует места для создания нового списка того же размера, что и входной список.

временная сложность

давайте сначала посмотримmergeфункция. Он принимает два списка и перебираетnраз, из которыхn- это объединенный размер двух списков.merge_sortФункция разбивает заданный массив на 2 и рекурсивно сортирует подмассивы. Поскольку входные данные для рекурсии составляют половину заданного массива, как двоичное дерево, время обработки увеличивается логарифмически доn.

Таким образом, общая временная сложность алгоритма сортировки слиянием составляет O(nlog(n)).

быстрая сортировка

Этот алгоритм «разделяй и властвуй» является наиболее часто используемым алгоритмом сортировки в этой статье. При разумном использовании он очень эффективен и не требует дополнительного места, как сортировка слиянием. Мы разбиваем список по базовому значению и сортируем элементы по базовому значению.

вводить

Быстрая сортировка сначала разделяет список — выбирает первое значение списка для сортировки. Это значение называется эталонным значением. Все элементы меньше базового значения будут перемещены влево от него.

Теперь, когда базовое значение находится в нужном месте, мы рекурсивно сортируем элементы вокруг базового значения, пока не будет отсортирован весь список.

выполнить

# 快速排序分区有不同的方法，下面实现了 Hoare 的分区方案。Tony Hoare 还创建了快速排序算法。
def partition(nums, low, high):
    # 我们选择中间元素作为基准值。
    # 有些实现方法选择第一个元素或最后一个元素作为基准值。 
    # 有时将中间元素或一个随机元素作为基准值。
    # 还有很多可以选择或创建的方法。
    pivot = nums[(low + high) // 2]
    i = low - 1
    j = high + 1
    while True:
        i += 1
        while nums[i] < pivot:
            i += 1

        j -= 1
        while nums[j] > pivot:
            j -= 1

        if i >= j:
            return j

        # 如果 i 处的元素（在基准值左侧）大于 j 处的元素（在基准值右侧），则交换它们。
        nums[i], nums[j] = nums[j], nums[i]

def quick_sort(nums):
    # 创建一个辅助函数来进行递归调用
    def _quick_sort(items, low, high):
        if low < high:
            # 这是基准元素后的索引，我们的列表在这里被拆分
            split_index = partition(items, low, high)
            _quick_sort(items, low, split_index)
            _quick_sort(items, split_index + 1, high)

    _quick_sort(nums, 0, len(nums) - 1)

# 检验算法是否正确
random_list_of_nums = [22, 5, 1, 18, 99]
quick_sort(random_list_of_nums)
print(random_list_of_nums)

временная сложность

Худший случай — всегда выбирать наименьший или наибольший элемент в качестве базового значения. Это создаст размерn-1разделы, что приводит к рекурсивным вызовамn-1Второсортный. Это приводит к наихудшей временной сложности O (n ^ 2).

Хотя наихудший случай хуже, быстрая сортировка по-прежнему широко используется, потому что ее средняя временная сложность намного быстрее, чем у других алгоритмов сортировки. Несмотря на то чтоpartitionФункция использует вложенный цикл while, но сравнивает все элементы массива для обмена. Следовательно, его временная сложность составляет всего O(n).

Если вы выберете хорошее базовое значение, функция быстрой сортировки разделит массив на две части, которые будутnЛогарифмический рост. Следовательно, средняя временная сложность алгоритма быстрой сортировки составляет O(nlog(n)).

Встроенные функции сортировки Python

Хотя понимание этих алгоритмов сортировки полезно, в большинстве проектов Python вы, вероятно, будете использовать функции сортировки, уже предусмотренные в языке.

Мы можем изменить список так, чтобы его содержимоеsort()Сортировать по методу:

apples_eaten_a_day = [2, 1, 1, 3, 1, 2, 2]
apples_eaten_a_day.sort()
print(apples_eaten_a_day) # [1, 1, 1, 2, 2, 2, 3]

или мы можем использоватьsorted()Функция создает новый отсортированный список:

apples_eaten_a_day_2 = [2, 1, 1, 3, 1, 2, 2]
sorted_apples = sorted(apples_eaten_a_day_2)
print(sorted_apples) # [1, 1, 1, 2, 2, 2, 3]

Все они отсортированы в порядке возрастания, но вы можетеreverseустановлен флагTrueлегко сортировать по убыванию:

# 对列表进行反向排序
apples_eaten_a_day.sort(reverse=True)
print(apples_eaten_a_day) # [3, 2, 2, 2, 1, 1, 1]

# 反向排序以获取新列表
sorted_apples_desc = sorted(apples_eaten_a_day_2, reverse=True)
print(sorted_apples_desc) # [3, 2, 2, 2, 1, 1, 1]

В отличие от созданной нами функции алгоритма сортировки, обе эти функции могут сортировать списки кортежей и классов.sorted()Функция может сортировать любой итерируемый объект, в том числе — можно создавать списки, строки, кортежи, словари, наборы и пользовательскиеитератор.

Эти функции сортировки реализуютTim Sortалгоритм, основанный на сортировке слиянием и сортировке вставками.

сравнение скорости

Чтобы увидеть, насколько быстро они работают, мы создаем список из 5000 чисел от 0 до 1000. Затем мы вычисляем время, необходимое для завершения каждого алгоритма. Каждый алгоритм запускается 10 раз, чтобы мы могли построить более надежную модель производительности.

Вот результат, время в секундах:

Run пузырь выберите вставлять куча сливаться быстрый
1 5.53188 1.23152 1.60355 0.04006 0.02619 0.01639
2 4.92176 1.24728 1.59103 0.03999 0.02584 0.01661
3 4.91642 1.22440 1.59362 0.04407 0.02862 0.01646
4 5.15470 1.25053 1.63463 0.04128 0.02882 0.01860
5 4.95522 1.28987 1.61759 0.04515 0.03314 0.01885
6 5.04907 1.25466 1.62515 0.04257 0.02595 0.01628
7 5.05591 1.24911 1.61981 0.04028 0.02733 0.01760
8 5.08799 1.25808 1.62603 0.04264 0.02633 0.01705
9 5.03289 1.24915 1.61446 0.04302 0.03293 0.01762
10 5.14292 1.22021 1.57273 0.03966 0.02572 0.01606
средний 5.08488 1.24748 1.60986 0.04187 0.02809 0.01715

Если вы проверите это самостоятельно, вы получите разные значения, но наблюдаемые модели производительности должны быть одинаковыми или похожими. Пузырьковая сортировка — самый медленный и худший алгоритм из всех. Хотя он полезен как введение в сортировку и алгоритмы, он не подходит для практического использования.

Мы также заметили, что быстрая сортировка работает очень быстро, почти в два раза быстрее, чем сортировка слиянием, и не требует дополнительного места во время выполнения. Напомним, что наше разбиение основано на среднем элементе списка, и разные методы разбиения могут дать разные результаты.

Поскольку сортировка вставками выполняет гораздо меньше сравнений, чем сортировка выбором, реализации сортировки вставками, как правило, быстрее, но в наших тестах сортировка выбором была немного быстрее.

Сортировка вставками меняет местами элементы чаще, чем сортировка выбором. Этот «обратный» результат правдоподобен, если подкачка значений занимает больше времени, чем сравнение значений.

Помните о сценариях использования при выборе алгоритма сортировки, так как это может повлиять на производительность.

Суммировать

Алгоритмы сортировки дают нам множество способов сортировки данных. Мы рассмотрели 6 различных алгоритмов — пузырьковая сортировка, сортировка выбором, сортировка вставками, сортировка слиянием, сортировка кучей, быстрая сортировка — и их реализация в Python. .

Количество сравнений и перестановок, выполняемых алгоритмом, и среда, в которой выполняется код, являются ключевыми факторами, определяющими производительность. В реальных приложениях Python рекомендуется придерживаться встроенных функций сортировки Python из-за их гибкости ввода и скорости.

Если вы обнаружите ошибки в переводе или в других областях, требующих доработки, добро пожаловать наПрограмма перевода самородковВы также можете получить соответствующие бонусные баллы за доработку перевода и PR. начало статьиПостоянная ссылка на эту статьюЭто ссылка MarkDown этой статьи на GitHub.

Программа перевода самородковэто сообщество, которое переводит высококачественные технические статьи из Интернета сНаггетсДелитесь статьями на английском языке на . Охват контентаAndroid,iOS,внешний интерфейс,задняя часть,блокчейн,продукт,дизайн,искусственный интеллектЕсли вы хотите видеть более качественные переводы, пожалуйста, продолжайте обращать вниманиеПрограмма перевода самородков,официальный Вейбо,Знай колонку.

Категории