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

Алгоритм состоит из повторяющихся проходов по сортируемому массиву.
За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется перестановка элементов.
Алгоритмическая сложность - квадратичная O(n²).

Пример на Go

package main

import "fmt"

func main() {
   testData := []int{7, 2, -5, 3, 1, 9, 8}
   testDataLen := len(testData)
   var tmp int

   for i := 0; i < testDataLen; i++ {
      for j := 1; j < testDataLen; j++ {
         if testData[j-1] > testData[j] {
            tmp = testData[j-1]
            testData[j-1] = testData[j]
            testData[j] = tmp
         }
      }
   }

   fmt.Println(testData) // [-5 1 2 3 7 8 9]
}

Пример на PHP

$testArray = [7, 2, -5, 3, 1, 9, 8];

$len = count($testArray);
for ($i = 0; $i < $len; $i++) {
    for ($j = $i + 1; $j < ($len); $j++) {
        if ($testArray[$i] > $testArray[$j]) {
            $tmp = $testArray[$j];
            $testArray[$j] = $testArray[$i];
            $testArray[$i] = $tmp;
        }
    }
}

echo implode(", ", $testArray) . PHP_EOL; // -5, 1, 2, 3, 7, 8, 9

Сортировка вставками

Условно разделяем массив на 2 области - слева отсортированные значения, справа неотсортированные значения.
Последовательно берутся элементы неотсортированной области и вставляются в нужное место среди отсортированных.
Алгоритмическая сложность - квадратичная O(n²).

Пример на Go

package main

import "fmt"

func main() {
   testData := []int{7, 2, -5, 3, 1, 9, 8}
   testDataLen := len(testData)

   for i := 1; i < testDataLen; i++ {
      v := testData[i]
      idx := i

      for j := i - 1; j >= 0; j-- {
         if testData[j] > v {
            idx = j
         }
      }

      // Удаление
      testData = append(testData[:i], testData[i+1:]...)

      // Вставка
      testData = append(testData[:idx+1], testData[idx:]...)
      testData[idx] = v
   }

   fmt.Println(testData) // [-5 1 2 3 7 8 9]
}

Пример на PHP

$testArray = [7, 2, -5, 3, 1, 9, 8];

$len = count($testArray);
for ($i = 1; $i < $len; $i++) {
    $v = $testArray[$i];
    $idx = null;

    for ($j = $i - 1; $j >= 0; $j--) {
        if ($testArray[$j] > $v) {
            $idx = $j;
        }
    }

    if ($idx === null) {
        $idx = $i;
    }

    // Удаление
    unset($testArray[$i]);
    $testArray = array_values($testArray);

    // Добавление
    $testArray = array_merge(
        array_slice($testArray, 0, $idx),
        [$v],
        array_slice($testArray, $idx)
    );
}

echo implode(", ", $testArray) . PHP_EOL; // -5, 1, 2, 3, 7, 8, 9

Сортировка слиянием

Вначале рекурсивно разбиваем исходный массив на 2 части, пока размер массива не достигнет 1. Каждая из получившихся частей сортируется отдельно. Далее сливаем упорядоченные массивы в один.
Алгоритмическая сложность - линейно-логарифмическая O(n log n).

Пример на PHP

function mergeSort(array $arr): array {
    $count = count($arr);

    if ($count <= 1) {
        return $arr;
    }

    $left  = array_slice($arr, 0, (int) ($count / 2));
    $right = array_slice($arr, (int) ($count / 2));

    // Рекурсивный вызов
    $left = mergeSort($left);
    $right = mergeSort($right);

    return merge($left, $right);
}

function merge(array $left, array $right): array {
    $result = [];

    while (count($left) > 0 && count($right) > 0) {
        if ($left[0] < $right[0]) {
            array_push($result, array_shift($left));
        } else {
            array_push($result, array_shift($right));
        }
    }

    array_splice($result, count($result), 0, $left);
    array_splice($result, count($result), 0, $right);

    return $result;
}

$testArray = [7, 2, -5, 3, 1, 9, 8];

echo implode(", ", mergeSort($testArray)) . PHP_EOL; // -5, 1, 2, 3, 7, 8, 9

Пример на Go

package main

import "fmt"

func main() {
   testData := []int{7, 2, -5, 3, 1, 9, 8}

   fmt.Println(mergeSort(testData)) // [-5 1 2 3 7 8 9]
}

func mergeSort(data []int) []int {
   length := len(data)

   if length <= 1 {
      return data
   }

   mid := length / 2

   // Рекурсивный вызов
   return merge(mergeSort(data[:mid]), mergeSort(data[mid:]))
}

func merge(left []int, right []int) []int {
   var res []int

   for len(left) > 0 && len(right) > 0 {
      if left[0] < right[0] {
         res = append(res, left[0])
         left = left[1:]
      } else {
         res = append(res, right[0])
         right = right[1:]
      }
   }

   if len(left) > 0 {
      res = append(res, left...)
   }

   if len(right) > 0 {
      res = append(res, right...)
   }

   return res
}

Пирамидальная сортировка (сортировка кучей)

