哈嘍，大家好，我是瓜哥，致力于為大家分享互聯(lián)網(wǎng)各領(lǐng)域干貨。

這篇文章可以說是一本書了，排版，碼字耗費(fèi)了瓜哥很長(zhǎng)的時(shí)間，10?萬 字 C 語言從入門到精通保姆級(jí)教程2021年版，覺得有價(jià)值記得一鍵三連支持。

計(jì)數(shù)排序（Counting Sort）

• 計(jì)數(shù)排序是一個(gè)非基于比較的排序算法，該算法于1954年由 Harold H. Seward 提出。它的優(yōu)勢(shì)在于在對(duì)一定范圍內(nèi)的整數(shù)排序時(shí)，快于任何比較排序算法。
• 排序思路:

• 1.找出待排序數(shù)組最大值
• 2.定義一個(gè)索引最大值為待排序數(shù)組最大值的數(shù)組
• 3.遍歷待排序數(shù)組, 將待排序數(shù)組遍歷到的值作新數(shù)組索引
• 4.在新數(shù)組對(duì)應(yīng)索引存儲(chǔ)值原有基礎(chǔ)上 1

• 簡(jiǎn)單代碼實(shí)現(xiàn):

int?main()
{
????//?待排序數(shù)組
????int?nums[5]?=?{3,?1,?2,?0,?3};
????//?用于排序數(shù)組
????int?newNums[4]?=?{0};
????//?計(jì)算待排序數(shù)組長(zhǎng)度
????int?len?=?sizeof(nums)?/?sizeof(nums[0]);
????//?遍歷待排序數(shù)組
????for(int?i?=?0;?i?????????//?取出待排序數(shù)組當(dāng)前值
????????int?index?=?nums[i];
????????//?將待排序數(shù)組當(dāng)前值作為排序數(shù)組索引
????????//?將用于排序數(shù)組對(duì)應(yīng)索引原有值 1
????????newNums[index]?=?newNums[index]? 1;
????}
????
????//?計(jì)算待排序數(shù)組長(zhǎng)度
????int?len2?=?sizeof(newNums)?/?sizeof(newNums[0]);
????//?輸出排序數(shù)組索引,?就是排序之后結(jié)果
????for(int?i?=?0;?i?????????for(int?j?=?0;?j?????????????printf("%i\n",?i);
????????}
????}
????/*
????//?計(jì)算待排序數(shù)組長(zhǎng)度
????int?len2?=?sizeof(newNums)?/?sizeof(newNums[0]);
????//?還原排序結(jié)果到待排序數(shù)組
????for(int?i?=?0;?i?????????int?index?=?0;
????????for(int?i?=?0;?i?????????????for(int?j?=?0;?j?????????????????nums[index ]?=?i;
????????????}
????????}
????}
????*/
????return?0;
}


選擇排序

選擇排序(Selection sort)是一種簡(jiǎn)單直觀的排序算法。它的工作原理如下。首先在未排序序列中找到最小元素,存放到排序序列的起始位置,然后,再從剩余未排序元素中繼續(xù)尋找最小元素,然后放到排序序列末尾。以此類推,直到所有元素均排序完畢。

• 排序思路:
• 假設(shè)按照升序排序
• 1.用第0個(gè)元素和后面所有元素依次比較
• 2.判斷第0個(gè)元素是否大于當(dāng)前被比較元素, 一旦小于就交換位置
• 3.第0個(gè)元素和后續(xù)所有元素比較完成后, 第0個(gè)元素就是最小值
• 4.排除第0個(gè)元素, 用第1個(gè)元素重復(fù)1~3操作, 比較完成后第1個(gè)元素就是倒數(shù)第二小的值
• 以此類推, 直到當(dāng)前元素沒有可比較的元素, 排序完成
• 代碼實(shí)現(xiàn):

//?選擇排序void?selectSort(int?numbers[],?int?length)?{????????//?外循環(huán)為什么要-1?????//?最后一位不用比較,?也沒有下一位和它比較,?否則會(huì)出現(xiàn)錯(cuò)誤訪問????for?(int?i?=?0;?i?for?(int?j?=?i;?j?if?(numbers[i]?

冒泡排序

• 冒泡排序(Bubble Sort)是一種簡(jiǎn)單的排序算法。它重復(fù) 地走訪過要排序的數(shù)列,一次比較兩個(gè)元素,如果他們的順序錯(cuò)誤就把他們交換過來。走訪數(shù)列的工作是重復(fù)地進(jìn)行直到?jīng)]有再需要交換,也就是說該數(shù)列已經(jīng)排序完成。這個(gè)算法的名字由來是因?yàn)樵叫〉脑貢?huì)經(jīng)由交換慢慢“浮”到數(shù)列的頂端。
• 排序思路:

