问题：怎么理解排序算法的不稳定性？
简单地说就是所有相等的数经过某种排序方法后，仍能保持它们在排序之前的相对次序，我们就说这种排序方法是稳定的。反之，就是非稳定的。
我们现在所做的拿数据简单的做测试对破坏顺序当然没什么关系。但是如果是那结构体来排序呢？比如一个结构体里面包含一个人的学号和分数，要求在分数相等的情况下再按照学号排序，这个时候顺序就有关系了。
1、冒泡排序
原理：临近的两个数字两两比较，按照从大到小或者从小到大的顺序排序，这样一次遍历下来，最大或者最小的数字就被选择了出来，再依次遍历后面的数字，直到倒数第二位结束。
时间复杂度：平均情况：O(n^2) 最好情况（n）
空间复杂度：O(1)
稳定性：稳定
代码:
<?php
$arr = [12,12,23,3,4,4,43,4,345,43,54,35,46,567,34];
$len = count($arr);
for ($i=0; $i < $len; $i++) {
for ($j=0; $j < $len - 1 -$i; $j++) {
if($arr[$j] > $arr[$j+1]){
$tmp = $arr[$j];
$arr[$j] = $arr[$j+1];
$arr[$j+1] = $tmp;
}
}
}
print_r($arr);
?>
2、选择排序
原理：设排序的记录有n个，i遍历 0 - n 和 i后面的记录做比较，每一次遍历能找出最大或者最小记录，执行n-1次后，完成排序
时间复杂度：平均情况：O(n^2) 最好情况：O(n)
空间复杂度：O(1)
稳定性：不稳定
代码：
<?php
function selectionSort($arr)
{
$len = count($arr);
// var_dump($len);
for( $i = 0;$i < $len; $i++){
//在[i,n)区间内去找最小数
$minIndex = $i;
for ($j=$i+1; $j<$len; $j++) {
if($arr[$j] < $arr[$minIndex]){
$minIndex = $j;
}
}
swapItem($arr[$minIndex],$arr[$i]);
}
return $arr;
}
function swapItem(& $a,& $b){
$tmp = 0;
$tmp = $a;
$a = $b;
$b = $tmp;
}
$arr = [10,9,8,7,6,5,4,3,2,1];
$arr = selectionSort($arr);
print_r($arr);
?>
3、插入排序
原理：将记录插入到一个已经排好序的序列中，形成一个新的有序数列。即先将序列的第一位看成一个有序序列，然后从第二个序列开始逐个插入形成新的有序序列，直到遍历完整个序列。性能上比冒泡和简单选择排序更好。
时间复杂度：平均情况：O(n^2) 最好情况：O(n)
空间复杂度：O(1)
稳定性：稳定
代码：
<?php
$arr = [12,34,4,3,5,2,3,44];
$len = count($arr);
for($i = 0; $i < $len;$i++){
//新取的记录和有序序列的最后一位比较大小，所以$j = $i-1
$newitem = $arr[$i];
$j = $i -1;//$arr[$j]代表有序序列的最后一个记录
//如何有序序列长度大于1且新插入的要比序列的最后一个记录小，则要进入循环，找到合适的位置
while ($j > -1 && $arr[$j] > $newitem) {
$arr[$j+1] = $arr[$j];
$j = $j - 1;
}
$arr[$j+1] = $newitem;
}
print_r($arr);
?>
算法2：
<?php
$arr = [12,34,4,3,5,2,3,44,2,2,33,0,1];
$len = count($arr);
for($i = 1;$i<$len;$i++){
for($j = $i;$j-1>=0&&$arr[$j]<$arr[$j-1];$j--){
$tmp = $arr[$j-1];
$arr[$j-1] = $arr[$j];
$arr[$j] = $tmp;
}
}
print_r($arr);
?>
4、快速排序
原理：每一趟排序将原序列分成两个独立的部分，并且其中一个部分的所有数据要比另一个部分的所有数据要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
时间复杂度：平均情况：O(nlog2n) 最好情况：O(nlog2n)，最坏情况（n^2）
空间复杂度：O（nlog2n）
代码：
<?php
$arr = [12,34,4,3,5,2,3,44];
function quickSort($arr){
$len = count($arr);
if($len <=1){
return $arr;
}
$base_num = $arr[0];//选择一个标尺 选择第一个元素
$left_array = array();
$right_array = array();
for($i = 1;$i < $len;$i++){
if($arr[$i]>$base_num){
$right_array[] = $arr[$i];
}else{
$left_array[] = $arr[$i];
}
}
$left_array = quickSort($left_array);
$right_array = quickSort($right_array);
return array_merge($left_array,array($base_num),$right_array);
}
$newArray = quickSort($arr);
print_r($newArray);
?>
5、希尔排序
原理：希尔排序是插入排序的改进版，将原序列按下标的一定增量分组，每组元素分别进行插入排序。然后增量减小，排序后的序列在按减小后的增量分组排序，指导增量减小为1，整个序列恰好被分成一组，算法结束。
时间复杂度：平均情况：O(n√n) 最好情况：O（nlog2n） 最坏情况：O（n2）
空间复杂度：O(1)
代码：
<?php
$arr = [12,34,4,3,5,2,3,44,33,2];
function shellSort($arr){
$len = count($arr);
for($step = $len/2;$step>0;$step /=2){
//从第step个元素，逐个对其所在组进行直接插入排序操作
for($i = $step; $i<$len;$i++){
for($j = $i;$j>=$step && $arr[$j]<$arr[$j-$step];$j-=$step){
$tmp = $arr[$j-$step];
$arr[$j-$step] = $arr[$j];
$arr[$j] = $tmp;
}
}
}
print_r($arr);
}
shellSort($arr);
?>
网友评论