Используем бинарное сортирующее дерево (двоичная куча, пирамида). Оно должно удовлетворять условиям:
- значение в любой вершине не меньше, чем значения потомков;
- глубина всех листьев отличается не более чем на 1;
- последний слой заполняется слева направо.
Алгоритм:
- формируем пирамиду с наибольшим значение в корне кучи;
- меняем последний и первый элементы кучи;
- убираем последний элемент кучи (на данный момент он является наибольшим, откладываем его);
- сортируем полученную кучу;
- повторяем вышеуказанные шаги, пока размер кучи > 1.

Алгоритмическая сложность - линейно-логарифмическая O(n log n).

Пример на PHP

function heapSort(array $data): array {
    $len = count($data);

    for ($i = $len / (2 - 1); $i >= 0; $i--) {
        $data = heapify($data, $len, $i);
    }

    for ($i = $len-1; $i >= 0; $i--) {
        $temp = $data[0];
        $data[0] = $data[$i];
        $data[$i] = $temp;

        $data = heapify($data, $i, 0);
    }

    return $data;
}

function heapify(array $data, int $n, int $i): array {
    $largest = $i;
    $leftIndex = 2*$i + 1;
    $rightIndex = 2*$i + 2;

    if ($leftIndex < $n && $data[$leftIndex] > $data[$largest]) {
        $largest = $leftIndex;
    }

    if ($rightIndex < $n && $data[$rightIndex] > $data[$largest]) {
        $largest = $rightIndex;
    }

    if ($largest != $i) {
        $swap = $data[$i];
        $data[$i] = $data[$largest];
        $data[$largest] = $swap;

        $data = heapify($data, $n, $largest);
    }

    return $data;
}

$testArray = [7, 2, -5, 3, 1, 9, 8];

echo implode(", ", heapSort($testArray)) . PHP_EOL; // -5, 1, 2, 3, 7, 8, 9

Пример на Go

package main

import "fmt"

func main() {
   testData := []int{7, 2, -5, 3, 1, 9, 8}
   fmt.Println(heapSort(testData)) // [-5 1 2 3 7 8 9]
}

func heapSort(data []int) []int {
   data = buildMaxHeap(data)
   fmt.Printf("Heap: %v\n", data) // Heap: [9 3 8 2 1 -5 7]
   
   size := len(data)
   for i := size - 1; i >= 1; i-- {
      data[0], data[i] = data[i], data[0]
      size--
      heapify(data[:size], 0)
   }
   return data
}

func buildMaxHeap(data []int) []int {
   for i := len(data)/2 - 1; i >= 0; i-- {
      data = heapify(data, i)
   }

   return data
}

func heapify(data []int, index int) []int {
   leftIndex := getLeftIndex(index) + 1
   rightIndex := getRightIndex(index) + 1
   var largest int

   if leftIndex < len(data) && leftIndex >= 0 && data[leftIndex] > data[index] {
      largest = leftIndex
   } else {
      largest = index
   }

   if rightIndex < len(data) && rightIndex >= 0 && data[rightIndex] > data[largest] {
      largest = rightIndex
   }

   if largest != index {
      data[index], data[largest] = data[largest], data[index]
      data = heapify(data, largest)
   }

   return data
}

func getLeftIndex(i int) int {
   return 2 * i
}

func getRightIndex(i int) int {
   return 2*i + 1
}

Быстрая сортировка

Вначале выбираем опорный элемент. Далее сравниваем элементы с опорным и те, что меньше поместим перед ним, остальные после него. Рекурсивно повторяем действия для левой и правой части (применяем рекурсию пока размер части не станет <= 1).
Алгоритмическая сложность - линейно-логарифмическая O(n log n).

Пример на PHP

function quickSort(array $data) {
    $count = count($data);
    if ($count <= 1) {
        return $data;
    }

    $mainElem = $data[0]; // Берем за опорный 1-й элемент
    $left = [];
    $right = [];

    for ($i = 1; $i < $count; $i++) {
        if ($data[$i] < $mainElem) {
            $left[] = $data[$i];
        } else {
            $right[] = $data[$i];
        }
    }

    // Рекурсивные вызовы
    $left = quickSort($left); 
    $right = quickSort($right);

    return array_merge($left, array($mainElem), $right);
}

$testArray = [7, 2, -5, 3, 1, 9, 8];

echo implode(", ", quickSort($testArray)) . PHP_EOL; // -5, 1, 2, 3, 7, 8, 9

Пример на Go

package main

import "fmt"

func main() {
   testData := []int{7, 2, -5, 3, 1, 9, 8}
   fmt.Println(quickSort(testData)) // [-5 1 2 3 7 8 9]
}

func quickSort(data []int) []int {
   dataLen := len(data)
   if dataLen < 2 {
      return data
   }

   var left, right []int
   mainElem := data[0]

   for i := 1; i < dataLen; i++ {
      if data[i] < mainElem {
         left = append(left, data[i])
      } else {
         right = append(right, data[i])
      }
   }

   left = quickSort(left)
   right = quickSort(right)

   left = append(left, mainElem)
   return append(left, right...)
}

Источники:
https://en.wikipedia.org/wiki/Bubble_sort
https://en.wikipedia.org/wiki/Insertion_sort
https://en.wikipedia.org/wiki/Merge_sort
http://php-zametki.ru/php-nachinayushhim/136-php-sortirovka.html
https://en.wikipedia.org/wiki/Heapsort
https://en.wikipedia.org/wiki/Quicksort