資訊專欄INFORMATION COLUMN
摘要：總結(jié)比較排序算法都是空間復(fù)雜度為的原地排序算法，其中冒泡排序和插入排序兩兩比較不會(huì)交換相等的記錄，所以這兩種排序都是穩(wěn)定排序，而選擇排序只是記錄最小值最后進(jìn)行交換，所以會(huì)破壞相對(duì)順序，選擇排序不是穩(wěn)定算法。
冒泡排序
兩兩比較相鄰記錄的關(guān)鍵字，如果反序則交換，大的數(shù)字往下沉，一直到最大的出現(xiàn)在數(shù)組最后
function swap(&$x, &$y) {
$temp = $x;
$x = $y;
$y = $temp;
}
function bubble_sort(&$arr) {//php的陣列視為基本型別，所以必須用傳參考才能修改原陣列
for ($i = 0; $i < count($arr) - 1; $i++) { //控制循環(huán)的次數(shù)
for ($j = 0; $j < count($arr) - 1 - $i; $j++) {
if ($arr[$j] > $arr[$j + 1]) {
swap($arr[$j], $arr[$j + 1]);
}
}
}
}
改進(jìn)的冒泡排序
第一層循環(huán)不變，第二層循環(huán)冒泡變成從后往前，這樣做可以在冒泡的過(guò)程中盡可能的將小的數(shù)據(jù)向前冒。
function bubble_sort(&$arr)
{
for ($i=0;$i$i;$j--) {
if ($arr[$j-1]>$arr[j]) {
swap($arr[j-1],$arr[j]);
}
}
}
}
插入排序
將一個(gè)記錄插入到已經(jīng)排好序的有序表中
function insertion_sort(&$arr)
{//php的陣列視為基本型別，所以必須用傳參考才能修改原陣列
for ($i = 1; $i < count($arr); $i++) {
$temp = $arr[$i];
for ($j = $i - 1; $j >= 0 && $arr[$j] > $temp; $j--) {
$arr[$j + 1] = $arr[$j];
}
$arr[$j + 1] = $temp;
}
}
選擇排序
通過(guò)n-i次關(guān)鍵字的比較，找出n-i+1個(gè)記錄中最小的記錄，并和第i個(gè)記錄交換
function select_sort(&$arr)
{
for ($i = 0;$i < count($arr);$i++) {
$min = $i;
for ($j = count($arr)-1;$j > $i;$j--) {
if ($arr[$j] < $arr[$min]) {
$min = $j;
}
}
if ($min != $i) {
swap($arr[$i],$arr[$min]);
}
}
}
為什么插入排序比冒泡排序好
兩個(gè)算法的時(shí)間復(fù)雜度都是O（n^2），但是冒泡排序每次交換記錄時(shí)都要進(jìn)行三次賦值操作，而插入排序因?yàn)橛猩诒兞?，所以只有一步賦值操作，減少了排序時(shí)間。
總結(jié)比較排序算法都是空間復(fù)雜度為O（1）的原地排序算法，其中冒泡排序和插入排序兩兩比較不會(huì)交換相等的記錄，所以這兩種排序都是穩(wěn)定排序，而選擇排序只是記錄最小值最后進(jìn)行交換，所以會(huì)破壞相對(duì)順序，選擇排序不是穩(wěn)定算法。
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/29549.html
摘要：良好的排序算法具有進(jìn)行最少的比較和交換的特征。冒泡排序是一個(gè)基于比較的排序算法，被認(rèn)為是效率最低的排序算法之一。現(xiàn)在讓我們使用實(shí)現(xiàn)冒泡排序算法。插入排序到目前為止，我們已經(jīng)看到了兩種基于比較的排序算法。 預(yù)警 本文適合對(duì)于排序算法不太了解的新手同學(xué)觀看，大佬直接忽略即可。因?yàn)榭紤]到連貫性，所以篇幅較長(zhǎng)。老鐵們看完需要大概一個(gè)小時(shí)，但是從入門(mén)到完全理解可能需要10個(gè)小時(shí)(哈哈哈，以我自己...
摘要：在算法中，比快速排序還快的，無(wú)疑是基數(shù)排序，粗略看了一下算法，可能是基礎(chǔ)排序中的桶排序。桶排序是穩(wěn)定的桶排序是常見(jiàn)排序里最快的一種，比快排還要快大多數(shù)情況下桶排序非常快，但是同時(shí)也非常耗空間以空間換時(shí)間 ext/standard/php_array.h https://github.com/php/php-src/blob/master/ext/standard/php_array....
摘要：而在證明算法是正確的基礎(chǔ)上，第二步就是分析算法的時(shí)間復(fù)雜度。算法的時(shí)間復(fù)雜度反映了程序執(zhí)行時(shí)間隨輸入規(guī)模增長(zhǎng)而增長(zhǎng)的量級(jí)，在很大程度上能很好反映出算法的優(yōu)劣與否。 showImg(https://segmentfault.com/img/remote/1460000016451712?w=800&h=341); 前言 雖然工作中，你覺(jué)得自己并沒(méi)有涉及到算法這方面的東西，但是算法是程序的...
摘要：本文將介紹快速排序計(jì)數(shù)排序梳排序堆排序歸并排序希爾排序選擇排序插入排序地精排序聯(lián)合冒泡排序雞尾酒排序冒泡排序奇偶排序使用標(biāo)志的冒泡排序種排序算法的實(shí)現(xiàn)。是一種不穩(wěn)定的排序算法。 本文將介紹快速排序、計(jì)數(shù)排序、梳排序、堆排序、歸并排序、希爾排序、選擇排序、插入排序、地精排序、聯(lián)合冒泡排序、雞尾酒排序、冒泡排序、奇偶排序、使用標(biāo)志的冒泡排序14種排序算法的實(shí)現(xiàn)。本文是由于閱讀了文章《測(cè)試評(píng)...
摘要：一冒泡排序原理對(duì)一組數(shù)據(jù)，比較相鄰數(shù)據(jù)的大小，將值小數(shù)據(jù)在前面，值大的數(shù)據(jù)放在后面。通過(guò)以上五輪排序，若干次比較，我們有理由推斷出一個(gè)結(jié)論對(duì)于一個(gè)長(zhǎng)度為的數(shù)組，我們需要排序輪，每輪要比較次。 一、冒泡排序 原理：對(duì)一組數(shù)據(jù)，比較相鄰數(shù)據(jù)的大小，將值小數(shù)據(jù)在前面，值大的數(shù)據(jù)放在后面。 （以下都是升序排列，即從小到大排列） 舉例說(shuō)明： $arr = array(6, 3, 8,...
閱讀 1286·2021-10-11 10:57
閱讀 2059·2021-09-02 15:15
閱讀 1617·2019-08-30 15:56
閱讀 1210·2019-08-30 15:55
閱讀 1167·2019-08-30 15:44
閱讀 992·2019-08-29 12:20
閱讀 1338·2019-08-29 11:12
閱讀 1079·2019-08-28 18:29
