基数排序

public static void radixSort(int[] array, int d) {
    int n = 1;
    int times = 1; // 排序次数，由位数最多的元素决定
    int[][] temp = new int[10][array.length]; //数组的第一维表示可能的余数0-9
    int[] order = new int[10]; //数组order用来表示该位是i的元素个数
    while (times <= d) {
        for (int i = 0; i < array.length; i++) {
            int lsd = ((array[i] / n) % 10);
            temp[lsd][order[lsd]] = array[i];
            order[lsd]++;
        }
        int k = 0;
        for (int i = 0; i < 10; i++) {
            if (order[i] != 0) {
                for (int j = 0; j < order[i]; j++) {
                    array[k] = temp[i][j];
                    k++;
                }
                order[i] = 0;
            }
        }
        n *= 10;
        times++;
    }
}

function radixSort($arr) {
    for ($i = 0; $i < 10; $i++) {
        $posArr[$i] = false;
    }
    $max = $arr[0];
    $length = count($arr);
    for ($i = 0; $i < $length; $i++) {
        if ($max < $arr[$i]) {
            $max = $arr[$i];
        }
    }
    $maxLength = strlen('' . $max);
    $time = 0;
    $baseNum = 1;
    while ($time < $maxLength) {
        $pos = $posArr;
        for ($i = 0; $i < $length; $i++) {
            $lsp = $arr[$i] / $baseNum % 10;
            $pos[$lsp][] = $arr[$i];
        }
        for ($i = 0; $i < 10; $i++) {
            if ($pos[$i] != false) {
                for ($j = 0; $j < count($pos[$i]); $j++) {
                    $temp[] = $pos[$i][$j];
                }
            }
        }
        $arr = $temp;
        unset($temp);
        unset($pos);
        $baseNum *= 10;
        $time++;
    }
    return $arr;
}

//优化
function radixSort(&$arr) {
    $length = count($arr);
    for ($i = 0; $i < 10; $i++) {
        $order[] = 0;
    }
    $max = $arr[0];
    for ($i = 1; $i < $length; $i++) {
        if ($arr[$i] > $max) {
            $max = $arr[$i];
        }
    }
    $maxTime = strlen('' . $max);
    $time = 0;
    $number = 1;
    while ($time < $maxTime) {
        for ($i = 0; $i < $length; $i++) {
            $left = intval($arr[$i] / $number) % 10;
            $pos[$left][$order[$left]] = $arr[$i];
            $order[$left]++;
        }
        $k = 0;
        for ($i = 0; $i < 10; $i++) {
            // for ($i = 9; $i >= 0; $i--) {
            if ($order[$i] != 0) {
                for ($j = 0; $j < $order[$i]; $j++) {
                    $arr[$k++] = $pos[$i][$j];
                }
                $order[$i] = 0;
            }
        }
        $number *= 10;
        $time++;
    }
}