排序算法的稳定性

比如说学校统计学生成绩，学生是按学生名字拼音的字典顺序来进行排序，
现在的话统计按学生分数来进行排序，排序前后，若学生拼音的字典顺序没有改变，则这个排序是稳定的，反之，并不稳定。

//c++写法
bool operator<(const Student& otherStudent){
retutn score !=otherStudent.score ?
            score > otherStudent.score : 
            name < otherStudent.name

稳定的排序算法

插入排序

//php写法
function insertSort(&$arr){
    for($i = 1; $i<count($arr); $i++){
        $temp = $arr[$i];
        for($j = $i-1; $j >=0; $j--){
            if($temp < $arr[$j]){
                $arr[$j+1] = $arr[$j];
                $arr[$j] = $temp;
            }
        }
    }
} 

归并排序

//php写法
function MergeSort(array &$arr){
    $start = 0;
    $end = count($arr) - 1;
    MSort($arr,$start,$end);
}

function MSort(array &$arr,$start,$end){ 
    if($start < $end){
        $mid = floor(($start + $end) /2);
        MSort($arr,$start,$mid);
        MSort($arr,$mid+1,$end);
        Merge($arr,$start,$mid,$end);
    }
    
}
//归并操作
function Merge(array &$arr,$start,$mid,$end){
    $i = $start;
    $j=$mid + 1;
    $k = $start;
    $temparr = array();

    while($i!=$mid+1 && $j!=$end+1)
    {
       if($arr[$i] >= $arr[$j]){
           $temparr[$k++] = $arr[$j++];
       }
       else{
           $temparr[$k++] = $arr[$i++];
       }
    }

    //将第一个子序列的剩余部分添加到已经排好序的 $temparr 数组中
    while($i != $mid+1){
        $temparr[$k++] = $arr[$i++];
    }
    //将第二个子序列的剩余部分添加到已经排好序的 $temparr 数组中
    while($j != $end+1){
        $temparr[$k++] = $arr[$j++];
    }
    for($i=$start; $i<=$end; $i++){
        $arr[$i] = $temparr[$i];
    }
}

不稳定的排序算法

快速排序
例如待排序数组
$a = [1,2,2,3,4,5,6];
若选择第一2，(2[1])为比较的元素，把<= 2[1]的放在左边，那么第二个2和第一个2顺序和原数组顺序不对了
若选择第二个2，（2[2]）为比较的元素，把>=2[2]的放在右边，那么第一个2，和第二个2顺序和原数组顺眼不对了，所以是不稳定的。

//php写法
function kuaisort($arr){
    if(count($arr)<=1){
        return $arr;
    }
    $key = $arr[0];
    $left = array();
    $right = array();
    for($i = 1; $i <count($arr); $i++){
        if($key >= $arr[$i]){
            array_push($left,$arr[$i]);
        }else{
            array_push($right,$arr[$i]);
        }
    }
    $left = kuaisort($left);
    $right = kuaisort($right);
    return array_merge($left,array($key),$right);
}