Классификация

1. По степени роста сложности
2. По использованию дополнительной памяти
3. Рекурсивный или нет
4. По устойчивости
5. По методу сортировки: вставка, слияние, обмен

Распространенные алгоритмы

• Сортировка пузырьком
• Сортировка вставками
• Сортировка выбором
• Сортировка слиянием
• Быстрая сортировка

Ссылка на сайт с гифками, которые демонстрируют работу алгоритмов: https://www.toptal.com/developers/sorting-algorithms

Сортировка пузырьком

Самая стандартная и простая сортировка. Выполняет проходы по массиву и перемещает наибольший элемент в конец массива.

public void Sort(int[] inputArray)
{
	for (int i = 0; i < inputArray.Length; i++) {
		for (int j = 1; j < inputArray.Length; j++) {
			if (inputArray[j-1] > inputArray[j]) {
				Swap(inputArray, j-1, j);
			}
		}
	}
}

public void Swap(int[] inputArray, int indexLeft, int indexRight)
{
	if (indexLeft == indexRight) return;
	var temp = inputArray[indexLeft];
	inputArray[indexLeft] = inputArray[indexRight];
	inputArray[indexRight] = temp;
}

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

public static void Sort(int[] inputArray)
{
	int currentElementIndex= 1;
	while (currentElementIndex < inputArray.Length)
	{
		if (inputArray[currentElementIndex] < inputArray[currentElementIndex - 1]) {
			var newIndex = FindIndex(inputArray, inputArray[currentElementIndex]);
			Insert(inputArray, newIndex, currentElementIndex);
		}
		currentElementIndex++;
	}
}

public static int FindIndex(int[] inputArray, int element)
{
	for (int i = 0; i < inputArray.Length; i++)
	{
		if (inputArray[i] > element) {
			return i;
		}
	}
	return 0;
}

public static void Insert(int[] inputArray, int indexLeft, int indexRight)
{
	if (indexLeft == indexRight) return;
	var temp = inputArray[indexLeft];
	inputArray[indexLeft] = inputArray[indexRight];
	for (int current = indexRight; current > indexLeft; current--) {
		inputArray[current] = inputArray[current-1];
	}
	inputArray[indexLeft + 1] = temp;
}

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

public static void Sort(int[] input) {
	for (int i = 0; i < input.Length; i++) {
		var smallestElementIndex = FindIndexOfSmallestElement(input, i);
		Swap(input, smallestElementIndex, i);
	}
}

public static int FindIndexOfSmallestElement(int[] input, int startFrom = 0) {
	var smallestElementValue = input[startFrom];
	var smallestElementIndex = startFrom;
	for (int i = startFrom + 1; i < input.Length; i++)
	{
		if (smallestElementValue > input[i]) {
			smallestElementValue = input[i];
			smallestElementIndex = i;
		}
	}
	return smallestElementIndex;
}

public static void Swap(int[] input, int indexLeft, int indexRight)
{
	if (indexLeft == indexRight) return;
	var temp = input[indexLeft];
	input[indexLeft] = input[indexRight];
	input[indexRight] = temp;
}

Сортировка слиянием
Разбивает массив на подмассивы примерно одинакового размера, рекурсивно разбивает до тех пор, пока размер массива будет равен 1. После этого происходит сортировка частей и их соединение в один.

public static void Sort(int[] input) {
	if (input.Length <= 1) {
		return;
	}
	
	// Поделили массивы
	var leftSize = input.Length / 2;
	var rightSize = input.Length - leftSize;
	var left = new int[leftSize];
	var right = new int[rightSize];
	
	// Скопировали данные из основного массива
	Array.Copy(input, 0, left, 0, leftSize);
	Array.Copy(input, leftSize, right, 0, rightSize);
	
	Sort(left);
	Sort(right);
	
	Merge(input, left, right);
}

public static void Merge(int[] input, int[] left, int[] right) {
	var leftIndex = 0;
	var rightIndex = 0;
	var leftAndRightSize = left.Length + right.Length;
	
	for (int i = 0; i < leftAndRightSize; i++) {
		if (leftIndex >= left.Length) {
			input[i] = right[rightIndex];
			rightIndex++;
		}
		else if (rightIndex >= right.Length) {
			input[i] = left[leftIndex];
			leftIndex++;
		}
		else if (left[leftIndex] < right[rightIndex]) {
			input[i] = left[leftIndex];
			leftIndex++;
		}
		else {
			input[i] = right[rightIndex];
			rightIndex++;
		}
	}
}

Быстрая сортировка
Один из самых быстрых алгоритмов, о чем говорит название.

Этапы сортировки:
• Случайный выбор опорного элемента массива (pivotValue), относительно которого переупорядочиваются элементы массива.
• Переместить все значения, которые больше опорного, вправо, а все значения, что меньше опорного, влево.
• Повторить алгоритм для неотсортированной левой и правой части массива, пока каждый элемент не окажется на своей позиции.

public static void Sort(int[] input, int leftIndex, int rightIndex) {
	var i = leftIndex;
	var j = rightIndex;
	var pivot = input[(leftIndex + rightIndex) >> 1];
	
	while (i <= j) {
		while (input[i] < pivot) {
			i++;
		}
		while (input[j] > pivot) {
			j--;
		}
		
		if (i <= j) {
			Swap(input, i, j);
			j--;
			i++;
		}
		
		if (leftIndex < j) {
			Sort(input, leftIndex, j);
		}
		
		if (rightIndex > i) {
			Sort(input, i, rightIndex);
		}
	}
}

public static void Swap(int[] input, int indexLeft, int indexRight)
{
	if (indexLeft == indexRight) return;
	var temp = input[indexLeft];
	input[indexLeft] = input[indexRight];
	input[indexRight] = temp;
}