柚子快報(bào)邀請(qǐng)碼778899分享：數(shù)據(jù)結(jié)構(gòu)-排序算法篇
柚子快報(bào)邀請(qǐng)碼778899分享：數(shù)據(jù)結(jié)構(gòu)-排序算法篇
前言
? 在我們的生活中有很多東西都是有大小的，那么該如何去排序？假設(shè)有10個(gè)數(shù)字要你去排序，眼睛一掃就看出來了，那100、1000、10000····要怎么去排？下面就為大家介紹各種排序的算法。
內(nèi)容
1.冒泡排序
2.選擇排序
3.插入排序
4.希爾排序
5.快排
6.歸并排序
7.計(jì)數(shù)排序
1.冒泡排序
? ?冒泡排序排序是一種交換排序，第一個(gè)數(shù)與第二個(gè)數(shù)進(jìn)行比較（這里排序都默認(rèn)是升序）如果第二個(gè)數(shù)小于第一個(gè)數(shù)，那就交換這兩數(shù)位置然后第二個(gè)數(shù)再和第三個(gè)數(shù)依次進(jìn)行比較，最后會(huì)將這個(gè)數(shù)組中最大數(shù)移動(dòng)到數(shù)組最后的位置。
圖解
代碼
//冒泡排序
void BubbleSort(int* a, int n)
{
for (int i = 0; i < n; i++)
{
//j //下次排序就不用再比較了可以提高效率 int flang = 1;//假設(shè)已經(jīng)這個(gè)數(shù)組已經(jīng)有序了 for (int j = 0; j < n - i; j++) { if (j + 1 { flang = 0;//進(jìn)入到這里說明數(shù)組還沒有完全有序 Wsap(&a[j + 1], &a[j]); } } //如果flang==1那就說明這個(gè)數(shù)組已經(jīng)有序就可以直接終止循環(huán)提高效率 //防止出現(xiàn) 9 1 2 3 4 5 6 7 8 這種情況可以提升代碼的效率 if (flang == 1) { break; } } } 2.選擇排序 圖解 代碼 // 選擇排序 void SelectSort(int* a, int n) { int min = 0; for (int j = 0; j < n; j++) { min = j; for (int i = j; i < n; i++) { if (a[i] < a[min]) { min = i; } } Wsap(&a[j], &a[min]); } } //優(yōu)化算法 void SelectSortpro(int* a, int n) { int min = 0,max = 0; //用begin和end來控制數(shù)組的左右兩邊 int begin = 0, end = n - 1; while (begin < end) { for (int i = begin; i <= end; i++) { if (a[i] < a[min]) { min = i; } if (a[i] > a[max]) { max = i; } } Wsap(&a[begin], &a[min]); if (a[min] > a[max]) { max = min; } Wsap(&a[end], &a[max]); //每次遍歷之后因?yàn)橐呀?jīng)將此次遍歷的最小和最大放到了兩邊所以需要縮小區(qū)間 begin++; end--; } } 3.插入排序 ? ? ? ? 首先要將數(shù)組分為已排序和未排序兩個(gè)部分，一般需要從第二個(gè)元素開始因?yàn)榈谝粋€(gè)元素只有一個(gè)已經(jīng)有序了。 圖解 代碼 // 插入排序 void InsertSort(int* a, int n) { for (int i = 0; i < n-1; i++) { int begin = 0, end = i; int key = a[end + 1]; while (end >= begin) { if (key < a[end]) { a[end + 1] = a[end]; end--; } //當(dāng)a[end]>key時(shí)就停止循環(huán)這時(shí)end+1的位置是要插入key的位置 else { break; } } //當(dāng)數(shù)組的首元素位置是要插入key的時(shí)候end=-1所以end需要加一才是首元素的位置 a[end + 1] = key; } } 4.希爾排序 圖解 代碼 // 希爾排序 void ShellSort(int* a, int n) { int gap = n; //當(dāng)需要排序的內(nèi)容過多時(shí)不再3組3組的分，需要數(shù)組長度不斷除3來提升效率 //除完加一是保證最后gap除3之后為零時(shí)gap= 1 while (gap > 1) { gap = gap/3+1; for (int i = 0; i < n - gap; i++)//i { int end = i; int key = a[end + gap]; while (end >= 0) { if (key < a[end]) { a[end + gap] = a[end]; end -= gap; } else { break; } } a[end + gap] = key; } } } 5.快排 ? 快排需要借助遞歸來實(shí)現(xiàn)快排的版本有很多圖解中為大家一一敘述，快排的非遞歸需要借助棧來是實(shí)現(xiàn)這里就不過多的敘述了詳細(xì)的思想見圖解。 霍爾版本 ? ?霍爾版本的快排，需要選擇數(shù)組最左邊的值做為key然后定義一個(gè)left和right分別指向最左邊和最右邊的元素然后right先走遍歷數(shù)組找到比key小的數(shù)停止，left遍歷找到比key大的停止然后left和right交換一直到left遇到right或者right遇到left停止，然后交換left或right和key的位置。由key分割數(shù)組的區(qū)間進(jìn)行，遞歸操作。 圖解 代碼 //霍爾版本 int QuickSort1(int* a, int begin, int end) { int key = a[begin], left = begin, right = end, key1 = begin; while (left < right) { while (left < right && a[right] > key)//找比key小的數(shù) { right--; } while (left < right && a[left] <= key)//找比key大的數(shù) { left++; } Wsap(&a[left], &a[right]); } Wsap(&a[left], &a[key1]); return left; } //快排 void QuickSort(int* a, int begin, int end) { if (begin >= end) { return; } int key = QuickSort1(a, begin, end); QuickSort(a, begin, key - 1); QuickSort(a, key+1, end); } 雙指針法 ? 雙指針法的也需要定義一個(gè)key指向數(shù)組最左邊的值，再定義一個(gè)prev和cur，prev指向首元素的位置，cur的指向prev的下一個(gè)元素。 比較key和cur位置的值如果cur下于key那么就交換prev和cur位置的值如果cur大于key那么cur就加加，直到cur=right就結(jié)束。 代碼 //雙指針法 int QuickSort2(int* a, int left, int right) { int prev = left, cur = left + 1, key = left; while (cur <= right) { //++prev != cur 是為了防止prev和cur相等時(shí)交換可以提升效率 if (a[cur] < a[key] && ++prev != cur) { Wsap(&a[cur], &a[prev]); } else { cur++; } } Wsap(&a[key], &a[prev]); return prev; } void QuickSort(int* a, int begin, int end) { if (begin >= end) { return; } int key = QuickSort1(a, begin, end); QuickSort(a, begin, key - 1); QuickSort(a, key+1, end); } 挖坑法 ? 首先定義key存儲(chǔ)首元素，將首元素的位置看做一個(gè)坑定義變量ken，再定義一個(gè)begin，和end用來遍歷數(shù)組，end先遍歷找到比key小的元素就停止，然后讓ken的位置等于end指向的元素再使end位置成為一個(gè)新的坑也就是使ken=end。然后begin開始遍歷找比key大的數(shù)找到后停止再使ken的位置等于begin位置所指向的元素再使begin位置成為新的坑。直到begin和end相遇然后讓begin和end指向的位置等于key。 代碼 //挖坑法 int QuickSort3(int* a, int left, int right) { int ken = left, key = a[left], begin = left, end = right; while (begin < end) { while (a[end] >= key&& begin < end) { end--; } a[ken] = a[end]; ken = end; while (a[begin] <= key&& begin < end) { begin++; } a[ken] = a[begin]; ken = begin; } a[begin] = key; return begin; } //快排 void QuickSort(int* a, int begin, int end) { if (begin >= end) { return; } int key = QuickSort3(a, begin, end); QuickSort(a, begin, key - 1); QuickSort(a, key+1, end); } 快排的優(yōu)化 三數(shù)取中和小區(qū)間優(yōu)化 代碼 //三數(shù)取中 int GetMid(int left, int mid, int end) { if (left > mid) { if (end > left)//end>left>mid { return left; } else if (mid > end) { return mid; } else { return end; } } else//mid>left { if (end > mid)//end>mid>left { return mid; } else if (left > end)//mid>left>end { return left; } else { return end; } } } //快排 void QuickSort(int* a, int begin, int end) { if (begin >= end) { return; } if (end - begin + 1 <= 10) { InsertSort(a, end - begin + 1); } else { int key = QuickSort3(a, begin, end); QuickSort(a, begin, key - 1); QuickSort(a, key + 1, end); } } 6.歸并排序 遞歸版本 ? 歸并的本質(zhì)是分組，將數(shù)組分成兩份一份是有序的另一份也是有序的，然后創(chuàng)建數(shù)組tmp從兩份有序的數(shù)首元素開始遍歷誰小誰就尾插到tmp數(shù)組中，直到兩份數(shù)組都沒有元素。將tmp數(shù)組中的內(nèi)容拷貝到原數(shù)組中。 代碼 //歸并排序 void _MergeSort(int* a, int* tmp, int left, int right) { if (left == right) { return; } int mid = (right + left) / 2; _MergeSort(a, tmp, left, mid); _MergeSort(a, tmp, mid+1, right); int begin1 = left, begin2 = mid+1, end1 = mid, end2 = right; int j = 0; while (begin1 <= end1 && begin2 <= end2) { //誰小誰就尾插到tmp中 if (a[begin1] <= a[begin2]) { tmp[j++] = a[begin1++]; } else { tmp[j++] = a[begin2++]; } } //當(dāng)出現(xiàn)6 7 8 9，2 3 4 5時(shí)6大于第二份中的所有數(shù)時(shí) //我們需要將第一份剩余是數(shù)組繼續(xù)插入到tmp中 while (begin1 <= end1) { tmp[j++] = a[begin1++]; } while (begin2 <= end2) { tmp[j++] = a[begin2++]; } //每次遞歸都要拷貝一次因?yàn)楸举|(zhì)是對(duì)a中的數(shù)據(jù)排序但是現(xiàn)在我們是在tmp使其有序 //所以每次排序完都要拷貝回去使a中也有序 memcpy(a+left, tmp, (right - left + 1)*sizeof(int)); } //歸并排序 void MergeSort(int* a, int n) { //創(chuàng)建數(shù)組tmp int* tmp = malloc(sizeof(int) * n+1); if (tmp == NULL) { perror("tmp fail:"); return; } _MergeSort(a, tmp, 0, n); } 非遞歸版本? ? ? ? ? 當(dāng)遞歸的層度太深的話就會(huì)導(dǎo)致棧溢出的分險(xiǎn)，所以我們需要嘗試不借用遞歸實(shí)現(xiàn)歸并排序。歸并的本質(zhì)是對(duì)數(shù)組進(jìn)行分組比較，最開始的時(shí)候是每組有一個(gè)元素然后每相鄰的兩個(gè)組進(jìn)行比較。1X1歸并2X2歸并4X4歸并直到數(shù)組有序（當(dāng)然也會(huì)出現(xiàn)不能均勻分割的情況，但是3X4依舊可以歸并）。歸并的難點(diǎn)在于怎么樣去控制下標(biāo)進(jìn)行分組，首先對(duì)數(shù)組進(jìn)行1X1的分組定義變量gap=1（gap組）,進(jìn)行遍歷數(shù)組相鄰的兩組進(jìn)行比較，小的就尾插到copy數(shù)組中，然后再將已經(jīng)有序的部分拷貝會(huì)原數(shù)組中這是一次循環(huán)，在這個(gè)循壞外再加上一次循環(huán)用來控制每組元素的個(gè)數(shù)直到整個(gè)數(shù)組有序。 代碼 //歸并非遞歸 void MergeSortNOT(int* a, int n) { //創(chuàng)建coap數(shù)組用于拷貝 int* copy = (int*)malloc(sizeof(int)*(n+1)); if (copy==NULL) { perror("copy fail:"); return; } int gap = 1;//組數(shù) while (gap < n) { for (int i = 0; i < n; i += 2 * gap) { //定義變量分割區(qū)間 int begin1 = i, end1 = i + gap - 1, begin2 = i + gap, end2 = i + 2 * gap - 1; //printf("[%d %d] [%d %d]", begin1, end1, begin2, end2); //防止越界情況的發(fā)生 if (end1 > n) { break; } if (end2 > n) { end2 = n - 1; } int j = 0; while (begin1 <= end1 && begin2 <= end2) { //誰小誰就尾插到tmp中 if (a[begin1] <= a[begin2]) { copy[j++] = a[begin1++]; } else { copy[j++] = a[begin2++]; } } while (begin1 <= end1) { copy[j++] = a[begin1++]; } while (begin2 <= end2) { copy[j++] = a[begin2++]; } memcpy(a+i, copy, (end2-i+1) * sizeof(int)); } gap*=2; printf("\n"); } } 7.計(jì)數(shù)排序 ? 計(jì)數(shù)排序是創(chuàng)建一個(gè)數(shù)組count用來記錄a數(shù)組中元素的出現(xiàn)的個(gè)數(shù)，然后通過數(shù)組下標(biāo)的自然有序使a數(shù)組中的元素出現(xiàn)在正確的位置上，使a有序。 代碼 //計(jì)數(shù)有序 void CountSort(int* a, int n) { //首先找出數(shù)組中的最大，最小值 int max = a[0], min = a[0]; for (int i = 0; i < n; i++) { if (a[i] > max) max = a[i]; if (a[i] < min) min = a[i]; } //創(chuàng)建max-min+1個(gè)空間是為防止出現(xiàn)6 6 6 6 10的情況減少申請(qǐng)的內(nèi)存空間 int* count = calloc((max-min+1),sizeof(int)); if(count==NULL) { perror("count fail::"); } for (int i = 0; i < n; i++) { count[a[i] - min]++; } int b = 0; for (int j = 0; j < (max-min+1); j++) { while (count[j]--) { a[b++] = j + min; } } free(count); } 總結(jié) 本篇章講述了大部分的常用的排序，還有一個(gè)堆排將在二叉樹中詳細(xì)講解。 希望大大多多指點(diǎn)。 記得三連哦！感謝！感謝！感謝！ 柚子快報(bào)邀請(qǐng)碼778899分享：數(shù)據(jù)結(jié)構(gòu)-排序算法篇 推薦文章
本文內(nèi)容根據(jù)網(wǎng)絡(luò)資料整理，出于傳遞更多信息之目的，不代表金鑰匙跨境贊同其觀點(diǎn)和立場。
轉(zhuǎn)載請(qǐng)注明，如有侵權(quán)，聯(lián)系刪除。
Darty跨境電器行
