September 13, 2019
Сортировки - Python
Алгоритмы сортировок на Python.
Сортировка вставками.
def insert_sort(arr): for i in range(len(arr)): value = arr[i] j = i while j and value < arr[j - 1]: arr[j] = arr[j - 1] j -= 1 arr[j] = value arr = [1, 4, 5, 0, 8, 9, 1, 9, 2, 11, 0, 9] answer = [1, 4, 5, 0, 8, 9, 1, 9, 2, 11, 0, 9] answer.sort() insert_sort(arr) assert arr == answer
Быстрая сортировка.
def quick_sort(nums): if not nums: return [] left = [] right = [] pivot = nums[0] for i in range(1, len(nums)): if nums[i] < pivot: left.append(nums[i]) else: right.append(nums[i]) return quick_sort(left) + [pivot] + quick_sort(right) arr = [1, 4, 5, 0, 8, 9, 1, 9, 2, 11, 0, 9] answer = [1, 4, 5, 0, 8, 9, 1, 9, 2, 11, 0, 9] answer.sort() assert quick_sort(arr) == answer
Сортировка Слиянием.
def merge_sort(arr): if len(arr) > 1: left = arr[len(arr) // 2:] right = arr[:len(arr) // 2] merge_sort(left) merge_sort(right) i, j, k = 0, 0, 0 while i < len(left) and j < len(right): if left[i] < right[j]: arr[k] = left[i] i += 1 else: arr[k] = right[j] j += 1 k += 1 while i < len(left): arr[k] = left[i] i += 1 k += 1 while j < len(right): arr[k] = right[j] j += 1 k += 1 arr = [1, 4, 5, 0, 8, 9, 1, 9, 2, 11, 0, 9] answer = [1, 4, 5, 0, 8, 9, 1, 9, 2, 11, 0, 9] answer.sort() merge_sort(arr) assert arr == answer
September 13, 2019, 12:44
0 views
0 reactions