下面的99%的代碼都是手動敲出來的,參考了諸多資料,已經經過測驗,可以放心食用,
1.冒泡排序
基本思想
冒泡排序基本思想是依次比較兩個相鄰的元素,如果順序(如從大到小、首字母從Z到A)錯誤就把他們交換過來,走訪元素的作業是重復地進行直到沒有相鄰元素需要交換,也就是說該元素列已經排序完成,
在進行第一輪上面的從左到右的比較時,則會把一個最小或者最大的元素(取決于你想要的排列方式)"冒泡"到最右邊的位置,第二輪則是冒泡第二大或第二小的數到最右邊,因此我們總共只需要進行n-1輪即可,最后一個數的位置也被固定了(其余n-1個數都比他大且都在其右邊),
這個演算法的名字由來是因為越小的元素會經由交換慢慢“浮”到數列的頂端(升序或降序排列),就如同碳酸飲料中二訊訓碳的氣泡最侄訓上浮到頂端一樣,故名“冒泡排序”,
影片:
實作
//void bubbleSort(){
//C實作
int arr[] = {5, 9, 3, 8, 6};
int len = sizeof(arr)/sizeof(arr[0]);
int temp;
for (int i = 0; i < len - 1; i++) //從小到大
{ // 外回圈為排序趟數,len個數進行len-1趟
for (int j = 0; j < len - 1 - i; j++)
{ // 內回圈為每趟比較的次數,第i趟比較len-i次,因為第一次已經將最大的元素冒泡到最后一個位置了
if (arr[j] > arr[j + 1])
{ //相鄰元素比較,逆序則將交換位置
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
//列印陣列
for (int i = 0; i < len; i++)
printf("%d\t", arr[i]);
}
小編推薦一個學C語言/C++的學習裙【 712,284,705】,無論你是小白還是進階者,是想轉行還是想入行都可以來了解一起進步一起學習!裙內有開發工具,很多干貨和技術資料分享!
2.選擇排序
基本思想
第一次從待排序的資料元素中選出最小(或最大)的一個元素,存放在序列的起始位置,然后再從剩余的未排序元素中尋找到最小(大)元素,然后放到已排序的序列的末尾,以此類推,直到全部待排序的資料元素的個數為零,
影片:
實作
//int arr[] = {100, 92, 5, 9, 3, 8, 23, 17, 50, 6}; int len = sizeof(arr)/sizeof(arr[0]);
int index = 0; //待會用來存盤未排序區最小元素的位置索引
for (int i = 0; i < len; i++) //從小到大
{
index = i;
for (int j = i + 1; j < len; j++) //用i之后的每一個元素去與i元素比較大小,若小于arr[i]則更新最小元素索引
{
if (arr[j] < arr[index])
index = j;
}
//將i與index的元素調換位置
//注意:此處不可將調換位置的函式寫進第二層for回圈即for(int j=i+1)中,因為交換后i與min指向的物件會交換,此后回圈就可能出現僅僅小于arr[i](此時已經換到了min位置)但不小于arr[min](這時在i位置上)的元素也與初始位置上進行交換的情況,具體情況可以試驗!
if (i != index) //判斷是否需要調換,將最小元素位置換至第一個未排序的位置
{
int temp = arr[i];
arr[i] = arr[index];
arr[index] = temp;
}
}
//列印陣列
for (int i = 0; i < len; i++)
printf("%d\t", arr[i]);
}
3.插入排序
基本思想
插入排序是一種最簡單的排序方法,它的基本思想是將一個記錄插入到已經排好序的有序表中,從而形成一個新的、記錄數增1的有序表,
一般將第一個元素看做最小的有序組,然后用第二個元素插入到第一個元素組成的有序表中(其實就是個簡單的比較大小),然后將第三個元素插入到前兩個元素組成的有序表中,形成一個三個元素的有序表,以此類推,最侄訓得一個包含全部元素的有序表
實作
//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開始是因為默認第一個元素是最小的有序表
{
key = arr[i];
j = i - 1; //a[j]是有序表最后一個元素
while ((j >= 0) && (arr[j] > key)) //從后往前遍歷并且判斷arr[j]是否大于key
//j>=0防止陣列越界
{
arr[j + 1] = arr[j];//后移
j--;//j前移
}
arr[j + 1] = key; //arr[j]是第一個比key小的元素,將key置于其后(比key大的有序表元素都已經后移一個位置了)
}
//列印陣列
for (int i = 0; i < len; i++)
printf("%d\t", arr[i]);
}
4.希爾排序
基本思想
希爾排序,也稱遞減增量排序演算法,是插入排序的一種更高效的改進版本
基本思想是先將整個待排序的記錄序列分割成為若干子序列分別進行直接插入排序,待整個序列中的記錄"基本有序"時,再對全體記錄進行依次直接插入排序,
具體實作方法:
- 把待排序列,分成多個間隔為gap的子序列,
- 然后對每個子序列進行插入排序
- 重復上述,每次間隔gap不同(并且越來越小),直到最后一次選取間隔gap=1,完成排序,
- 我們一般是取陣列長度的一半為第一個間隔,即第一次將整個陣列以len/2為間隔分為2個子序列,再進行插入排序,然后以len/2/2為間隔一直到gap=1重復上述動作下圖來自網路,便于理解
實作
//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) //第一個間隔為len/2,然后不斷除2縮小
{
for (i = gap; i < len; i++) //對每一個下標大于gap的元素進行遍歷
//arr[gap]是第一組最后一個元素
{
temp = arr[i]; //將要插入的值賦值給temp,因為它所處的位置可能被覆寫
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; //無論是arr[j]<temp還是j<0了,都將temp插入到arr[j]這一個子序列的后一個位置(j+gap)
}
}
//列印陣列
for (int i = 0; i < len; i++)
printf("%d\t", arr[i]);
}
5.歸并排序
影片
實作
//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)//將左邊剩下的元素放置到陣列b中
b[k++] = a[start1++];
while (start2 < end2)//將左邊剩下的元素放置到陣列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);
}
小編推薦一個學C語言/C++的學習裙【 712,284,705】,無論你是小白還是進階者,是想轉行還是想入行都可以來了解一起進步一起學習!裙內有開發工具,很多干貨和技術資料分享!
6.快速排序
基本思想
- 從數列中挑出一個元素,稱為 “基準”(pivot);
- 重新排序數列,所有元素比基準值小的擺放在基準前面,所有元素比基準值大的擺在基準的后面(相同的數可以到任一邊),在這個磁區退出之后,該基準就處于數列的中間位置,這個稱為磁區(partition)操作;
- 遞回地(recursive)把小于基準值元素的子數列和大于基準值元素的子數列排序;
影片
實作
//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]作為基準,將被放置在陣列中間
//同時將start位置作為交換元素的緩沖點-類比交換兩個數的第三個數
int li = start, ri = end;//li->left index 左索引 li==start 所以初始li是第一個緩沖點
while (li < ri)
{
while (li < ri && arr[ri] > temp)//找到我們右起第一個小于基準值的元素索引ri
ri--;
if (li < ri)
{
arr[li] = arr[ri];//將右起第一個小于基準值的元素索引放置在緩沖點(li)
//同時此時的ri成為新的緩沖點
li++;
}
while (li < ri && arr[li] < temp)//找到我們右起第一個小于基準值的元素索引li
li++;
if (li < ri)
{
arr[ri] = arr[li];//將左起第一個大于基準值的元素索引放置在緩沖點 (ri)
//同時此時的li成為新的緩沖點
ri--;
}
//結束上述操作后li和ri分別是左右已排序部分(置于兩端)的后面一個和前面一個元素(不包含在其中)
//明顯若li==ri則只剩下最后一個位置
}
arr[li] = temp;
return li;//回傳的是基準值最終的索引
}
void quick_sort(int arr[], int start, int end)
{
if (start < end)
{
int index = partition(arr, start, end);//依斬訓準值磁區
quick_sort(arr, start, index - 1);//基準值之左再排序
quick_sort(arr, index + 1, end);//基準值之右再排序
}
}
7.堆排序
基本思想
- 創建一個大頂堆( 每個結點的值都大于或等于其左右孩子結點的值,稱為大頂堆 );
- 把堆首(最大值)和堆尾互換;
- 把堆的尺寸縮小 1,利用剩下的元素再次建立一個大頂堆;
- 重復步驟 2 3,直到堆的尺寸為 1,
影片
實作
////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); //建立堆 每次規模減1
//列印結果
for (int i = 0; i < len; i++)
printf("%d ", arr[i]);
return 0;
}
//構造一個大頂堆并將最大值換至最后一位
void heap_Sort(int arr[], int len)
{
int dad = len / 2 - 1; //最后一個父節點
int son = 2 * dad + 1; //該父節點下的首個子節點
while (dad >= 0)
{
//判斷是否有兩個子節點若有則在其中尋找最大子節點
if (son + 1 <= len - 1 && arr[son] < arr[son + 1])
son++;
if (arr[dad] < arr[son]) //若父節點小于子節點則交換位置
swap(&arr[dad], &arr[son]);
dad--; //回退到上一個父節點
son = 2 * dad + 1; //上一個父節點的首個子節點
}
swap(&arr[0], &arr[len - 1]);
}
void swap(int *a, int *b)
{
int temp = *a;
*a = *b;
*b = temp;
}
8.計數排序
基本思想
- 找出待排序的陣列中最大和最小的元素
- 統計陣列中每個值為i的元素出現的次數,存入陣列C的第i項
- 對所有的計數累加(從C中的第一個元素開始,每一項和前一項相加)
- 反向填充目標陣列:將每個元素i放在新陣列的第C(i)項,每放一個元素就將C(i)減去1
影片
實作
//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];
}
//建立計數陣列
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++) //計數
conunting_arr[arr[i] - min]++;
//根據計數結果進行排序
for (i = 0; i < new_len; i++)
{
int index = conunting_arr[i];
while (index != 0)
{
arr[j] = i + min;
index--;
j++;
}
}
}
9.桶排序
最簡單的桶排序
將陣列{1,3,3,7,9,2,4,6,6,0}進行排序:
觀察陣列元素范圍,看出來是從0到9(可以去遍歷取得最大最小值),所以我們建立10個有序桶,將數字一個個塞入對應的桶中,然后根據桶的情況進行輸出(桶中有幾個元素就輸出幾個,沒有就跳過)-實際上就是最簡單的計數排序,但網上有人把這個也算作桶排序了,不要搞混,下面來看真正的桶排序吧,
基本思想
桶排序(Bucket sort)或所謂的箱排序,計數排序的升級版,作業的原理是將陣列分到有限數量的桶子里,每個桶子再個別排序(有可能再使用別的排序演算法或是以遞回方式繼續使用桶排序進行排序),
每個桶對應一個資料或者一個資料段(實際上當每個桶對應一個資料的時候其實就是前面的計數排序)
這里我們使每個桶對應一個資料段并且對桶中元素使用冒泡排序進行排序操作
影片
實作
//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; //初始化桶,每個桶存放6個資料
//尋找最大最小值
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];
}
//遍歷陣列,將元素放到對應桶中
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++;
}
}
//在每個桶中使用冒泡排序
for (i = 0; i < 5; i++)
{
for (int j = 0; j < 5; j++) //從小到大
{ // 外回圈為排序趟數,len個數進行len-1趟
for (int k = 0; k < 5 - i; k++)
{ // 內回圈為每趟比較的次數,第i趟比較len-i次,因為第一次已經將最大的元素冒泡到最后一個位置了
if (bucket[i][k] > bucket[i][k + 1])
{ //相鄰元素比較,逆序則將交換位置
temp = bucket[i][k];
bucket[i][k] = bucket[i][k + 1];
bucket[i][k + 1] = temp;
}
}
}
}
//將桶中排序結果還原到原陣列中
for (i = 0; i < 5; i++)
{
for (j = 0; j < 6; j++)
{
arr[i * 6 + j] = bucket[i][j];
}
}
}
10.基數排序
基本思想
基數排序是一種非比較型整數排序演算法,其原理是將整數按位數切割成不同的數字,然后按每個位數分別比較,由于整數也可以表達字串(比如名字或日期)和特定格式的浮點數,所以基數排序也不是只能使用于整數,
影片
實作
#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結尾的數的個數-以i結尾的數的最大索引+1
for (i = 1; i < BASE; i++)
bucket[i] += bucket[i - 1];
//依據前綴和將原陣列中每一個元素放置在基于技術排列后的位置 并將前綴和減1
for (i = n - 1; i >= 0; i--)
b[--bucket[(a[i] / exp) % BASE]] = a[i];
//復制回原陣列
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;
}
來源:https://blog.csdn.net/weixin_45761327/article/details/105908057
轉載請註明出處,本文鏈接:https://www.uj5u.com/houduan/250439.html
標籤:C
上一篇:編譯lua可執行程式
