Приветствую всех, сегодня хочу поговорить о алгоритме сортировки. Сегодня в программировании применяются множество готовых решений метод в этой задачи. Но рассмотреть я хотел бы сами алгоритмы сортировки.
Сортировка пузырьковым методом:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
private static void BubbleSort(int[] array) { for (int i = 0; i < array.Length; i++) for (int j = 0; j < array.Length - 1; j++) if (array[j] > array[j + 1]) { int t = array[j + 1]; array[j + 1] = array[j]; array[j] = t; } } public static void Main() { int[] array = {5,3,4,9,7,2,1,8,6 }; BubbleSort(array); foreach (int e in array) Console.WriteLine(e); Console.ReadKey(); } |
Решил не углубляться в разбор метода, а показать наглядно что происходит внутри метода сортировки. Для этого посмотрим анимацию:
Сортировка слиянием:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
static int[] temporaryArray; static void Merge(int[] array, int start, int middle, int end) { var leftPtr = start; var rightPtr = middle + 1; var length = end - start + 1; for (int i = 0; i < length; i++) { if (rightPtr > end || (leftPtr <= middle && array[leftPtr] < array[rightPtr])) { temporaryArray[i] = array[leftPtr]; leftPtr++; } else { temporaryArray[i] = array[rightPtr]; rightPtr++; } } for (int i = 0; i < length; i++) array[i + start] = temporaryArray[i]; } static void MergeSort(int[] array, int start, int end) { if (start == end) return; var middle = (start + end) / 2; MergeSort(array, start, middle); MergeSort(array, middle + 1, end); Merge(array, start, middle, end); } static void MergeSort(int[] array) { temporaryArray = new int[array.Length]; MergeSort(array, 0, array.Length - 1); } public static void Main() { int [] array = {3,2,5,7,8,1,9 }; MergeSort(array); foreach (var e in array) Console.WriteLine(e); Console.ReadKey(); } |
Принцип работы сортировки слияние так же можете увидеть на анимации ниже:
Сортировка Quick-Sort и сортировка Hoare-Sort:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
static void HoareSort(int[] array, int start, int end) { if (end == start) return; var pivot = array[end]; var storeIndex = start; for (int i = start; i <= end - 1; i++) if (array[i] <= pivot) { var t = array[i]; array[i] = array[storeIndex]; array[storeIndex] = t; storeIndex++; } var n = array[storeIndex]; array[storeIndex] = array[end]; array[end] = n; if (storeIndex > start) HoareSort(array, start, storeIndex - 1); if (storeIndex < end) HoareSort(array, storeIndex + 1, end); } static void HoareSort(int[] array) { HoareSort(array, 0, array.Length - 1); } static Random random = new Random(); public static void Main() { int [] array = {3,2,5,7,8,1,9 }; HoareSort(array); foreach (var e in array) Console.WriteLine(e); Console.ReadKey(); } |
Еще один пример быстрой сортировки:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 |
class Program { static void Main(string[] args) { int[] i = {4,3,7,23,6,8,123,6,32 }; QuickSort(i,0,8); foreach(int w in i) { Console.WriteLine(w); } Console.ReadKey(); } private static int[] QuickSort(int[] a, int i, int j) { if (i < j) { int q = Partition(a, i, j); a = QuickSort(a, i, q); a = QuickSort(a, q + 1, j); } return a; } private static int Partition(int[] a, int p, int r) { int x = a[p]; int i = p - 1; int j = r + 1; while (true) { do { j--; } while (a[j] > x); do { i++; } while (a[i] < x); if (i < j) { int tmp = a[i]; a[i] = a[j]; a[j] = tmp; } else { return j; } } } } |
Принцип работы сортировки Quick-Sort и сортировка Hoare-Sort так же можете увидеть на анимации ниже:
Существуют:
- алгоритмы сортировки O(n2) вроде сортировки вставками, пузырьком и выбором, которые используются в особых случаях;
- быстрая сортировка (общего назначения): в среднем O(n log n) обменов, но худшее время – O(n2), если массив уже отсортирован, или элементы равны;
- алгоритмы O(n log n), такие как сортировка слиянием и кучей (пирамидальная сортировка), которые также являются хорошими алгоритмами сортировки общего назначения;
- O(n) или линейные алгоритмы сортировки (выбор, выбор с обменом, выбор с подсчетом) для списков целых чисел, которые могут быть подходящими в зависимости от характера целых чисел в ваших списках.
Алгоритм сортировка подсчетом O(n ) C#
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
private static void CountingSort(int[] arr) { int max = arr.Max(); int min = arr.Min(); int[] count = new int[max - min + 1]; int z = 0; for (int i = 0; i < count.Length; i++) { count[i] = 0; } for (int i = 0; i < arr.Length; i++) { count[arr[i] - min]++; } for (int i = min; i <= max; i++) { while (count[i - min]-- > 0) { arr[z] = i; z++; } } foreach (var x in arr) { Console.Write(x + " "); } } |
Алгоритм сортировки методом отбора О(n)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
public static void Sort(int [] a) { int tmp, min_key; for (int j = 0; j < a.Length - 1; j++) { min_key = j; for (int k = j + 1; k < a.Length; k++) { if (a[k] < a[min_key]) { min_key = k; } } tmp = a[min_key]; a[min_key] = a[j]; a[j] = tmp; } for (int i = 0; i < a.Length; i++) { Console.Write(a[i] + " "); } } |
Это конечно не все алгоритмы сортировки описаны мною, их куда больше, однако основные алгоритмы я вам показал. И в конце статьи хочу показать вам последнюю анимацию, которая визуально продемонстрирует принцип всех сортировок, а так же время работы методов по отношению друг к другу.
