数据结构与算法整理总结---排序 2

冒泡排序、插⼊排序、选择排序这三种排序算法,它们的时间复杂度都是O(n2),⽐较⾼,适合⼩规模数据的排序。今天,我讲两种时间复杂度为O(nlogn)的排序算法,归并排序和快速排序。这两种排序算法适合⼤规模的数据排序,⽐冒泡排序、插⼊排序、选择排序这三种排序算法要更常⽤。

归并排序

归并排序的原理

归并排序的核⼼思想还是蛮简单的。如果要排序⼀个数组,我们先把数组从中间分成前后两部分,然后对前后两部分分别排序,再将排好序的两部分合并在⼀起,这样整个数组就都有序了。

数据结构与算法整理总结---排序2

数据结构与算法整理总结---排序2

归并排序使⽤的就是分治思想。分治,顾名思义,就是分⽽治之,将⼀个⼤问题分解成⼩的⼦问题来解决。⼩的⼦问题解决了,⼤问题也就解决了。

分治算法⼀般都是⽤递归来实现的。分治是⼀种解决问题的处理思想,递归是⼀种编程技巧,这两者并不冲突。

归并排序算法实现

class mergeSort{

    //需要排序的数组
    public $arr = [6,3,-1,9,39,43,23,11];

    function __construction()
    {
        $this->mergeSort(0,count($arr)-1);
    }
    publuc function mergeSort($min,$max){
        if($min<$max){
            $middle = ($min+$max)/2;
            $this->mergeSort($this->arr,0,$middle-1);
            $this->mergeSort($this->arr,$middle+1,$max);
            $this->merge($min,$middle,$max);
        }
    }
    //$left为左数组起始下标,$right为右数组结束下标
    public function merge($left,$middle,$right){
        $tempArr = $this->arr;
        $rightStart = $middle+1;
        $temp = $left;
        while($left<=$middle&&$rightStart<=$right){
            if($arr[$left]<$arr[$rightStart]){
                $tempArr[$temp++]=$this->arr[$left++]; 
            }else{
                $tempArr[$temp++]=$this->arr[$rightStart++];   
            }
        }
        while($rightStart<=$right){
            $tempArr[$temp++]=$this->arr[$rightStart++];
        }
        $this->arr = $tempArr;
    }
}

$sort = new mergeSort();
$arr = $sort->arr;

归并排序的性能分析

归并排序稳不稳定关键要看merge()函数,也就是两个有序⼦数组合并成⼀个有序数组的那部分代码。
在合并的过程中,如果A[p…q]和A[q+1…r]之间有值相同的元素,那我们可以像伪代码中那样,先把A[p…q]中的元素放⼊tmp 数组。这样就保证了值相同的元素,在合并前后的先后顺序不变。所以,归并排序是⼀个稳定的排序算法。
其时间复杂度是⾮常稳定的,不管是最好情况、最坏情况,还是平均情况,时间复杂度都是O(nlogn)。
归并排序的合并函数,在合并两个有序数组为⼀个有序数组时,需要借助额外的存储空间。空间复杂度为O(n)。

快速排序

快速排序的原理

快排利⽤的也是分治思想。乍看起来,它有点像归并排序,但是思路其实完全不⼀样。

快排的思想是这样的:如果要排序数组中下标从p到r之间的⼀组数据,我们选择p到r之间的任意⼀个数据作为pivot(分区点)。

我们遍历p到r之间的数据,将⼩于pivot的放到左边,将⼤于pivot的放到右边,将pivot放到中间。经过这⼀步骤之后,数组p到r之间的数据就被分成了三个部分,前⾯p到q-1之间都是⼩于pivot的,中间是pivot,后⾯的q+1到r之间是⼤于pivot的。

数据结构与算法整理总结---排序 2

根据分治、递归的处理思想,我们可以⽤递归排序下标从p到q-1之间的数据和下标从q+1到r之间的数据,直到区间缩⼩为1,就说明所有的数据都有序了。

归并排序中有⼀个merge()合并函数,我们这⾥有⼀个partition()分区函数。partition()分区函数实际上我们前⾯已经讲过了,就是随机选择⼀个元素作为pivot(⼀般情况下,可以选择p到r区间的最后⼀个元素),然后对A[p…r]分区,函数返回pivot的下标。

如果我们不考虑空间消耗的话,partition()分区函数可以写得⾮常简单。我们申请两个临时数组X和Y,遍历A[p…r],将⼩于pivot的元素都拷⻉到临时数组X,将⼤于pivot的元素都拷⻉到临时数组Y,最后再将数组X和数组Y中数据顺序拷⻉到A[p…r]。

数据结构与算法整理总结---排序 2

快速排序算法实现

class quickSort{

    public $arr = [4,3,8,65,43,-1,21,55];

    __construction(){
        $this->quickSort($this->arr,0,count($arr)-1);
    }
    function quickSort($arr,$begin,$end){
        if($begin<$end){
            //以第一个数为基准
            $first = $arr[$begin];
            $i = $begin;
            $j = $end;
            while($i<$j){
                while($i<$j&&$arr[$j]<$first){
                    $j--;
                    $arr[$i]=$arr[$j];
                }
                while($i<$j&&$arr[$i]>=$first){
                    $i++;
                    $arr[$j]=$arr[$i];
                }
                $arr[$i] = $first;
            }
            $this->quickSort($arr,$begin,$i-1);
            $this->quickSort($arr,$i+1,$end);
        }else{
            return $arr;
        }
    }
}
$quickSort = new quickSort();
$arr = $quickSort->arr;

快速排序的性能分析

快排是⼀种原地、不稳定的排序算法。快排也是⽤递归来实现的。对于递归代码的时间复杂度。如果每次分区操作,都能正好把数组分成⼤⼩接近相等的两个⼩区间,那快排的时间复杂度递推求解公式跟归并是相同的。所以,快排的时间复杂度也是 O(nlogn)。

归并排序与快速排序比较

数据结构与算法整理总结---排序 2

本作品采用《CC 协议》,转载必须注明作者和本文链接
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

请勿发布不友善或者负能量的内容。与人为善,比聪明更重要!