阅读 607

干货分享:大话12种排序算法

常见的排序算法:

  • 快速排序、堆排序、归并排序、选择排序
  • 插入排序、二分插入排序
  • 冒泡排序、鸡尾酒排序
  • 桶排序、计数排序、基数排序、位图排序

技能点
1.归并排序在O(N*logN)的几种排序方法(快速排序,归并排序,希尔排序,堆排序)效率比较高。
2.位图排序、计数排序 不是比较排序,通过空间消耗,实现时间复杂度O(n)的排序。

快速排序

通过一趟排序将待排记录分割成独立的A、B两部分,A部分全部小于基准值,B部分全部大于基准值。然后在对两部分做相同的处理,已完成排序的功能。

算法描述与分析
  1. 从数列中挑选一个元素,作为基准值, pivot;
  2. 便利排序数列,比基准值小的放在左边A,大的放在右边B(相同的放在任意一边)。待分组完成后基准值就处于A、B的中间位置。 这个过程称为分区(partition)操作,
    两种实现方式具体实现见代码
  3. 递归排序A、B两部分,重复上面1 2两步,进行排序。


    快速排序-图例
复杂度

时间复杂度:
A.

o(nlogn)
* : 将数组分解为一些列小问题进行独立解决,上述的过程重复logn次得到有序的序列; 每次都需要对n个进行一次处理,所以时间复杂度为 n*logn

B. o(n^2): 固定选择第一个元素做基准值,对倒序数组进行正序排列;每次划分只得到一个比上一次划分少一个记录的子序列,每次只排一个。相当于向后冒泡排序,所以时间复杂度为o(n^2)

空间复杂度:
额外使用的空间需要看具体的代码实现,理论上最优情况下空间复杂度为o(1),只是用一个交换空间; 如果考虑递归的实现逻辑则复杂度为 o(logn)

代码实现

教科书式实现:

//普通方法实现
function quick_sort( &$arr, $left, $right ){
    if( $left < $right){
        //取基准值,取最左边的一个元素
        $pivot = $arr[$left];
        //随机取基准值 - 避免对倒序数组进行正序排序时,时间复杂度 O(n^2)的情况
        // $k = rand($left, $right);
        // swap($arr, $left, $k);
        // $pivot = $arr[$left];

        $i = $left; $j = $right;
       //一趟排序比较
        while($i < $j){
            //基准值从左边选取的,所以先从右侧开始比较;反之亦然。(注)
            while( $arr[$j] >= $pivot && $j > $i){
                $j--;
            }
            swap($arr, $i, $j);
            while( $arr[$i] < $pivot && $i < $j ){
                $i++;
            }
            swap($arr, $i, $j);
        }
        quick_sort($arr, $left, $i-1);  //对左边内容进行排序
        quick_sort($arr, $i+1, $right); //右边内容进行排序
    }
}

$arr = [49, 38, 65, 97, 76, 13, 27, 50];
quick_sort($arr, 0, count($arr)-1 );
echo implode(',', $arr);
复制代码

剑指offer的实现:

//分区方法. 这个思想很重要,可以在多个问题中使用。如:取前几名、字符串大小写字母分组等
function partition(&$arr, $left, $right){
    //随机、取最后一个为基准值,方便从头开始遍历
    $k = rand($left, $right);
    swap($arr, $k, $right);
    $pivot = $arr[$right]; 
    // 取两个指针A B,从{$left}开始走,B在遇到小于基准值是前走; 
    // 当A遇到小于基准值时和B处交换值;然后B指针前移一位。 
    // 完成一遍遍历,B指针的位置就是分割位。在把基准值替换到B+1即可
    $b = $left-1;
    for($a=$left; $a<=$right; $a++){
        if( $arr[$a] < $pivot){
            $b++;
            if( $a != $b){
                swap($arr, $a, $b);
            }
        }
    }

    $b++;  //指针后移一位,然后替换基准值,保证前面的都小、后面的都大
    swap($arr, $b, $right);
    return $b;
}
//交换元素。除了这种方式还可以使用:
// a=a+b;  b=a-b ;  a=a-b,加法来实现,不申请额外空间
// a=a^b;  b = a^b; a = b^a,异或来实现
function swap(&$arr, $i, $j){
    $t = $arr[$i];
    $arr[$i] = $arr[$j];
    $arr[$j] = $t;
}
//排序
function quick_sort( &$arr, $left, $right ){
    if( $left < $right){
        $index = partition($arr, $left, $right);
        quick_sort($arr, $left, $index-1);
        quick_sort($arr, $index+1, $right);
    }
}

