排序算法 php实现

冒泡排序（Bubble Sort）

冒泡排序通过重复地遍历待排序的列表，比较相邻的元素并交换它们的位置，直到列表排序完成。

function bubbleSort($array) {
    $n = count($array);
    for ($i = 0; $i < $n - 1; $i++) {
        for ($j = 0; $j < $n - $i - 1; $j++) {
            if ($array[$j] > $array[$j + 1]) {
                $temp = $array[$j];
                $array[$j] = $array[$j + 1];
                $array[$j + 1] = $temp;
            }
        }
    }
    return $array;
}

选择排序（Selection Sort）

选择排序每次从未排序部分选择最小（或最大）的元素，放到已排序部分的末尾。

function selectionSort($array) {
    $n = count($array);
    for ($i = 0; $i < $n - 1; $i++) {
        $minIndex = $i;
        for ($j = $i + 1; $j < $n; $j++) {
            if ($array[$j] < $array[$minIndex]) {
                $minIndex = $j;
            }
        }
        if ($minIndex != $i) {
            $temp = $array[$i];
            $array[$i] = $array[$minIndex];
            $array[$minIndex] = $temp;
        }
    }
    return $array;
}

插入排序（Insertion Sort）

插入排序通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

function insertionSort($array) {
    $n = count($array);
    for ($i = 1; $i < $n; $i++) {
        $key = $array[$i];
        $j = $i - 1;
        while ($j >= 0 && $array[$j] > $key) {
            $array[$j + 1] = $array[$j];
            $j--;
        }
        $array[$j + 1] = $key;
    }
    return $array;
}

快速排序（Quick Sort）

快速排序采用分治法，选择一个基准元素，将数组分为两部分，一部分小于基准，另一部分大于基准，然后递归排序子数组。

function quickSort($array) {
    $length = count($array);
    if ($length <= 1) {
        return $array;
    }
    $pivot = $array[0];
    $left = $right = [];
    for ($i = 1; $i < $length; $i++) {
        if ($array[$i] < $pivot) {
            $left[] = $array[$i];
        } else {
            $right[] = $array[$i];
        }
    }
    return array_merge(quickSort($left), [$pivot], quickSort($right));
}

归并排序（Merge Sort）

归并排序将数组分成两半，递归排序每一半，然后将两个有序数组合并成一个有序数组。

function mergeSort($array) {
    $length = count($array);
    if ($length <= 1) {
        return $array;
    }
    $mid = (int)($length / 2);
    $left = array_slice($array, 0, $mid);
    $right = array_slice($array, $mid);
    return merge(mergeSort($left), mergeSort($right));
}

function merge($left, $right) {
    $result = [];
    while (count($left) > 0 && count($right) > 0) {
        if ($left[0] < $right[0]) {
            $result[] = array_shift($left);
        } else {
            $result[] = array_shift($right);
        }
    }
    return array_merge($result, $left, $right);
}

堆排序（Heap Sort）

堆排序利用堆数据结构（一种完全二叉树）进行排序，分为建堆和调整堆两个阶段。

function heapSort(&$array) {
    $n = count($array);
    for ($i = (int)($n / 2) - 1; $i >= 0; $i--) {
        heapify($array, $n, $i);
    }
    for ($i = $n - 1; $i > 0; $i--) {
        $temp = $array[0];
        $array[0] = $array[$i];
        $array[$i] = $temp;
        heapify($array, $i, 0);
    }
}

function heapify(&$array, $n, $i) {
    $largest = $i;
    $left = 2 * $i + 1;
    $right = 2 * $i + 2;
    if ($left < $n && $array[$left] > $array[$largest]) {
        $largest = $left;
    }
    if ($right < $n && $array[$right] > $array[$largest]) {
        $largest = $right;
    }
    if ($largest != $i) {
        $temp = $array[$i];
        $array[$i] = $array[$largest];
        $array[$largest] = $temp;
        heapify($array, $n, $largest);
    }
}

使用示例

$unsortedArray = [64, 34, 25, 12, 22, 11, 90];
$sortedArray = bubbleSort($unsortedArray);
print_r($sortedArray);