下面的99%的代碼都是手動(dòng)敲出來(lái)的，參考了諸多資料,，已經(jīng)經(jīng)過測(cè)試,，可以放心食用。
1.冒泡排序
基本思想
冒泡排序基本思想是依次比較兩個(gè)相鄰的元素,，如果順序（如從大到小,、首字母從Z到A）錯(cuò)誤就把他們交換過來(lái),。走訪元素的工作是重復(fù)地進(jìn)行直到?jīng)]有相鄰元素需要交換，也就是說(shuō)該元素列已經(jīng)排序完成,。
在進(jìn)行第一輪上面的從左到右的比較時(shí),，則會(huì)把一個(gè)最小或者最大的元素（取決于你想要的排列方式）'冒泡'到最右邊的位置，第二輪則是冒泡第二大或第二小的數(shù)到最右邊,，因此我們總共只需要進(jìn)行n-1輪即可,，最后一個(gè)數(shù)的位置也被固定了（其余n-1個(gè)數(shù)都比他大且都在其右邊）。
這個(gè)算法的名字由來(lái)是因?yàn)?strong>越小的元素會(huì)經(jīng)由交換慢慢“浮”到數(shù)列的頂端（升序或降序排列）,，就如同碳酸飲料中二氧化碳的氣泡最終會(huì)上浮到頂端一樣,，故名“冒泡排序”。
動(dòng)畫：
實(shí)現(xiàn)
//void bubbleSort(){
//C實(shí)現(xiàn)
int arr[] = {5, 9, 3, 8, 6};
int len = sizeof(arr)/sizeof(arr[0]);
int temp;
for (int i = 0; i < len - 1; i ) //從小到大
{ // 外循環(huán)為排序趟數(shù)，len個(gè)數(shù)進(jìn)行l(wèi)en-1趟
for (int j = 0; j < len - 1 - i; j )
{ // 內(nèi)循環(huán)為每趟比較的次數(shù),，第i趟比較len-i次,因?yàn)榈谝淮我呀?jīng)將最大的元素冒泡到最后一個(gè)位置了
if (arr[j] > arr[j 1])
{ //相鄰元素比較,逆序則將交換位置
temp = arr[j];
arr[j] = arr[j 1];
arr[j 1] = temp;
}
}
}
//打印數(shù)組
for (int i = 0; i < len; i )
printf('%d\t', arr[i]);
}2.選擇排序
基本思想
第一次從待排序的數(shù)據(jù)元素中選出最?。ɑ蜃畲螅┑囊粋€(gè)元素，存放在序列的起始位置,，然后再?gòu)氖Ｓ嗟奈磁判蛟刂袑ふ业阶钚,。ù螅┰兀缓蠓诺揭雅判虻男蛄械哪┪?。以此類推,，直到全部待排序的?shù)據(jù)元素的個(gè)數(shù)為零。
動(dòng)畫：
實(shí)現(xiàn)
//int arr[] = {100, 92, 5, 9, 3, 8, 23, 17, 50, 6}; int len = sizeof(arr)/sizeof(arr[0]);
int index = 0; //待會(huì)用來(lái)存儲(chǔ)未排序區(qū)最小元素的位置索引
for (int i = 0; i < len; i ) //從小到大
{
index = i;
for (int j = i 1; j < len; j ) //用i之后的每一個(gè)元素去與i元素比較大小,若小于arr[i]則更新最小元素索引
{
if (arr[j] < arr[index])
index = j;
}
//將i與index的元素調(diào)換位置
//注意:此處不可將調(diào)換位置的函數(shù)寫進(jìn)第二層for循環(huán)即for(int j=i 1)中,因?yàn)榻粨Q后i與min指向的對(duì)象會(huì)交換,此后循環(huán)就可能出現(xiàn)僅僅小于arr[i](此時(shí)已經(jīng)換到了min位置)但不小于arr[min](這時(shí)在i位置上)的元素也與初始位置上進(jìn)行交換的情況,具體情況可以試驗(yàn)!
if (i != index) //判斷是否需要調(diào)換,將最小元素位置換至第一個(gè)未排序的位置
{
int temp = arr[i];
arr[i] = arr[index];
arr[index] = temp;
}
}
//打印數(shù)組
for (int i = 0; i < len; i )
printf('%d\t', arr[i]);
}3.插入排序
基本思想
插入排序是一種最簡(jiǎn)單的排序方法，它的基本思想是將一個(gè)記錄插入到已經(jīng)排好序的有序表中,，從而形成一個(gè)新的,、記錄數(shù)增1的有序表。
一般將第一個(gè)元素看做最小的有序組,然后用第二個(gè)元素插入到第一個(gè)元素組成的有序表中(其實(shí)就是個(gè)簡(jiǎn)單的比較大小),然后將第三個(gè)元素插入到前兩個(gè)元素組成的有序表中,形成一個(gè)三個(gè)元素的有序表,以此類推,最終獲得一個(gè)包含全部元素的有序表
實(shí)現(xiàn)
//void insertionSort(){
int arr[] = {1, 5, 3, 9, 7};
int len = sizeof(arr)/sizeof(arr[0]);
int i, j, key;
for (i = 1; i < len; i ) //從1開始是因?yàn)槟J(rèn)第一個(gè)元素是最小的有序表
{
key = arr[i];
j = i - 1; //a[j]是有序表最后一個(gè)元素
while ((j >= 0) && (arr[j] > key)) //從后往前遍歷并且判斷arr[j]是否大于key
//j>=0防止數(shù)組越界
{
arr[j 1] = arr[j];//后移
j--;//j前移
}
arr[j 1] = key; //arr[j]是第一個(gè)比key小的元素,將key置于其后(比key大的有序表元素都已經(jīng)后移一個(gè)位置了)
}
//打印數(shù)組
for (int i = 0; i < len; i )
printf('%d\t', arr[i]);
}4.希爾排序
基本思想
希爾排序，也稱遞減增量排序算法,，是插入排序的一種更高效的改進(jìn)版本
基本思想是先將整個(gè)待排序的記錄序列分割成為若干子序列分別進(jìn)行直接插入排序,，待整個(gè)序列中的記錄'基本有序'時(shí)，再對(duì)全體記錄進(jìn)行依次直接插入排序,。
具體實(shí)現(xiàn)方法:
- 把待排序列，分成多個(gè)間隔為gap的子序列,，
- 然后對(duì)每個(gè)子序列進(jìn)行插入排序
- 重復(fù)上述,，每次間隔gap不同（并且越來(lái)越?。钡阶詈笠淮芜x取間隔gap=1,，完成排序,。
- 我們一般是取數(shù)組長(zhǎng)度的一半為第一個(gè)間隔，即第一次將整個(gè)數(shù)組以len/2為間隔分為2個(gè)子序列,，再進(jìn)行插入排序,，然后以len/2/2為間隔一直到gap=1重復(fù)上述動(dòng)作下圖來(lái)自網(wǎng)絡(luò),便于理解
實(shí)現(xiàn)
//void shellSort(){
int arr[] = {1,12,13,19,26,7,8,15,3,23,99,8,35,27,34,5};
int len = sizeof(arr)/sizeof(arr[0]); //16
int gap, i, j;
int temp;
for (gap = len / 2; gap >= 1; gap /= 2) //第一個(gè)間隔為len/2,然后不斷除2縮小
{
for (i = gap; i < len; i ) //對(duì)每一個(gè)下標(biāo)大于gap的元素進(jìn)行遍歷
//arr[gap]是第一組最后一個(gè)元素
{
temp = arr[i]; //將要插入的值賦值給temp,因?yàn)樗幍奈恢每赡鼙桓采w
for (j = i - gap; arr[j] > temp && j >= 0; j -= gap)
{ //i所處的子序列:i i-gap i-2gap i-n*gap( i-n*gap >= 0)
arr[j gap] = arr[j]; //arr[j]若大于要插入的值則將位置后移
}
arr[j gap] = temp; //無(wú)論是arr[j]<temp還是j<0了,都將temp插入到arr[j]這一個(gè)子序列的后一個(gè)位置(j gap)
}
}
//打印數(shù)組
for (int i = 0; i < len; i )
printf('%d\t', arr[i]);
}5.歸并排序
動(dòng)畫
實(shí)現(xiàn)
//int min(int x, int y){
return x < y ? x : y;
}
void merge_sort(int arr[], int len)
{
int *a = arr; //左指針->首元素
int *b = (int *)malloc(len * sizeof(int)); //右指針->尾元素
int seg, start;
for (seg = 1; seg < len; seg = seg)
{
for (start = 0; start < len; start = seg * 2)
{
int low = start;
int mid = min(start seg, len);
int high = min(start seg * 2, len);
int k = low;
int start1 = low, end1 = mid;
int start2 = mid, end2 = high;
while (start1 < end1 && start2 < end2)
b[k ] = a[start1] < a[start2] ? a[start1 ] : a[start2 ];
while (start1 < end1)//將左邊剩下的元素放置到數(shù)組b中
b[k ] = a[start1 ];
while (start2 < end2)//將左邊剩下的元素放置到數(shù)組b中
b[k ] = a[start2 ];
}
int *temp = a;
a = b;
b = temp;
}
if (a != arr)
{
int i;
for (i = 0; i < len; i )
b[i] = a[i];
b = a;
}
free(b);
}6.快速排序
基本思想
- 從數(shù)列中挑出一個(gè)元素,，稱為 “基準(zhǔn)”（pivot）;
- 重新排序數(shù)列，所有元素比基準(zhǔn)值小的擺放在基準(zhǔn)前面,，所有元素比基準(zhǔn)值大的擺在基準(zhǔn)的后面（相同的數(shù)可以到任一邊）,。在這個(gè)分區(qū)退出之后，該基準(zhǔn)就處于數(shù)列的中間位置,。這個(gè)稱為分區(qū)（partition）操作,；
- 遞歸地（recursive）把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序；
動(dòng)畫
實(shí)現(xiàn)
//void quickSort(){
int arr[10] = {11, 7, 9, 3, 4, 6, 2, 8, 5, 3};
quick_sort(arr, 0, 9);
for (int i = 0; i < 10; i )
printf('%d\t', arr[i]);
}
int partition(int arr[], int start, int end)
{
int temp = arr[start];//以arr[start]作為基準(zhǔn),將被放置在數(shù)組中間
//同時(shí)將start位置作為交換元素的緩沖點(diǎn)-類比交換兩個(gè)數(shù)的第三個(gè)數(shù)
int li = start, ri = end;//li->left index 左索引 li==start 所以初始li是第一個(gè)緩沖點(diǎn)
while (li < ri)
{
while (li < ri && arr[ri] > temp)//找到我們右起第一個(gè)小于基準(zhǔn)值的元素索引ri
ri--;
if (li < ri)
{
arr[li] = arr[ri];//將右起第一個(gè)小于基準(zhǔn)值的元素索引放置在緩沖點(diǎn)(li)
//同時(shí)此時(shí)的ri成為新的緩沖點(diǎn)
li ;
}
while (li < ri && arr[li] < temp)//找到我們右起第一個(gè)小于基準(zhǔn)值的元素索引li
li ;
if (li < ri)
{
arr[ri] = arr[li];//將左起第一個(gè)大于基準(zhǔn)值的元素索引放置在緩沖點(diǎn) (ri)
//同時(shí)此時(shí)的li成為新的緩沖點(diǎn)
ri--;
}
//結(jié)束上述操作后li和ri分別是左右已排序部分(置于兩端)的后面一個(gè)和前面一個(gè)元素(不包含在其中)
//明顯若li==ri則只剩下最后一個(gè)位置
}
arr[li] = temp;
return li;//返回的是基準(zhǔn)值最終的索引
}
void quick_sort(int arr[], int start, int end)
{
if (start < end)
{
int index = partition(arr, start, end);//依照基準(zhǔn)值分區(qū)
quick_sort(arr, start, index - 1);//基準(zhǔn)值之左再排序
quick_sort(arr, index 1, end);//基準(zhǔn)值之右再排序
}
}7.堆排序
基本思想
- 創(chuàng)建一個(gè)大頂堆( 每個(gè)結(jié)點(diǎn)的值都大于或等于其左右孩子結(jié)點(diǎn)的值，稱為大頂堆 ),；
- 把堆首（最大值）和堆尾互換,；
- 把堆的尺寸縮小 1，利用剩下的元素再次建立一個(gè)大頂堆,；
- 重復(fù)步驟 2 3,，直到堆的尺寸為 1。
動(dòng)畫
實(shí)現(xiàn)
////7.堆排序void heapSort()
{
int arr[] = {3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6};
int len = (int)sizeof(arr) / sizeof(*arr);
for (int i = len; i > 1; i--)
heap_Sort(arr, i); //建立堆 每次規(guī)模減1
//打印結(jié)果
for (int i = 0; i < len; i )
printf('%d ', arr[i]);
return 0;
}
//構(gòu)造一個(gè)大頂堆并將最大值換至最后一位
void heap_Sort(int arr[], int len)
{
int dad = len / 2 - 1; //最后一個(gè)父節(jié)點(diǎn)
int son = 2 * dad 1; //該父節(jié)點(diǎn)下的首個(gè)子節(jié)點(diǎn)
while (dad >= 0)
{
//判斷是否有兩個(gè)子節(jié)點(diǎn)若有則在其中尋找最大子節(jié)點(diǎn)
if (son 1 <= len - 1 && arr[son] < arr[son 1])
son ;
if (arr[dad] < arr[son]) //若父節(jié)點(diǎn)小于子節(jié)點(diǎn)則交換位置
swap(&arr[dad], &arr[son]);
dad--; //回退到上一個(gè)父節(jié)點(diǎn)
son = 2 * dad 1; //上一個(gè)父節(jié)點(diǎn)的首個(gè)子節(jié)點(diǎn)
}
swap(&arr[0], &arr[len - 1]);
}
void swap(int *a, int *b)
{
int temp = *a;
*a = *b;
*b = temp;
}8.計(jì)數(shù)排序
基本思想
- 找出待排序的數(shù)組中最大和最小的元素
- 統(tǒng)計(jì)數(shù)組中每個(gè)值為i的元素出現(xiàn)的次數(shù)，存入數(shù)組C的第i項(xiàng)
- 對(duì)所有的計(jì)數(shù)累加（從C中的第一個(gè)元素開始,，每一項(xiàng)和前一項(xiàng)相加）
- 反向填充目標(biāo)數(shù)組：將每個(gè)元素i放在新數(shù)組的第C(i)項(xiàng),，每放一個(gè)元素就將C(i)減去1
動(dòng)畫
實(shí)現(xiàn)
//void countingSort(){
int arr[] = {3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6};
int len = (int)sizeof(arr) / sizeof(*arr);
counting_Sort(arr, len);
for (int i = 0; i < len; i )
printf('%d ', arr[i]);
}
void counting_Sort(int arr[], int LEN)
{
//尋找最大最小值
int max = arr[0], min = arr[0], i, j = 0;
for (i = 0; i < LEN; i )
{
if (arr[i] < min)
min = arr[i];
if (arr[i] > max)
max = arr[i];
}
//建立計(jì)數(shù)數(shù)組
int new_len = max - min 1;
int conunting_arr[new_len];
for (i = 0; i < new_len; i ) //初始化
conunting_arr[i] = 0;
for (i = 0; i < LEN; i ) //計(jì)數(shù)
conunting_arr[arr[i] - min] ;
//根據(jù)計(jì)數(shù)結(jié)果進(jìn)行排序
for (i = 0; i < new_len; i )
{
int index = conunting_arr[i];
while (index != 0)
{
arr[j] = i min;
index--;
j ;
}
}
}9.桶排序
最簡(jiǎn)單的桶排序
將數(shù)組{1,3,3,7,9,2,4,6,6,0}進(jìn)行排序:
觀察數(shù)組元素范圍,，看出來(lái)是從0到9（可以去遍歷取得最大最小值），所以我們建立10個(gè)有序桶,，將數(shù)字一個(gè)個(gè)塞入對(duì)應(yīng)的桶中,，然后根據(jù)桶的情況進(jìn)行輸出（桶中有幾個(gè)元素就輸出幾個(gè)，沒有就跳過）-實(shí)際上就是最簡(jiǎn)單的計(jì)數(shù)排序，但網(wǎng)上有人把這個(gè)也算作桶排序了,，不要搞混,，下面來(lái)看真正的桶排序吧。
基本思想
桶排序(Bucket sort)或所謂的箱排序,，計(jì)數(shù)排序的升級(jí)版,，工作的原理是將數(shù)組分到有限數(shù)量的桶子里。每個(gè)桶子再個(gè)別排序（有可能再使用別的排序算法或是以遞歸方式繼續(xù)使用桶排序進(jìn)行排序）,。
每個(gè)桶對(duì)應(yīng)一個(gè)數(shù)據(jù)或者一個(gè)數(shù)據(jù)段(實(shí)際上當(dāng)每個(gè)桶對(duì)應(yīng)一個(gè)數(shù)據(jù)的時(shí)候其實(shí)就是前面的計(jì)數(shù)排序)
這里我們使每個(gè)桶對(duì)應(yīng)一個(gè)數(shù)據(jù)段并且對(duì)桶中元素使用冒泡排序進(jìn)行排序操作
動(dòng)畫
實(shí)現(xiàn)
//void bucketSort(){
int arr[] = {3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6};
int len = (int)sizeof(arr) / sizeof(arr[0]);//30
bucket_Sort(arr, len);
for (int i = 0; i < len; i )
printf('%d ', arr[i]);
}
void bucket_sort(int arr[], int LEN)
{
int bucket[5][6] = {0}, i, j, k, temp; //初始化桶,每個(gè)桶存放6個(gè)數(shù)據(jù)
//尋找最大最小值
int min = arr[0], max = arr[0];
for (i = 0; i < LEN; i )
{
if (arr[i] < min)
min = arr[i];
if (arr[i] > max)
max = arr[i];
}
//遍歷數(shù)組,將元素放到對(duì)應(yīng)桶中
int index0 = 0, index1 = 0, index2 = 0, index3 = 0, index4 = 0;
for (i = 0; i < LEN; i )
{
if (arr[i] < min (max - min 1) / 5 * 1 && index0 < 7)
{
bucket[0][index0] = arr[i];
index0 ;
}
else if (arr[i] < min (max - min 1) / 5 * 2 && (index1 < 7 || index0 >= 7))
{
bucket[1][index1] = arr[i];
index1 ;
}
else if (arr[i] < min (max - min 1) / 5 * 3 && (index2 < 7 || index1 >= 7))
{
bucket[2][index2] = arr[i];
index2 ;
}
else if (arr[i] < min (max - min 1) / 5 * 4 && (index3 < 7 || index2 >= 7))
{
bucket[3][index3] = arr[i];
index3 ;
}
else if (arr[i] < min (max - min 1) / 5 * 5 && (index4 < 7 || index3 >= 7))
{
bucket[4][index4] = arr[i];
index4 ;
}
}
//在每個(gè)桶中使用冒泡排序
for (i = 0; i < 5; i )
{
for (int j = 0; j < 5; j ) //從小到大
{ // 外循環(huán)為排序趟數(shù),，len個(gè)數(shù)進(jìn)行len-1趟
for (int k = 0; k < 5 - i; k )
{ // 內(nèi)循環(huán)為每趟比較的次數(shù),，第i趟比較len-i次,因?yàn)榈谝淮我呀?jīng)將最大的元素冒泡到最后一個(gè)位置了
if (bucket[i][k] > bucket[i][k 1])
{ //相鄰元素比較,逆序則將交換位置
temp = bucket[i][k];
bucket[i][k] = bucket[i][k 1];
bucket[i][k 1] = temp;
}
}
}
}
//將桶中排序結(jié)果還原到原數(shù)組中
for (i = 0; i < 5; i )
{
for (j = 0; j < 6; j )
{
arr[i * 6 j] = bucket[i][j];
}
}
}10.基數(shù)排序
基本思想
基數(shù)排序是一種非比較型整數(shù)排序算法，其原理是將整數(shù)按位數(shù)切割成不同的數(shù)字,，然后按每個(gè)位數(shù)分別比較,。由于整數(shù)也可以表達(dá)字符串（比如名字或日期）和特定格式的浮點(diǎn)數(shù)，所以基數(shù)排序也不是只能使用于整數(shù),。
動(dòng)畫
實(shí)現(xiàn)
#include <stdio.h>
//void radixsort(int *a, int n){
int b[n], m = a[0], exp = 1, BASE = 10, i;
//尋找最大值
for (i = 1; i < n; i )
if (a[i] > m)
m = a[i];
while (m / exp > 0)
{
int bucket[BASE] = {0};
//按照exp所在的位將所有元素放入桶中
for (i = 0; i < n; i )
bucket[(a[i] / exp) % BASE] ;
//做前綴和-以<=i結(jié)尾的數(shù)的個(gè)數(shù)-以i結(jié)尾的數(shù)的最大索引 1
for (i = 1; i < BASE; i )
bucket[i] = bucket[i - 1];
//依據(jù)前綴和將原數(shù)組中每一個(gè)元素放置在基于技術(shù)排列后的位置 并將前綴和減1
for (i = n - 1; i >= 0; i--)
b[--bucket[(a[i] / exp) % BASE]] = a[i];
//復(fù)制回原數(shù)組
for (i = 0; i < n; i )
a[i] = b[i];
exp *= BASE;
}
}
int main()
{
int arr[10] = {1, 35, 98, 256, 789, 47, 4, 956, 64, 222};
int len = sizeof(arr) / sizeof(arr[0]);
radixsort(&arr[0], len);
for (int i = 0; i < len; i )
printf('%d\t', arr[i]);
return 0;
}來(lái)源：https://blog.csdn.net/weixin_45761327/article/details/105908057
C語(yǔ)言是每個(gè)想要學(xué)習(xí)編程的小伙伴首要學(xué)習(xí)的語(yǔ)言~如果你也希望成為一個(gè)好的程序員,，了解C語(yǔ)言更多知識(shí),，點(diǎn)擊下方【了解更多】，接受牛人大牛們的指導(dǎo),，聽聽他們對(duì)寫代碼的建議,，一起快樂學(xué)習(xí)，共同進(jìn)步~