• 假設(shè)按照升序排序
• 1.從第0個(gè)元素開始, 每次都用相鄰兩個(gè)元素進(jìn)行比較
• 2.一旦發(fā)現(xiàn)后面一個(gè)元素小于前面一個(gè)元素就交換位置
• 3.經(jīng)過一輪比較之后最后一個(gè)元素就是最大值
• 4.排除最后一個(gè)元素, 以此類推, 每次比較完成之后最大值都會(huì)出現(xiàn)再被比較所有元素的最后
• 直到當(dāng)前元素沒有可比較的元素, 排序完成

• 代碼實(shí)現(xiàn):

//?冒泡排序
void?bubbleSort(int?numbers[],?int?length)?{
????for?(int?i?=?0;?i?????????//?-1防止`角標(biāo)越界`:?訪問到了不屬于自己的索引
????????for?(int?j?=?0;?j????????????//??1.用當(dāng)前元素和相鄰元素比較
????????????if?(numbers[j]?????????????????//??2.一旦發(fā)現(xiàn)小于就交換位置
????????????????swapEle(numbers,?j,?j? ?1);
????????????}
????????}
????}
}
//?交換兩個(gè)元素的值,?i/j需要交換的索引
void?swapEle(int?array[],?int?i,?int?j)?{
????int?temp?=?array[i];
????array[i]?=?array[j];
????array[j]?=?temp;
}


插入排序

• 插入排序（Insertion-Sort）的算法描述是一種簡(jiǎn)單直觀的排序算法。它的工作原理是通過構(gòu)建有序序列，對(duì)于未排序數(shù)據(jù)，在已排序序列中從后向前掃描，找到相應(yīng)位置并插入。
• 排序思路:

• 假設(shè)按照升序排序
• 1.從索引為1的元素開始向前比較, 一旦前面一個(gè)元素大于自己就讓前面的元素先后移動(dòng)
• 2.直到?jīng)]有可比較元素或者前面的元素小于自己的時(shí)候, 就將自己插入到當(dāng)前空出來的位置

• 代碼實(shí)現(xiàn):

int?main()
{
????//?待排序數(shù)組
????int?nums[5]?=?{3,?1,?2,?0,?3};
????//?0.計(jì)算待排序數(shù)組長(zhǎng)度
????int?len?=?sizeof(nums)?/?sizeof(nums[0]);

????//??1.從第一個(gè)元素開始依次取出所有用于比較元素
????for?(int?i?=?1;?i?????{
????????//?2.取出用于比較元素
????????int?temp?=?nums[i];
????????int?j?=?i;
????????while(j?>?0){
????????????//?3.判斷元素是否小于前一個(gè)元素
????????????if(temp?????????????????//?4.讓前一個(gè)元素向后移動(dòng)一位
????????????????nums[j]?=?nums[j?-?1];
????????????}else{
????????????????break;
????????????}
????????????j--;
????????}
????????//?5.將元素插入到空出來的位置
????????nums[j]?=?temp;
????}
}
int?main()
{
????//?待排序數(shù)組
????int?nums[5]?=?{3,?1,?2,?0,?3};
????//?0.計(jì)算待排序數(shù)組長(zhǎng)度
????int?len?=?sizeof(nums)?/?sizeof(nums[0]);

????//??1.從第一個(gè)元素開始依次取出所有用于比較元素
????for?(int?i?=?1;?i?????{
????????//?2.遍歷取出前面元素進(jìn)行比較
????????for(int?j?=?i;?j?>?0;?j--)
????????{
????????????//?3.如果前面一個(gè)元素大于當(dāng)前元素,就交換位置
????????????if(nums[j-1]?>?nums[j]){
????????????????int?temp?=?nums[j];
????????????????nums[j]?=?nums[j?-?1];
????????????????nums[j?-?1]?=?temp;
????????????}else{
????????????????break;
????????????}
????????}
????}
}


希爾排序

• 1959年Shell發(fā)明，第一個(gè)突破O(n2)的排序算法，是簡(jiǎn)單插入排序的改進(jìn)版。它與插入排序的不同之處在于，它會(huì)優(yōu)先比較距離較遠(yuǎn)的元素。希爾排序又叫縮小增量排序。
• 排序思路:

• 1.希爾排序可以理解為插入排序的升級(jí)版, 先將待排序數(shù)組按照指定步長(zhǎng)劃分為幾個(gè)小數(shù)組
• 2.利用插入排序?qū)π?shù)組進(jìn)行排序, 然后將幾個(gè)排序的小數(shù)組重新合并為原始數(shù)組
• 3.重復(fù)上述操作, 直到步長(zhǎng)為1時(shí),再利用插入排序排序即可

• 代碼實(shí)現(xiàn):

