之前读 刘未鹏 的《暗时间》里面就有这样一个观点 "互联网技术日新月异,程序员要学的技术变化的很快,但真正不变的东西其实很少,比如数据结构和算法",
原文请访问 番茄技术小站
磨刀不误砍柴工
先做一些,准备工作,比如生成排序算法需要的随机数组,数组元素交换,测试排序算法的性能,生成基本有序的数据等函数
为什么需要学习 O(n*n) 复杂度的算法
<?php
/**
* 排序算法帮助函数
* @author junqi1 <2018-1-7>
*/
/**
* [generateRandomArray 生成有n个元素的随机数组,每个元素的随机范围为[rangeL, rangeR]]
* @param [type] $n [description]
* @param [type] $rangeL [description]
* @param [type] $rangeR [description]
* @return [type] [description]
*/
function generateRandomArray($n, $rangeL, $rangeR) {
assert($rangeL < $rangeR);
$arr = array();
for ($i = 0; $i < $n; $i++){
$arr[$i] = rand($rangeL, $rangeR);
}
return $arr;
}
/**
* [generateNearlyOrderedArray 产生n个几乎有序的数组, ]
* @param [type] $n [description]
* @param [type] $swapTimes [顺序数组中调换的个数]
* @return [type] [description]
*/
function generateNearlyOrderedArray($n, $swapTimes){
$arr = array();
for ($i=0; $i < $n; $i++) {
$arr[$i] = $i;
}
//调换数组
for ($i=0; $i < $swapTimes; $i++) {
$swap1 = rand(0, $n-1);
$swap2 = rand(0, $n-1);
swap($arr, $swap1, $swap2);
}
return $arr;
}
//数组元素交换
function swap(&$arr, $i, $j){
$tmp = $arr[$i];
$arr[$i] = $arr[$j];
$arr[$j] = $tmp;
}
function isSort($arr, $n){
for ($i=0; $i < $n-1; $i++) {
if ($arr[$i] > $arr[$i+1]) {
return false;
}
}
return true;
}
//测试排序算法的性能
function testSort($sortName, $sorFunction, $arr, $n){
$t1 = microtime(true);
$sorFunction($arr, $n);
$t2 = microtime(true);
assert(isSort($arr, $n), "排序算法错误!\n");
echo "{$sortName}运行的时间为:". (($t2-$t1)).'s'."\n";
}
基础
编码简单,易于实现,是一些简单情景的自选
在一些特殊的情况下,简单的排序算法更有效(比如,基本有序的情况下,插入排序的效率极高)
简单的排序算法思想衍生出复杂的排序算法
作为子过程, 改进更复杂的排序算法.
选择排序算法(selection sort)
定义 (wiki)
选择排序(Selection sort)是一种简单直观的排序算法.它的工作原理如下.首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾.以此类推,直到所有元素均排序完毕.
代码实现
插入排序(insertionSort)
<?php
require('../Library/SortTestHelper.php');
/**
* [selectSort 选择排序]
* @param [type] &$arr [description]
* @param [type] $n [description]
* @return [type] [description]
*/
function selectSort(&$arr, $n){
for($i = 0; $i < $n; $i++){
$minIndex = $i;
for ($j=$i + 1; $j < $n; $j++) {
if ($arr[$j] < $arr[$minIndex]) {
swap($arr, $minIndex, $j);
}
}
}
}
//main
// $n = 100;
// $arr = generateRandomArray($n, 0, $n);
// testSort("selectSort", "selectSort", $arr, $n);
现实生活中,整理扑克牌扑克牌其实就是插入排序的应用
定义
插入排序(英语:Insertion Sort)是一种简单直观的排序算法.它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入.在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间.
基本代码实现
运行时间
/**
* [insertSort 插入排序]
* @param [type] &$arr [description]
* @param [type] $n [description]
* @return [type] [description]
*/
function insertSort( & $arr, $n) {
//从第2个元素开始,找寻它的位置,所以从i=1开始
for ($i = 1; $i < $n; $i++) {
//从第1个元素到第i个元素之间,寻找arr[i]的位置, j>0表示,最终比较的是第1个元素和第0个元素
//第一种写法
// for ($j=i; $j > 0 ; $j--) {
// if ($arr[j-1] > arr[j]) {
// swap($arr, $j-1, $j);
// }else{
// break;
// }
// }
//第二种写法:更简洁
for ($j = $i; $j > 0 && $arr[$j - 1] > $arr[$j]; $j--) {
swap($arr, $j - 1, $j);
}
}
}
结果对比
//main
$n = 10000;
// $arr = generateRandomArray($n, 0, $n);
$arr = generateNearlyOrderedArray($n, 100);
$copy_arr = $arr;
testSort("selectSort", "selectSort", $arr, $n);
testSort("insertSortSeo", "insertSort", $copy_arr, $n);
selectSort运行的时间为:3.898992061615s
insertSort运行的时间为:4.036700963974s
结果分析
按常理来说,插入排序应该比选择排序时间短,但是实际却长,这主要是因为插入排序中频繁进行 swap 操作造成的,而一次 swap,需要进行三次交换,那么有没有优化的方法呢?有的!
优化插入排序(insertSortSeo)
代码实现
运行时间
/**
* [insertSortSeo 优化的插入排序算法:swap是进行三次交换,将这三次交换改变成一次赋值]
* @param [type] &$arr [description]
* @param [type] $n [description]
* @return [type] [description]
*/
function insertSortSeo( & $arr, $n) {
for ($i = 1; $i < $n; $i++) {
//采用复制的方式
$tmp = $arr[$i];
for ($j = $i; $j > 0 && $tmp < $arr[$j - 1]; $j--) {
$arr[$j] = $arr[$j - 1];
}
$arr[$j] = $tmp;
}
}
结果对比
//main
$n = 10000;
$arr = generateRandomArray($n, 0, $n);
// $arr = generateNearlyOrderedArray($n, 100);
$copy_arr = $arr;
testSort("selectSort", "selectSort", $arr, $n);
testSort("insertSortSeo", "insertSortSeo", $copy_arr, $n);
selectSort运行的时间为:4.1174781322479s
insertSortSeo运行的时间为:1.817638874054s
插入排序的实际应用
插入排序在需要排序的数据基本有序的情况下,非常快,甚至比 O(n*logN) 时间复杂度的算法还快,比如对服务器日志记录进行排序时, 日志数据基本上都是有序的,只有少数任务执行时间较长,造成数据顺序不一致,这中情况下,非常适合插入排序算法.
测试比较
首先生成基本有序的数据:
运行时间
/**
* [generateNearlyOrderedArray 产生n个几乎有序的数组, ]
* @param [type] $n [description]
* @param [type] $swapTimes [顺序数组中调换的个数]
* @return [type] [description]
*/
function generateNearlyOrderedArray($n, $swapTimes) {
$arr = array();
for ($i = 0; $i < $n; $i++) {
$arr[$i] = $i;
}
//调换数组
for ($i = 0; $i < $swapTimes; $i++) {
$swap1 = rand(0, $n - 1);
$swap2 = rand(0, $n - 1);
swap($arr, $swap1, $swap2);
}
return $arr;
}
结果对比
//main
$n = 10000;
// $arr = generateRandomArray($n, 0, $n);
$arr = generateNearlyOrderedArray($n, 100);
$copy_arr = $arr;
testSort("selectSort", "selectSort", $arr, $n);
testSort("insertSortSeo", "insertSortSeo", $copy_arr, $n);
selectSort运行的时间为:2.0646297931671s
insertSortSeo运行的时间为:0.040951013565063s
插入算法的延伸
希尔排序算法就是插入算法的延伸.
来源: https://juejin.im/post/5a51ea68f265da3e2e6251df