常见排序算法介绍

Question

常见排序列表

中文名称	英文名称	平均时间复杂度	最坏时间复杂度	最好时间复杂度	空间复杂度	稳定性
选择排序	Selection	n^2	n^2	n^2	1	不稳
冒泡排序	Bubble	n^2	n^2	n	1	稳
插入排序	Insertion	n^2	n^2	n	1	稳
堆排序	heap	nlog~2n	nlog~2n	nlog~2n	1	不稳
希尔排序	Shell	n^1.3	n^2	n	1	不稳
归并排序	Merger	nlog~2n	nlog~2n	nlog~2n	n	稳
快速排序	Quick	nlog~2n	n	nlog~2n	log~2n	不稳
桶排序	Bucket	n+k	n^2	n	n+k	稳
计数排序	Counting	n+k	n+k	n+k	n+k	稳
基数排序	Radix	n*k	n*k	n*k	n+k	稳

西风烈，
长空雁叫霜晨月。
霜晨月，
马蹄声碎，
喇叭声咽。
雄关漫道真如铁，
而今迈步从头越。
从头越，
苍山如海，
残阳如血。
---------------------------------
选泡插
快归堆希桶计基，
恩方恩老恩一三，
对恩加k恩乘k，
不稳稳稳不稳稳，
不稳不稳稳稳稳！

如何验证算法的正确性-对数器

1、肉眼观察
2、产生足够多的随机样本
3、用确定正确的算法计算样本结果
4、对比被验证算法的结果

一、选择排序（基本不用，不稳）

最简单，最没用

一遍一遍过滤数组，每次选择出最小（最大）的数

$list = [3,8,5,1,9,4,7];

for ($i=0;$i<count($list)-1;$i++){
  $index = $i;

  for($j=$i+1;$j<count($list);$j++){
    if($list[$index]>$list[$j]){
      $index = $j;
    }
  }
  $tmp = $list[$i];
  $list[$i] = $list[$index];
  $list[$index] = $tmp;
}

print_r($list);

二、冒泡排序（基本不用，太慢）

$list = [3,8,5,1,9,4,7];


for($i=0;$i<count($list)-1;$i++){
  for($j=0;$j<count($list)-$i-1;$j++){
    if($list[$j]>$list[$j+1]){
      $tmp = $list[$j];
      $list[$j] = $list[$j+1];
      $list[$j+1] = $tmp;
    }
  }
}

print_r($list);

三、插入排序（样本小且基本有序的时候效率比较高）

$list = [3,8,5,1,9,4,7];


for ($i=1;$i<count($list);$i++){
  for($j=$i;$j>0;$j--){
    if($list[$j] < $list[$j-1]){
      $tmp = $list[$j-1];
      $list[$j-1] = $list[$j];
      $list[$j] = $tmp;
    }else{
      //确保最好情况下的时间复杂度为O(n)
      break;
    }
  }
}

print_r($list);

四、希尔排序（1959 年改进的插入排序）

在间隔大的时候，移动次数比较少。在间隔小的时候，移动距离比较短。所以希尔排序会比普通的插入排序效率要高。

由于是跳着排，所以会不稳定

for($gap=4;$gap>=1;$gap/=2){
  for($i=$gap;$i<count($list);$i++){
    for ($j=$i;$j>$gap-1;$j-=$gap){
      if($list[$j]<$list[$j-$gap]){
        $tmp = $list[$j];
        $list[$j] = $list[$j-$gap];
        $list[$j-$gap] = $tmp;
      }
    }
  }
}

//间隔问题
//Knuth
h = 1;
h = 3*h+1

$h = 1;
while ($h<=count($list)/3){
  $h = $h*3+1;
}

for($gap=$h;$gap>=1;$gap=($gap-1)/3){
  for($i=$gap;$i<count($list);$i++){
    for ($j=$i;$j>$gap-1;$j-=$gap){
      if($list[$j]<$list[$j-$gap]){
        $tmp = $list[$j];
        $list[$j] = $list[$j-$gap];
        $list[$j-$gap] = $tmp;
      }
    }
  }
}

五、归并排序

java 和 python 对于对象的排序都是归并。

$list = [10,4,11,7,1,3,6,2];
print_r(mergerSort($list));
function mergerSort($list){
  if(count($list)>1){
    $mid = floor((count($list)-1)/2);
    $left_arr = array_slice($list,0,$mid+1);
    $right_arr = array_slice($list,$mid+1,count($list)-$mid-1);
    $left_arr = mergerSort($left_arr);
    $right_arr = mergerSort($right_arr);

    return merger($left_arr,$right_arr);
  }else{
    return $list;
  }
}


function merger($left_arr,$right_arr){
  $tmp = [];
  $i = 0;//左序列指针
  $j = 0;//有序列指针
  while($i<count($left_arr) && $j<count($right_arr)){
    if($left_arr[$i] <= $right_arr[$j]){
      $tmp[] = $left_arr[$i++];
    }else{
      $tmp[] = $right_arr[$j++];
    }
  }

  //防止左边还有剩余的
  while ($i<count($left_arr)){
    $tmp[] = $left_arr[$i++];
  }

  //防止右边还有剩余的
  while ($j<count($right_arr)){
    $tmp[] = $right_arr[$j++];
  }

  return $tmp;
}

六、快速排序

function quickSort($list){
  if(count($list)<=1){
    return $list;
  }


  $left = [];
  $right = [];
  $mid = floor((count($list)-1)/2);
  for($i=0;$i<count($list);$i++){
    if($i==$mid){
      continue;
    }

    if($list[$i] <= $list[$mid]){
      $left[] = $list[$i];
    }else{
      $right[] = $list[$i];
    }
  }

  $left = quickSort($left);
  $right = quickSort($right);

  return array_merge($left,[$list[$mid]],$right);
}

print_r(quickSort($list));