Приветствую всех, сегодня хочу поговорить о алгоритме сортировки. Сегодня в программировании применяются множество готовых решений метод в этой задачи. Но рассмотреть я хотел бы сами алгоритмы сортировки.
Сортировка пузырьковым методом:
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();
}
Решил не углубляться в разбор метода, а показать наглядно что происходит внутри метода сортировки. Для этого посмотрим анимацию:
Сортировка слиянием:
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:
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();
}
Еще один пример быстрой сортировки:
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#
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)
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] + " ");
}
}Это конечно не все алгоритмы сортировки описаны мною, их куда больше, однако основные алгоритмы я вам показал. И в конце статьи хочу показать вам последнюю анимацию, которая визуально продемонстрирует принцип всех сортировок, а так же время работы методов по отношению друг к другу.
