6. Сортировка
O(N²): пузырьковая сортировка, сортировка выбором, сортировка вставками
O(NlogN): быстрая сортировка, сортировка слиянием, сортировка кучей
6. 1. Пузырьковая сортировка — O(N²)
Сравнивает первую цифру массива со значением следующей цифры, и если предыдущее значение больше, позиция цифры меняется. Повторите длину массива, чтобы сравнить индексы сзади.
func boubbleSort (_ data:[Int],_ n:Int) -> [Int]{ var data = data for i in 0...n-2 { let last = n-i for j in 0...last-1 { if data[j] > data[j+1] { let temp = data[j] data[j] = data[j+1] data[j+1] = temp } } } return data } boubbleSort([7,5,4,2,3,9], 5)
6. 2. Сортировка вставками — O(N²)
Если значение в самом конце массива меньше, чем значение предыдущей цифры на месте, поменяйте местами два значения. Если измененное значение меньше предыдущего, поменяйте местами два значения. Если обмен не производится, повторите со значением в конце массива.
func insertionSort (_ data:[Int],_ n:Int) -> [Int]{ var data = data var end = n-1 for i in (0...n-1).reversed() { for j in (0...end).reversed() { if data[i] < data[j] { let temp = data[i] data[i] = data[j] data[j] = temp } } end -= 1 } return data } insertionSort([7,5,4,2,3,9], 6)
6. 3. Сортировка выбором — O(N²)
Найдите наибольшее значение в массиве и замените его значением в конце массива. Затем повторите с массивом, кроме последнего.
func selectionSort (_ data:[Int],_ n:Int) -> [Int]{ var data = data var end = n-1 for i in 0...end { var largestIndex = 0 for j in 0...end { if data[j] > data[largestIndex] { largestIndex = j } } let temp = data[largestIndex] data[largestIndex] = data [n-1-i] data[n-1-i] = temp end -= 1 } return data } selectionSort([7,5,4,2,3,9], 6)
6. 4. Быстрая сортировка — O(NlogN)
Быстрая сортировка – лучший метод сортировки среди нескольких методов сортировки.
(Используются методы рекурсии, разделения и квантизации.)
- Определить опорное значение из текущих данных D Предположим, что это самое левое значение в текущем диапазоне данных.
- После определения опорного значения его следует разделить на две независимые части с центром в нем. (D1), которое меньше опорного значения слева от опорного значения, и только значения больше опорного значения справа от опорного значения (D2). Это позволяет частям D1 и D2 быть независимыми друг от друга, сводя общую проблему к двум независимым проблемам.
- Если вы разделите на D1 и D2, вы можете рекурсивно обработать два вышеуказанных шага.
- Если вы больше не можете уменьшить размер данных, возвращаются текущие значения.
var data = [5,2,7,4,1,10,6,3,8,9] func quickSort(_ left: Int,_ right: Int){ if (left < right){ var pivot = partition(left, right) quickSort(left, pivot-1) quickSort(pivot+1, right) } } func partition(_ left: Int,_ right: Int) -> Int { var i = left for j in (left + 1)...(right + 1) { if data[j] < data[left] { i += 1 (data[i], data[j]) = (data[j], data[i]) } } (data[i], data[left]) = (data[left], data[i]) return i } quickSort(0,9)
6. 5. Сортировка слиянием — O(NlogN)
- Разделить: разделяет массив, в котором хранятся данные, пополам.
- Conquer: упорядочить каждый массив циклически
- Слияние: объединение двух массивов
Базовая сортировка слиянием начинается с двух отсортированных данных A, B и массива C для слияния двух данных. Переменные i, j и count используются для отображения текущего расположения данных сравнения массива A, B и C, а начальное значение устанавливается в исходное положение каждой переменной.
func merge(left:[Int],right:[Int]) -> [Int] { var mergedList = [Int]() var left = left var right = right while left.count > 0 && right.count > 0 { if left.first! < right.first! { mergedList.append(left.removeFirst()) } else { mergedList.append(right.removeFirst()) } } return mergedList + left + right } func mergeSort(list:[Int]) -> [Int] { guard list.count > 1 else { return list } let leftList = Array(list[0..<list.count/2]) let rightList = Array(list[list.count/2..<list.count]) return merge(left: mergeSort(list:leftList), right: mergeSort(list:rightList)) } print(mergeSort(list:[5,2,7,4,1,10,6,3,8,9]))