資訊專(zhuān)欄INFORMATION COLUMN
摘要：將大的先放在后面，再下一次可以把相同大的放在上一次的之前，順序改變。
之前介紹的排序算法：
計(jì)數(shù)排序是一個(gè)非基于比較的排序算法，該算法于1954年由
Harold H. Seward提出它的優(yōu)勢(shì)在于在對(duì)一定范圍內(nèi)的整數(shù)排序時(shí)，它的復(fù)雜度為Ο(n+k)（其中k是整數(shù)的范圍），快于任何比較排序算法
當(dāng)然這是一種犧牲空間換取時(shí)間的做法，而且當(dāng)
O(k)>O(n*log(n))的時(shí)候其效率反而不如基于比較的排序（基于比較的排序的時(shí)間復(fù)雜度在理論上的下限是O(n*log(n)), 如歸并排序，堆排序）
O(Max(N, Range))O(range)不適合排序了基本思路：遍歷數(shù)組a，a[i]下標(biāo)對(duì)應(yīng)的count[a[i]]++
count數(shù)組大小
看樣子范圍應(yīng)該是0到a數(shù)組中最大的數(shù)？
實(shí)則不是，如果數(shù)字是
1000， 1001， 1100
則從0到1100 ，浪費(fèi)了很多空間
所以我們定義一個(gè)映射數(shù)組，所有的數(shù)字都是相對(duì)最小的數(shù)字的大小
1000， 1001， 1100
映射數(shù)組數(shù)字大小：a[i] - min
0， 1， 100
將它設(shè)置為count數(shù)組對(duì)應(yīng)下標(biāo)
這里主要是尋找數(shù)組下標(biāo)與數(shù)組值之間的對(duì)應(yīng)關(guān)系
count[i]，拷貝的數(shù)字是i + min進(jìn)入原數(shù)組（返回映射）
count[i] 的數(shù)值表示，數(shù)字i需要拷貝到原數(shù)組的次數(shù)
所以count數(shù)組初始值都為0
拷貝一次count[i]–
//計(jì)數(shù)排序void CountSort(int* a, int n){ int max = a[0]; int min = a[0]; int i = 0; //取出最大和最小值找范圍 for (i = 0; i < n; i++) { if (a[i] > max) { max = a[i]; } if (a[i] < min) { min = a[i]; } } //數(shù)組數(shù)字所在范圍 int range = max - min + 1; //開(kāi)辟內(nèi)存空間，并且初始化為0 int* tmp = (int*)calloc(range, sizeof(int)); //malloc操作 //int* tmp = (int*)mallco(sizeof(int) * range); //memset(tmp, 0, sizeof(int) * range); if (!tmp) { printf("calloc fail/n"); exit(-1); } int* count = tmp; //計(jì)數(shù) for (i = 0; i < n; i++) { count[a[i] - min]++; } int j = 0; //計(jì)數(shù)放回 for (i = 0; j < range; j++) { while (count[j]--) { a[i++] = j + min; } } free(tmp); tmp = NULL;}相同數(shù)值，在排序過(guò)后相對(duì)位置不發(fā)生改變
直接插入排序 穩(wěn)定
因?yàn)槭前错樞颍瑥那巴螅?、2、3……個(gè)數(shù)依次插入排成有序
希爾排序 不穩(wěn)定
因?yàn)槭且詘為長(zhǎng)度，跨位置選數(shù)字組成一組開(kāi)始插入排序
選擇排序 不穩(wěn)定
選擇排序是按順序比較前后，挑出最大和最小。將大的先放在后面，再下一次可以把相同大的放在上一次的之前，順序改變。
但會(huì)有人說(shuō)我可以通過(guò)控制代碼，來(lái)選擇第一次選到最大的那個(gè)是后面的那個(gè)數(shù)
還有一種情況
選擇排序算法中還有一段是這樣的，如果找到最大最小的兩個(gè)數(shù)，最大的數(shù)在最小數(shù)需要放的位置，先交換最大和最小，改變序號(hào)
堆排序 不穩(wěn)定
看圖，向下調(diào)整之后位置改變
冒泡排序 穩(wěn)定
前后兩個(gè)數(shù)交換，可以控制代碼使之相對(duì)位置不改變
快速排序 不穩(wěn)定
假設(shè)最左為key，左邊找大，右邊找小
相對(duì)位置發(fā)生改變
歸并排序 穩(wěn)定
實(shí)質(zhì)上細(xì)分來(lái)看是每個(gè)循環(huán)都是兩個(gè)數(shù)組，相對(duì)順序不變
按照從小到大的順序歸并到一個(gè)數(shù)組，所以穩(wěn)定
計(jì)數(shù)排序 穩(wěn)定
統(tǒng)計(jì)相同數(shù)值的個(gè)數(shù)，按順序映射到原數(shù)組
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://specialneedsforspecialkids.com/yun/125655.html
摘要：之所以把計(jì)數(shù)排序桶排序基數(shù)排序放在一起比較，是因?yàn)樗鼈兊钠骄鶗r(shí)間復(fù)雜度都為。動(dòng)畫(huà)計(jì)數(shù)排序思想找出待排序的數(shù)組中最大和最小的元素。桶排序計(jì)數(shù)排序能派上用場(chǎng)嗎手機(jī)號(hào)碼有位，范圍太大，顯然不適合用這兩種排序算法。 showImg(https://segmentfault.com/img/bVbuF9e?w=900&h=500); 1. 前言 算法為王。 想學(xué)好前端，先練好內(nèi)功，只有內(nèi)功深厚者...
摘要：筆者寫(xiě)的數(shù)據(jù)結(jié)構(gòu)與算法之美系列用的語(yǔ)言是，旨在入門(mén)數(shù)據(jù)結(jié)構(gòu)與算法和方便以后復(fù)習(xí)。這應(yīng)該是目前較為簡(jiǎn)單的十大經(jīng)典排序算法的文章講解了吧。比如原本在的前面，而，排序之后，在的后面十大經(jīng)典排序算法冒泡排序思想冒泡排序只會(huì)操作相鄰的兩個(gè)數(shù)據(jù)。 showImg(https://segmentfault.com/img/bVbvHet); 1. 前言 算法為王。想學(xué)好前端，先練好內(nèi)功，內(nèi)功不行，就...
本篇有7k+字, 系統(tǒng)梳理了js中常見(jiàn)的12種排序算法。除了基本排序算法，文章還包含了希爾排序、堆排序、桶排序等較為復(fù)雜的排序?qū)崿F(xiàn)，如果喜歡請(qǐng)點(diǎn)贊支持~謝謝. 原文: http://louiszhai.github.io/20... 導(dǎo)讀 排序算法可以稱(chēng)得上是我的盲點(diǎn), 曾幾何時(shí)當(dāng)我知道Chrome的Array.prototype.sort使用了快速排序時(shí), 我的內(nèi)心是奔潰的(啥是快排, 我只知道...
摘要：實(shí)際上，桶排序的應(yīng)用場(chǎng)景十分的有限，對(duì)數(shù)據(jù)的要求比較苛刻。極端情況下，如果數(shù)據(jù)全部劃分到一個(gè)桶內(nèi)，就變成了非線性排序了。 1. 回顧 前面已經(jīng)說(shuō)完了幾種非線性排序，它們分別是時(shí)間復(fù)雜度為 O(n2) 、適合小規(guī)模數(shù)據(jù)的冒泡排序、選擇排序、插入排序，和應(yīng)用較廣泛的時(shí)間復(fù)雜度為 O(nlogn) 的希爾排序、歸并排序、快速排序。其實(shí)這幾種排序都有一個(gè)特性，那就是它們都是基于數(shù)據(jù)的比較和移動(dòng)...
摘要：本文將介紹快速排序計(jì)數(shù)排序梳排序堆排序歸并排序希爾排序選擇排序插入排序地精排序聯(lián)合冒泡排序雞尾酒排序冒泡排序奇偶排序使用標(biāo)志的冒泡排序種排序算法的實(shí)現(xiàn)。是一種不穩(wěn)定的排序算法。 本文將介紹快速排序、計(jì)數(shù)排序、梳排序、堆排序、歸并排序、希爾排序、選擇排序、插入排序、地精排序、聯(lián)合冒泡排序、雞尾酒排序、冒泡排序、奇偶排序、使用標(biāo)志的冒泡排序14種排序算法的實(shí)現(xiàn)。本文是由于閱讀了文章《測(cè)試評(píng)...
閱讀 3735·2023-01-11 11:02
閱讀 4244·2023-01-11 11:02
閱讀 3050·2023-01-11 11:02
閱讀 5180·2023-01-11 11:02
閱讀 4737·2023-01-11 11:02
閱讀 5534·2023-01-11 11:02
閱讀 5313·2023-01-11 11:02
閱讀 3990·2023-01-11 11:02