$arr = [49, 38, 65, 97, 76, 13, 27, 50];
quick_sort($arr, 0, count($arr)-1 );
echo implode(',', $arr);

复制代码

运行耗时出现两种情况:

A: 13,27,38,49,50,65,76,97[Finished in 0.2s]
B: 13,27,38,49,50,65,76,97[Finished in 0.1s]

原因:排序使用了随机基准值的方法,所以分区比较、分区大小都是随机的。所以递归次数会有不同,耗时自然也就不同。
复制代码

堆排序

利用堆这种数据结构,堆积生成一个近似完全的二叉树,并且满足堆积性质:即子节点的建值总是小于(或大于)它的父节点。 二叉树使用数组来实现,从头到尾对应堆的从上到下。

示例
最大堆(父节点大于任何一个子节点),则根节点时最大值。将根节点取出来,剩下的进行堆调整生成最大堆;重复上述步骤,直到堆无节点时完成排序。

海量数据TopK问题
用堆排序来解决海量数据TopK 问题会非常好。构建K个节点的最小堆;遍历数据,当数据大于最小根节点时替换根节点,进行堆调整,生成最小堆;遍历结束时,堆会保存其中最大的K个元素; 在进行堆排序,生成K个元素从大到小的排列。

算法描述与分析:

我们这里先介绍几个问题,一步步推到堆排序。
什么是堆
定义上面已有说明,示例如下:

最小堆结构

使用数组存储:$arr = [1, 2, 3, 17, 19, 36, 7, 15, 170]

堆调整
为了保证堆的特性而做的一个操作。将该根节点就行下沉操作,一直沉到合适的位置,使得刚才的子树满足堆的性质。
例如对最大堆进行堆调整:
1.对应的数组元素A[i], 左孩子 left(2i+1), 右孩子right(2i+2), 中找最大的那一个,将其下标存入largest中;
2.如果A[i] 是最大的元素,则程序直接结束;
3.否则,i的某个子节点为最大元素,将A[i] 与 A[largest] 交换;
4.在从交换的子子节点开始,重复1,2,3步,直到叶子节点,完成一次堆调整。

堆调示例

建堆
建堆就是一个不断进行堆调整的过程。在数组中,我们一般从第n/2个数开始做堆调整,一直到下标为0的数

(因为下标大于n/2的数,都是叶子节点,无子数,所以其子数已经满足堆的性质了)

堆调整只判断节点子树,进行该节点下沉操作,并不和父节点进行比较,
所以建堆时必须从后向前进行,首先保证子树满足特性,在一步步往上推。

ps: 数组下标从0开始,建堆节点应从下标 n/2 -1 开始

堆排序
堆排序是在建堆完成之后,进行的操作。
以最大堆为例,堆以数组形式进行存储,所以A[0]是最大值,将A[0]与A[n-1]交换,然后对A[0n-2]进行堆调整。第二次将A[0]与A[n-2]进行交换,A[0n-3]进行堆调整,重复这样的操作直到A[0]与A[1]进行交换。 每次都将最大的数移入后面的区间,故操作完成之后,所得的数组就是从小到大有序排列的了。

堆排序示例

堆排序图解

堆排序

堆排序
复杂度

时间复杂度:

O(n
logn)
* : 建堆过程为O(n), 堆调整过程为O(nlogn)
空间复杂度:
O(1) : 就地排序

代码实现
<?php
$arr = [49, 38, 65, 97, 76, 13, 27, 50];
sortHeap($arr);

function sortHeap(&$arr){
    $heap_size = count($arr) - 1;
    createHeap($arr, $heap_size );
    echo '建堆结果:'.implode(',', $arr)."\r\n";
    heapPrint($arr, $heap_size);

    //堆排序
    $n = $heap_size;
    for($i=0; $i<=$n; $i++ ){
        swap($arr, 0, $heap_size); //最大值替换到最后面
        $heap_size--;
        adjustHeap($arr, $heap_size, 0); //A[0]替换为新的值,从该节点进行堆调整
    }
    echo '堆排序结果'.implode(',', $arr)."\r\n";
}

//建堆
function createHeap( &$arr, $heap_size){
    $n = floor($heap_size/2) -1;
    for($i=$n; $i>=0; $i-- ){  
        // 从最后一个非叶子节点开始,下标递减进行建堆。 
        // 保证节点的子树满足堆的性质,才能进一步对节点的父节点进行堆调整; 否则会有问题
        adjustHeap($arr, $heap_size, $i);
    }

}

