摘要：說明本文是對(duì)個(gè)人學(xué)習(xí)冒泡快速選擇和插入排序的小總結(jié)。不管咋樣，個(gè)人學(xué)習(xí)時(shí)有關(guān)索引就用到快速排序，索引也是以數(shù)據(jù)結(jié)構(gòu)保存的存儲(chǔ)引擎，所以基本功還是很重要的嘛。

說明：本文是對(duì)個(gè)人學(xué)習(xí)冒泡、快速、選擇和插入排序的小總結(jié)。面試經(jīng)常問這些東西，雖然不知道為啥老愛問這些，該問的又不問。不管咋樣，個(gè)人學(xué)習(xí)MySQL時(shí)有關(guān)索引就用到快速排序，索引也是以B+Tree數(shù)據(jù)結(jié)構(gòu)保存的(Innodb存儲(chǔ)引擎)，所以基本功還是很重要的嘛。

個(gè)人實(shí)驗(yàn)發(fā)現(xiàn)，快速排序在這四個(gè)排序當(dāng)中似乎是最快的，看下圖比較直觀：

看下代碼吧：

arrayQuickSort($left);
        $right = $this->arrayQuickSort($right);

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

}

$arr       = [5, 4, 5, 3, 8, 10, 3, 2, 4, 7];
$arr2      = array_rand(range(1, 1000), 500);
shuffle($arr2);

$quickSort = new QuickSort();

$time1     = microtime(true);
//$quickArr  = $quickSort->arrayQuickSort($arr);
$quickArr  = $quickSort->arrayQuickSort($arr2);//11.8780136108ms
$time2     = microtime(true);

//var_dump($quickArr);
echo (($time2 - $time1)*1000)."ms".PHP_EOL;

實(shí)驗(yàn)快速排序，排序隨機(jī)的500個(gè)數(shù)只要11ms左右，還挺快。

冒泡排序效率就比較差了，看圖比較直觀它的原理：

看代碼吧：

 $data[$j+1]){
                    $this->swap($data[$j], $data[$j+1]);
                }
            }
        }

        return $data;
    }

    /**
     * 字符串排序也和數(shù)組一樣,字符串?dāng)?shù)組形式訪問字符
     * @param string|string $str
     * @return string
     */
    public function stringBubbleSort(string $str)
    {
        $count = strlen($str);
        for($i=0; $i<$count; $i++){
            for($j=0; $j<$count-1-$i; $j++){
                if($str[$j] > $str[$j+1]){
                    $this->swap($str[$j], $str[$j+1]);
                }
            }
        }

        return $str;
    }

    /**
     * 交換變量值
     * @param $var1
     * @param $var2
     */
    public function swap(&$var1, &$var2)
    {
        $tmp  = $var1;
        $var1 = $var2;
        $var2 = $tmp;
    }
}

$arr   = [5, 4, 5, 3, 8, 10, 3, 2, 4, 7];
$str   = "SegmentFault";
$arr2  = array_rand(range(1, 1000), 500);
shuffle($arr2);

$sort  = new BubbleSort();

$time1 = microtime(true);
//$bubbleArr = $sort->arrayBubbleSort($arr);
$bubbleArr = $sort->arrayBubbleSort($arr2);//316.018104553ms
$time2 = microtime(true);

//var_dump($bubbleArr);
echo (($time2 - $time1)*1000)."ms".PHP_EOL;

實(shí)驗(yàn)冒泡排序，排序隨機(jī)的500個(gè)數(shù)需要316ms左右，慢的不行。

插入排序個(gè)人覺得就像是玩撲克，牌桌上n張牌，一張張抓過來，然后新牌根據(jù)手上的m張牌依次比較，找到對(duì)應(yīng)位置。看圖比較直觀：

看代碼吧：

0; $j--){
                if($data[$j] > $data[$j-1]){
                    break;
                }
                $this->swap($data[$j-1], $data[$j]);
            }
        }

        return $data;
    }

    /**
     * 交換變量值
     * @param $var1
     * @param $var2
     */
    public function swap(&$var1, &$var2)
    {
        $tmp  = $var1;
        $var1 = $var2;
        $var2 = $tmp;
    }

}

$arr       = [5, 4, 5, 3, 8, 10, 3, 2, 4, 7];
$arr2      = array_rand(range(1, 1000), 500);
shuffle($arr2);
$insert    = new InsertSort();

$time1     = microtime(true);
//$insertArr = $insert->arrayInsertSort($arr);
$insertArr = $insert->arrayInsertSort($arr2);//315.321922302ms
$time2     = microtime(true);

//var_dump($insertArr);
echo (($time2 - $time1)*1000)."ms".PHP_EOL;



include __DIR__ . "/autoload.php";

function inverst_sort(string $str): string {
    for ($i = 1; $i < strlen($str); $i++) {
        $key = $str[$i];
        $j   = $i - 1;
        
        while ($j > 0 && $str[$j] > $key) {
            $str[$j+1] = $str[$j];
            $j         = $j -1;
        }
        
        $str[$j+1] = $key;
    }
    
    return $str;
}

dump(inverst_sort("abdghhjc"));

實(shí)驗(yàn)插入排序，排序隨機(jī)的500個(gè)數(shù)需要315ms左右，和冒泡排序差不多速度。

選擇排序速度還行，看圖：

看代碼吧：

 $data[$j]){
                    $min = $j;
                }
            }
            
            if($min != $i){
                $this->swap($data[$min], $data[$i]);
            }
        }

        return $data;
    }

    /**
     * 交換變量值
     * @param $var1
     * @param $var2
     */
    public function swap(&$var1, &$var2)
    {
        $tmp  = $var1;
        $var1 = $var2;
        $var2 = $tmp;
    }

}

$arr2      = array_rand(range(1, 1000), 500);
shuffle($arr2);
$arr       = [5, 4, 5, 3, 8, 10, 3, 2, 4, 7];

$select    = new SelectSort();

$time1     = microtime(true);
//$selectArr = $select->arraySelectSort($arr);
$selectArr = $select->arraySelectSort($arr2);//44.0230369568ms
$time2 = microtime(true);

//var_dump($selectArr);
echo (($time2 - $time1)*1000)."ms".PHP_EOL;

實(shí)驗(yàn)選擇排序，排序隨機(jī)的500個(gè)數(shù)需要44ms左右，速度還行。

總結(jié)：排序和查找是永恒主題。扎實(shí)下基本功，會(huì)繼續(xù)學(xué)習(xí)相關(guān)排序和查找算法，到時(shí)見。

歡迎關(guān)注Laravel-China。

RightCapital招聘Laravel DevOps