基数排序

基数排序(radix sort)属于“分配式排序”(distribution sort),又称“桶子法”(bucket sort)或bin sort,顾名思义,它是透过键值的部份资讯,将要排序的元素分配至某些“桶”中,藉以达到排序的作用,基数排序法是属于稳定性的排序,其时间复杂度为O (nlog(r)m),其中r为所采取的基数,而m为堆数,在某些时候,基数排序法的效率高于其它的稳定性排序法

方法:最高位优先MSD、最低位优先LSD

思想:最低位优先LSD方案

1、  将待排数字根据个位上的数字进行排序

2、  将待第一步排序结果再按照十位上数字进行排序

3、  按照位数从低到高依次排序

示例:

 

$arr = array(1,4,5,89,22,44,5,33,6,7,82,332);
function getIndex($num, $index) {
    $val = pow(10, $index - 1);
    return ($num / $val) % 10;
}
function radix_sort($arr,$max_len) {
    for($i = 1; $i <= $max_len; $i++) {
        $temp = array_fill(0, 10, array());//填充桶
        foreach ($arr as $v) {
            echo $index = getIndex($v, $i);
            echo '#';
            $temp[$index][] = $v;
        }
        $arr = array();
        echo "\n第".$i. '次排序之后:';
        foreach ($temp as $v) {
            for($j =0 ;$j < count($v); $j++) {
                echo $v[$j] ."," ;
                $arr[] = $v[$j];
            }
        }
        echo "\n";
    }
    return $arr;
}
$arr = radix_sort($arr, 3);
print_r($arr);

 

以上示例有一个问题,如果排序的数字是负数呢?

$arr = array(1,4,5,89,22,44,-5,33,-6,7,-82,332);
function getIndex($num, $index) {
    $val = pow(10, $index - 1);
    return 10+($num / $val) % 10;
}
function radix_sort($arr,$max_len) {
    for($i = 1; $i <= $max_len; $i++) {
        $temp = array_fill(0, 19, array());//填充桶,负数填充-9~0~9对应0~10~19
        foreach ($arr as $v) {
            echo $index = getIndex($v, $i);
            echo '#';
            $temp[$index][] = $v;
        }
        $arr = array();
        echo "\n第".$i. '次排序之后:';
        foreach ($temp as $v) {
            for($j =0 ;$j < count($v); $j++) {
                echo $v[$j] ."," ;
                $arr[] = $v[$j];
            }
        }
        echo "\n";
    }
    return $arr;
}
$arr = radix_sort($arr, 3);
print_r($arr);

 

奇偶排序

原理

奇偶排序法的思路是在数组中重复两趟扫描。第一趟扫描选择所有的数据项对,a[j]和a[j+1],j是奇数(j=1, 3, 5……)。如果它们的关键字的值次序颠倒,就交换它们。第二趟扫描对所有的偶数数据项进行同样的操作(j=2, 4,6……)。重复进行这样两趟的排序直到数组全部有序。

示例

php
//奇偶排序
$arr = array(1,4,5,89,22,44,5,33,6,7,82,332);
$num = count($arr);
$sort = true;
while ($sort) {
    $sort = false;
    for($i = 0; $i<$num;$i+=2) {
        if($arr[$i] > $arr[$i+1]) {
            $temp = $arr[$i];
            $arr[$i] = $arr[$i+1];
            $arr[$i + 1] = $temp;
            $sort = true;
        }
    }
    for($j=1; $j<$num-1;$j+=2) {
        if($arr[$j] > $arr[$j + 1]) {
            $temp = $arr[$j];
            $arr[$j] = $arr[$j+1];
            $arr[$j + 1] = $temp;
            $sort = true;
        }
    }
    if(!$sort) {
        break;
    }
 
}
print_r($arr);

 

快速排序

思想:
通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
示例:

 1) {
        $temp = $arr[0];
        $x = $y = array();
        for($i = 1; $i < count($arr); $i++) {
            if($arr[$i] < $temp) {
                $x[] = $arr[$i];
            } else {
                $y[] = $arr[$i];
            }
        }
        $x = quick_sort($x);
        $y = quick_sort($y);
        return array_merge($x, array($temp),  $y);
    } else {
        return $arr;
    }
}
$arr = array(1,4,5,89,22,44,5,33,6,7,82,332);
$result = quick_sort($arr);
print_r($result);

最坏的情况下就是O(n2)

插入排序

原理:
1. 从第一个元素开始,该元素可以认为已经被排序
2. 取出下一个元素,在已经排序的元素序列中从后向前扫描
3. 如果该元素(已排序)大于新元素,将该元素移到下一位置
4. 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置
5. 将新元素插入到下一位置中
6. 重复步骤2~5

php
//从小到大排序
function insert_sort($arr){
    for($i = 1; $i < count($arr); $i++){
        $tmp=$arr[$i];
        $key=$i-1;
        while($key>=0 && $tmp < $arr[$key]){
            $arr[$key+1]=$arr[$key];
            $key--;
        }
        if($key+1 != $i)
            $arr[$key+1]=$tmp;
        }
        return $arr;
}
$arr = array(1,4,5,89,22,44,5,33,6,7,82,332);
$result = insert_sort($arr);
print_r($result);

 

冒泡排序

原理:
1、比较相邻的元素。如果第一个比第二个大(小),就交换他们两个。
2、对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大(小)的数。
3、针对所有的元素重复以上的步骤,除了最后一个。
4、持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较
分析:
最好的时间复杂度为O(n),最坏的时间复杂度为O(n2)
稳定性:
属于稳定性排序

Continue reading

桶排序

桶排序 (Bucket sort)或所谓的箱排序,是一个排序算法,工作的原理是将数组分到有限数量的桶子里。每个桶子再个别排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序)
思想:
设待排序序列的元素取值范围为0到m,则我们新建一个大小为m+1的临时数组并把初始值都设为0,遍历待排序序列,把待排序序列中元素的值作为临时数组的下标,找出临时数组中对应该下标的元素使之+1;然后遍历临时数组,把临时数组中元素大于0的下标作为值按次序依次填入待排序数组,元素的值作为重复填入该下标的次数,遍历完成则排序结束序列有序。
示例:

 $v){
    for($i = 0; $i < $v; $i++) {
        echo $k;
    }
}

 
应用大量数据排序
比如9亿不重复的9位数字排序,可以初始化10亿个bit来标示存在这个数字是否存在,如果该位是1就输出该位整数