int?main(){????//?待排序數(shù)組????int?nums[5]?=?{3,?1,?2,?0,?3};????//?0.計(jì)算待排序數(shù)組長(zhǎng)度????int?len?=?sizeof(nums)?/?sizeof(nums[0]);//?2.計(jì)算步長(zhǎng)????int?gap?=?len?/?2;????do{????????//??1.從第一個(gè)元素開始依次取出所有用于比較元素????????for?(int?i?=?gap;?i?while((j?-?gap)?>=?0)????????????{????????????????printf("%i?>?%i\n",?nums[j?-?gap],?nums[j]);????????????????//?3.如果前面一個(gè)元素大于當(dāng)前元素,就交換位置????????????????if(nums[j?-?gap]?>?nums[j]){????????????????????int?temp?=?nums[j];????????????????????nums[j]?=?nums[j?-?gap];????????????????????nums[j?-?gap]?=?temp;????????????????}else{????????????????????break;????????????????}????????????????j--;????????????}????????}????????//?每個(gè)小數(shù)組排序完成,?重新計(jì)算步長(zhǎng)????????gap?=?gap?/?2;????}while(gap?>=?1);}


江哥提示: 對(duì)于初學(xué)者而言, 排序算法一次不易于學(xué)習(xí)太多, 咋們先來5個(gè)玩一玩, 后續(xù)繼續(xù)講解其它5個(gè) 公眾號(hào)代碼情緣歡迎關(guān)注

折半查找

• 基本思路
• 在有序表中,取中間元素作為比較對(duì)象,若給定值與中間元素的要查找的數(shù)相等,則查找成功;若給定值小于中間元素的要查找的數(shù),則在中間元素的左半?yún)^(qū)繼續(xù)查找;
• 若給定值大于中間元素的要查找的數(shù),則在中間元素的右半?yún)^(qū)繼續(xù)查找。不斷重復(fù)上述查找過 程,直到查找成功,或所查找的區(qū)域無數(shù)據(jù)元素,查找失敗

• 實(shí)現(xiàn)步驟

• 在有序表中,取中間元素作為比較對(duì)象,若給定值與中間元素的要查找的數(shù)相等,則查找成功;

• 若給定值小于中間元素的要查找的數(shù),則在中間元素的左半?yún)^(qū)繼續(xù)查找;

• 若給定值大于中間元素的要查找的數(shù),則在中間元素的右半?yún)^(qū)繼續(xù)查找。

• 不斷重復(fù)上述查找過 程,直到查找成功,或所查找的區(qū)域無數(shù)據(jù)元素,查找失敗。

• 代碼實(shí)現(xiàn)

int?findKey(int?values[],?int?length,?int?key)?{
????//?定義一個(gè)變量記錄最小索引
????int?min?=?0;
????//?定義一個(gè)變量記錄最大索引
????int?max?=?length?-?1;
????//?定義一個(gè)變量記錄中間索引
????int?mid?=?(min? ?max)?*?0.5;
????
????while?(min?<=?max)?{
????????//?如果mid對(duì)應(yīng)的值?大于?key,?那么max要變小
????????if?(values[mid]?>?key)?{
????????????max?=?mid?-?1;
????????????//?如果mid對(duì)應(yīng)的值?小于?key,?那么min要變
????????}else?if?(values[mid]?????????????min?=?mid? ?1;
????????}else?{
????????????return?mid;
????????}
????????//?修改完min/max之后,?重新計(jì)算mid的值
????????mid?=?(min? ?max)?*?0.5;
????}
????return?-1;
}


進(jìn)制轉(zhuǎn)換(查表法)

• 實(shí)現(xiàn)思路:

• 將二進(jìn)制、八進(jìn)制、十進(jìn)制、十六進(jìn)制所有可能的字符都存入數(shù)組
• 利用按位與運(yùn)算符和右移依次取出當(dāng)前進(jìn)制對(duì)應(yīng)位置的值
• 利用取出的值到數(shù)組中查詢當(dāng)前位輸出的結(jié)果
• 將查詢的結(jié)果存入一個(gè)新的數(shù)組, 當(dāng)所有位都查詢存儲(chǔ)完畢, 新數(shù)組中的值就是對(duì)應(yīng)進(jìn)制的值

• 代碼實(shí)現(xiàn)

#include?
void?toBinary(int?num)
{
????total(num,?1,?1);
}
void?toOct(int?num)
{
????total(num,?7,?3);
}
void?toHex(int?num)
{
????total(num,?15,?4);
}

void?total(int?num?,?int?base,?int?offset)
{
????//????1.定義表用于查詢結(jié)果
????char?cs[]?=?{
????????'0',?'1',?'2',?'3',?'4',?'5',
????????'6',?'7',?'8',?'9',?'a',?'b',
????????'c',?'d',?'e',?'f'
????};
????//????2.定義保存結(jié)果的數(shù)組
????char?rs[32];
????//????計(jì)算最大的角標(biāo)位置
????int?length?=?sizeof(rs)/sizeof(char);
????int?pos?=?length;//8

????while?(num?!=?0)?{
????????int?index?=?num?