您的位置:

PHP排序算法详解

一、Python排序算法详解

Python中有许多内置的排序算法,主要包括快速排序、堆排序、归并排序、希尔排序等。下面以快速排序为例详解。


function quick_sort($arr) {
    $len = count($arr);
    if ($len <= 1) {
        return $arr;
    }
    $pivot = $arr[0];
    $left_arr = $right_arr = array();
    for ($i = 1; $i < $len; $i++) {
        if ($arr[$i] < $pivot) {
            $left_arr[] = $arr[$i];
        } else {
            $right_arr[] = $arr[$i];
        }
    }
    $left_arr = quick_sort($left_arr);
    $right_arr = quick_sort($right_arr);
    return array_merge($left_arr, array($pivot), $right_arr);
}

二、简单选择排序算法(C语言详解版)

简单选择排序是一种简单直观的排序算法,通过交换找到最小的元素放到已排好序的序列末尾。


void selection_sort(int a[], int n) {
    int i, j, min_idx;
    for (i = 0; i < n-1; i++) {
        min_idx = i;
        for (j = i+1; j < n; j++) {
            if (a[j] < a[min_idx]) {
                min_idx = j;
            }
        }
        int temp = a[min_idx];
        a[min_idx] = a[i];
        a[i] = temp;
    }
}

三、哈希排序算法详解

哈希排序算法主要是通过将值的索引映射到特定的桶中,将相似的元素分在同一个桶中,从而实现高效排序。


function hash_sort($arr) {
    $max_val = max($arr);
    $num_buckets = sqrt(count($arr));
    $buckets = array();
    for ($i = 0; $i < $num_buckets; $i++) {
        $buckets[$i] = array();
    }
    foreach ($arr as $val) {
        $idx = floor($num_buckets * $val / ($max_val + 1));
        array_push($buckets[$idx], $val);
    }
    foreach ($buckets as &$bucket) {
        sort($bucket);
    }
    unset($bucket);
    $res = array();
    foreach ($buckets as $bucket) {
        foreach ($bucket as $val) {
            array_push($res, $val);
        }
    }
    return $res;
}

四、归并排序算法详解

归并排序是一种采用分治策略的排序算法,将一个大问题拆分成多个小问题,逐一解决并将子问题的结果合并。


function merge($arr1, $arr2) {
    $res = array();
    while (count($arr1) && count($arr2)) {
        $val1 = $arr1[0];
        $val2 = $arr2[0];
        if ($val1 < $val2) {
            array_push($res, array_shift($arr1));
        } else {
            array_push($res, array_shift($arr2));
        }
    }
    if (count($arr1)) {
        array_splice($res, count($res), 0, $arr1);
    }
    if (count($arr2)) {
        array_splice($res, count($res), 0, $arr2);
    }
    return $res;
}

function merge_sort($arr) {
    $len = count($arr);
    if ($len <= 1) {
        return $arr;
    }
    $mid = floor($len / 2);
    $left_arr = array_slice($arr, 0, $mid);
    $right_arr = array_slice($arr, $mid);
    $left_arr = merge_sort($left_arr);
    $right_arr = merge_sort($right_arr);
    return merge($left_arr, $right_arr);
}

五、选择排序算法详解

选择排序是一种简单直观的排序算法,将数组中最小的元素交换到第一个位置,以此类推。


function selection_sort($arr) {
    $len = count($arr);
    for ($i = 0; $i < $len-1; $i++) {
        $min_idx = $i;
        for ($j = $i+1; $j < $len; $j++) {
            if ($arr[$j] < $arr[$min_idx]) {
                $min_idx = $j;
            }
        }
        $temp = $arr[$min_idx];
        $arr[$min_idx] = $arr[$i];
        $arr[$i] = $temp;
    }
    return $arr;
}

六、鸡尾酒排序算法详解

鸡尾酒排序是改进的冒泡排序算法,从左向右找到最大元素,再从右向左找到最小元素,重复上述过程直到排序完毕。


function cocktail_sort($arr) {
    $len = count($arr);
    $left = 0;
    $right = $len - 1;
    while ($left < $right) {
        for ($i = $left; $i < $right; $i++) {
            if ($arr[$i] > $arr[$i+1]) {
                $temp = $arr[$i];
                $arr[$i] = $arr[$i+1];
                $arr[$i+1] = $temp;
            }
        }
        $right--;
        for ($i = $right; $i > $left; $i--) {
            if ($arr[$i] < $arr[$i-1]) {
                $temp = $arr[$i];
                $arr[$i] = $arr[$i-1];
                $arr[$i-1] = $temp;
            }
        }
        $left++;
    }
    return $arr;
}

七、合并排序算法详解

合并排序算法是将两个有序数组合并成一个有序数组,先比较两个数组的第一个元素,取其中较小的放入合并数组中,将取数的数组指针后移,再次比较两个数组中的第一个元素,以此类推。


function merge_sort($arr) {
    $len = count($arr);
    if ($len <= 1) {
        return $arr;
    }
    $mid = floor($len / 2);
    $left_arr = array_slice($arr, 0, $mid);
    $right_arr = array_slice($arr, $mid);
    $left_arr = merge_sort($left_arr);
    $right_arr = merge_sort($right_arr);
    $merged_arr = array();
    $left = 0;
    $right = 0;
    while ($left < count($left_arr) && $right < count($right_arr)) {
        if ($left_arr[$left] < $right_arr[$right]) {
            array_push($merged_arr, $left_arr[$left]);
            $left++;
        } else {
            array_push($merged_arr, $right_arr[$right]);
            $right++;
        }
    }
    while ($left < count($left_arr)) {
        array_push($merged_arr, $left_arr[$left]);
        $left++;
    }
    while ($right < count($right_arr)) {
        array_push($merged_arr, $right_arr[$right]);
        $right++;
    }
    return $merged_arr;
}