//堆调整 - 最大堆特性
function adjustHeap( &$arr, $heap_size, $i){
    $left = 2*$i + 1;    //左子节点
    $right = 2*$i + 2;   //右子节点
    $largest = $i;       //默认最大节点为当前节点
    while( $left < $heap_size || $right<$heap_size){
        if( $left < $heap_size && $arr[$left] > $arr[$largest] ){
            $largest = $left; //左子节点大于目前值最大节点
        }
        if( $right<$heap_size && $arr[$right] > $arr[$largest] ){
            $largest = $right; //右子节点大于最大节点
        }
        //子节点大于该节点,需要将该节点下沉,并对下沉后的节点进行子树堆调整
        if($largest != $i){
            swap($arr, $largest, $i);
            $i = $largest;
            $left = 2*$i+1;
            $right = 2*$i+2;
        }else{
            // 该节点值是最大值时,结束调整。 
            // 因为:深层次的子树在建堆时已经满足堆性质,不需要再进行判断
            break;
        }
    }
}

function swap(&$arr, $i, $j){
    $t = $arr[$i];  $arr[$i] = $arr[$j];  $arr[$j] = $t;
}

//堆打印
function heapPrint($arr, $heap_size){
    //判断有多少行
    $rows = 1;
    while( pow(2, $rows-1) < $heap_size ){ $rows++;}
    //最后一行叶子节点的个数,最大个数
    $lastNumbers = pow(2, $rows-1);

    //输出
    $row = 1;
    $num = pow(2, $row-1);
    for( $i=0; $i<$heap_size; $i++){
        $t = $lastNumbers/ ( pow(2, $row-1) +1 ); //空格平均分割。除以(数字个数+1)
        $t = ceil($t);
        for($j=0; $j<$t; $j++){ echo " " ; }
        echo $arr[$i];
        if( $i+1 == $num ){
            echo "\r\n";
            $row++;
            $num += pow(2, $row-1);
        }
    }
    echo "\r\n";
}
复制代码

运行结果:

建堆结果:97,76,65,38,49,13,27,50
    97
   76   65
  38  49  13  27

堆排序结果: 13,27,38,49,50,65,76,97
[Finished in 0.2s]
复制代码

归并排序

归并排序是 分治法(Divide and Conquer)的一个非常经典的应用。将大序列拆分成n个小序列,先使小序列有序,然后合并有序子序列,得到排序结果。
将两个有序序列合并成一个序列的方法叫做2路归并

算法描述与分析:

递归方法实现:
1.Divide: 把长度为n的序列分成长度为 n/2的子序列;
2.Conquer: 对每个子序列采用归并排序;
3.Combine:将排序好的两个子序列合并成最终的排序序列。

归并排序
归并排序动画

归并操作的工作原理如下:
第一步:申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列
第二步:设定两个指针最初位置分别为两个已经排序序列的起始位置
第三步:比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置
重复步骤3直到某一指针超出序列尾
将另一序列剩下的所有元素直接复制到合并序列尾。

复杂度:

时间复杂度:
O(nlogn): 将序列分成小序列需要logn步,每一步合并都需要对n个元素进行比较,时间复杂度为O(n),故一共为 o(nlogn)
空间复杂度:
O(n)

代码实现:
function mergeSort($arr){    
    $len = count($arr);
    if($len<=1) return $arr;

    $mid = intval($len/2);
    $left = array_slice($arr, 0, $mid);
    $right = array_slice($arr, $mid);

    $a = mergeSort($left);  //拆分排序子序列
    $b = mergeSort($right); //
    $arr = merge($a, $b);   //合并,拆分几次,就合并几次

    return $arr;
}
//2路合并
function merge($arrA, $arrB){
    $arrC = [];
    while ( count($arrA)>0 && count($arrB)>0 ) {
        $arrC[] = ($arrA[0] < $arrB[0]) ?  array_shift($arrA) : array_shift($arrB);
    }
    return array_merge($arrC, $arrA, $arrB);

}
$arr = [49, 38, 65, 97, 76, 13, 27, 50];
$arr = mergeSort($arr);
echo implode(',', $arr);
复制代码

输出结果:13,27,38,49,50,65,76,97[Finished in 0.2s]

插入排序

简介:

构建有序序列,对于未排序数据,在已排序序列从后向前扫描,找到合适的位置K并插入。 位置K之后的元素需要全部后移。

算法描述与分析:
  1. 取第一个元素构建有序序列;
  2. 取出下一个元素B,对有序序列从后向前扫描; 如果扫描到的元素大于B,则后移该元素;否则将B插入该元素后面;
  3. 重复第2步,直到遍历完所有数据。
插入排序
复杂度:

时间:O(n^2)
空间:O(1)

代码实现:
function insert_sort($arr){
    for( $i =1; $i<count($arr); $i++){
        $t = $arr[$i]; //待排元素
        for($j=$i-1; $j>=0; $j--){
            if( $arr[$j] > $t ){
                $arr[$j+1] = $arr[$j]; //大于待排元素,则后移
            }else{
                break;
            }
        }
        $arr[$j+1] = $t;
    }
    return $arr;
}
复制代码

二分插入排序

原理同上。 只是在第二步寻找合适位置时,使用二分查找法,快速定位插入位置K;然后将K后的元素后移;在K位置插入待排值

复杂度:

同插入排序。

代码实现:
function binary_insertion_sort($arr){
    $count = count($arr);
    for( $i=1; $i<$count; $i++){
        $tmp = $arr[$i];
        //查找需要替换的位置
        $left = 0;
        $right = $i-1;
        while( $left <= $right){
            $middle = intval( ($right+$left)/2 ); //向上加1
            if( $arr[$middle] > $tmp){
                $right = $middle-1;
            }else{
                $left = $middle+1;
            }
        }
        //位置后的元素后移
        for( $j; $j>=$left; $j--){
            $arr[$j+1] = $arr[$j];
        }
        $arr[$left] = $tmp;
    }
    echo implode(',', $arr)."\r\n";
}

复制代码

选择排序

从待排序列中选择最小(大)的元素,放在序列的起始位置;然后在从剩下的序列中继续选择最小(大)的元素,放在已排序序列的队尾。

选择排序
复杂度:

时间:O(n^2)
空间:O(1)

代码实现:

冒泡排序

两层循环,外层循环次数=元素个数;
内层循环挨个比较,当 A[j] 大于 A[j+1]时交换两个值;
当内循环结束时,最多有n-1次交换,会将最大值置于尾部;
当一次外循环无元素交换时,说明序列已有序,可提前结束外层循环。

复杂度

时间: o(n^2); 最优是已排序列进过一层循环发现无元素交换,直接退出程序,复杂度O(n)
空间:O(1)

鸡尾酒排序

冒泡排序的变种,不同的地方在于从低到高后从高到低。一次层循环内完成一大一小两个元素的冒泡。

鸡尾酒 - 双向冒泡排序
复杂度

同上

代码实现
function cocktail_sort($arr){
    $i=1;
    $start =0;
    $len = count($arr)-1;
    $end = 0;
    while($i>0){    //有交换元素时继续执行
        $i=0;
        for($j=$start; $j<$len-$end; $j++){
            if( $arr[$j] > $arr[$j+1]){
                $t = $arr[$j];
                $arr[$j] = $arr[$j+1];
                $arr[$j+1] = $t;
                $i=1;
            }
        }
        //逆向冒泡来一次
        for($j=$len-$end; $j>$start; $j--){
            if( $arr[$j] < $arr[$j-1]){
                $t = $arr[$j];
                $arr[$j] = $arr[$j-1];
                $arr[$j-1] = $t;
                $i=1;
            }
        }
        $end++;  //通过冒泡,尾部有序序列个数加一
        $start++; //头部有序序列个数加一
    }
}
复制代码

桶排序

将数组分别放到有限数量的桶中。每个桶在进行独立的排序。 分桶要求桶中的最大数据小于下一个桶的最小数据。

复杂度

时间:
空间: O(N+M)

计数排序

1.找出待排序列的最大值和最小值;使用数组C来标识 C[min] - c[max];
2.统计数组中每个值出现的次数,存入C[i]中;
3.反向填充目标数组:顺序遍历这个数组C,将下标解释成数据, 将该位置的值表示该数据的重复数量,得到排序好的数组。

  1. 当输入的元素是n 个0到k之间的整数时,它的运行时间是 O(n + k)。计数排序不是比较排序,排序的速度快于任何比较排序算法。
  2. 只能对整数进行排序
复杂度

时间:O(n)
空间:最大O(2n)

基数排序

将整数按位数切割成不同的数字,然后按每个位数分别比较。

位图排序

要求数据不重复,用bit位进行位图排序,能节省空间。

譬如: 每个学生答题一次,将已答题的学号记录在文件中。学号只出现一次,且学号连续。输入一个学号,查看是否答题。
解决: 将学号进行排序,在查找时使用二分查找。 因为学号不重复,所以可使用位图排序。

复杂度

位图排序不是比较排序,时间复杂度为 O(n)

相关阅读:


关注下面的标签,发现更多相似文章
评论