https://www.cnblogs.com/maluning/p/7944809.html
目錄
正文
簡介
其中排序算法總結(jié)如下：
一.交換排序
交換排序的基本思想都為通過比較兩個數(shù)的大小魁莉，當(dāng)滿足某些條件時(shí)對它進(jìn)行交換從而達(dá)到排序的目的。
1.冒泡排序
基本思想：比較相鄰的兩個數(shù)募胃，如果前者比后者大旗唁，則進(jìn)行交換。每一輪排序結(jié)束痹束，選出一個未排序中最大的數(shù)放到數(shù)組后面检疫。
#include//冒泡排序算法voidbubbleSort(int*arr,int n) {
? ? for(inti =0; i
? ? ? ? for(intj =0; j < n - i -1; j++)
? ? ? ? {
? ? ? ? ? ? //如果前面的數(shù)比后面大，進(jìn)行交換if(arr[j] > arr[j +1]) {
? ? ? ? ? ? ? ? inttemp = arr[j]; arr[j] = arr[j +1]; arr[j +1] = temp;
? ? ? ? ? ? }
? ? ? ? }
}int main() {
? ? intarr[] = {10,6,5,2,3,8,7,4,9,1 };
? ? intn =sizeof(arr) /sizeof(int);
? ? bubbleSort(arr, n);
? ? printf("排序后的數(shù)組為：\n");
? ? for(intj =0; j
? ? ? ? printf("%d ", arr[j]);
? ? printf("\n");
? ? return0;
分析：
最差時(shí)間復(fù)雜度為O(n^2),平均時(shí)間復(fù)雜度為O(n^2)祷嘶。穩(wěn)定性：穩(wěn)定屎媳。輔助空間O(1)。
升級版冒泡排序法：通過從低到高選出最大的數(shù)放到后面抹蚀，再從高到低選出最小的數(shù)放到前面剿牺，如此反復(fù)企垦，直到左邊界和右邊界重合瓣铣。當(dāng)數(shù)組中有已排序好的數(shù)時(shí)酱固，這種排序比傳統(tǒng)冒泡排序性能稍好。
#include//升級版冒泡排序算法voidbubbleSort_1(int*arr,int n) {
? ? //設(shè)置數(shù)組左右邊界intleft =0, right = n -1;
? ? //當(dāng)左右邊界未重合時(shí)，進(jìn)行排序while(left
? ? ? ? //從左到右遍歷選出最大的數(shù)放到數(shù)組右邊f(xié)or(inti =left; i < right; i++)
? ? ? ? {
? ? ? ? ? ? if(arr[i] > arr[i +1])
? ? ? ? ? ? {
? ? ? ? ? ? ? ? inttemp = arr[i]; arr[i] = arr[i +1]; arr[i +1] = temp;
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? right--;
? ? ? ? //從右到左遍歷選出最小的數(shù)放到數(shù)組左邊f(xié)or(intj = right;j> left; j--)
? ? ? ? {
? ? ? ? ? ? if(arr[j +1] < arr[j])
? ? ? ? ? ? {
? ? ? ? ? ? ? ? inttemp = arr[j]; arr[j] = arr[j +1]; arr[j +1] = temp;
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? left++;
? ? }
}int main() {
? ? intarr[] = {10,6,5,2,3,8,7,4,9,1 };
? ? intn =sizeof(arr) /sizeof(int);
? ? bubbleSort_1(arr, n);
? ? printf("排序后的數(shù)組為：\n");
? ? for(intj =0; j
? ? ? ? printf("%d ", arr[j]);
? ? printf("\n");
? ? return0;
}
2.快速排序
基本思想:選取一個基準(zhǔn)元素缕坎，通常為數(shù)組最后一個元素（或者第一個元素）。從前向后遍歷數(shù)組妈倔，當(dāng)遇到小于基準(zhǔn)元素的元素時(shí)及志，把它和左邊第一個大于基準(zhǔn)元素的元素進(jìn)行交換。在利用分治策略從已經(jīng)分好的兩組中分別進(jìn)行以上步驟朵诫，直到排序完成辛友。下圖表示了這個過程。
#includevoidswap(int*x,int*y) {
? ? inttmp = *x;
? ? *x = *y;
? ? *y = tmp;
}//分治法把數(shù)組分成兩份intpatition(int*a,intleft,int right) {
? ? intj = left;//用來遍歷數(shù)組inti = j -1;//用來指向小于基準(zhǔn)元素的位置intkey = a[right];//基準(zhǔn)元素
? ? //從左到右遍歷數(shù)組，把小于等于基準(zhǔn)元素的放到左邊废累，大于基準(zhǔn)元素的放到右邊f(xié)or(; j < right; ++j) {
? ? ? ? if(a[j] <= key)
? ? ? ? ? ? swap(&a[j], &a[++i]);
? ? }
? ? //把基準(zhǔn)元素放到中間swap(&a[right], &a[++i]);
? ? //返回?cái)?shù)組中間位置return i;
}//快速排序voidquickSort(int*a,intleft,int right) {
? ? if(left>=right)
? ? ? ? return;
? ? intmid = patition(a,left,right);
? ? quickSort(a, left, mid -1);
? ? quickSort(a, mid +1, right);
}int main() {
? ? inta[] = {10,6,5,7,12,8,1,3,11,4,2,9,16,13,15,14 };
? ? intn =sizeof(a) /sizeof(int);
? ? quickSort(a, 0,n-1);
? ? printf("排序好的數(shù)組為：");
? ? for(intl =0; l < n; l++) {
? ? ? ? printf("%d ", a[l]);
? ? }
? ? printf("\n");
? ? return0;
}
分析：
最差時(shí)間復(fù)雜度：每次選取的基準(zhǔn)元素都為最大（或最小元素）導(dǎo)致每次只劃分了一個分區(qū)邓梅，需要進(jìn)行n-1次劃分才能結(jié)束遞歸，故復(fù)雜度為O(n^2)邑滨；最優(yōu)時(shí)間復(fù)雜度：每次選取的基準(zhǔn)元素都是中位數(shù)日缨，每次都劃分出兩個分區(qū)，需要進(jìn)行l(wèi)ogn次遞歸掖看，故時(shí)間復(fù)雜度為O(nlogn)匣距；平均時(shí)間復(fù)雜度：O(nlogn)。穩(wěn)定性：不穩(wěn)定的哎壳。輔助空間：O(nlogn)毅待。
當(dāng)數(shù)組元素基本有序時(shí)，快速排序?qū)]有任何優(yōu)勢归榕，基本退化為冒泡排序恩静，可在選取基準(zhǔn)元素時(shí)選取中間值進(jìn)行優(yōu)化。
二.插入排序
1.直接插入排序
基本思想：和交換排序不同的是它不用進(jìn)行交換操作蹲坷，而是用一個臨時(shí)變量存儲當(dāng)前值驶乾。當(dāng)前面的元素比后面大時(shí)，先把后面的元素存入臨時(shí)變量循签，前面元素的值放到后面元素位置级乐，再到最后把其值插入到合適的數(shù)組位置。
#includevoidInsertSort(int*a,int n) {
? ? inttmp =0;
? ? for(inti =1; i < n; i++) {
? ? ? ? intj = i -1;
? ? ? ? if(a[i] < a[j]) {
? ? ? ? ? ? tmp = a[i];
? ? ? ? ? ? a[i] = a[j];
? ? ? ? ? ? while(tmp < a[j-1]) {
? ? ? ? ? ? ? ? a[j] = a[j-1];
? ? ? ? ? ? ? ? j--;
? ? ? ? ? ? }
? ? ? ? ? ? a[j] = tmp;
? ? ? ? }
? ? }
}int main() {
? ? inta[] = {11,7,9,22,10,18,4,43,5,1,32};
? ? intn =sizeof(a)/sizeof(int);
? ? InsertSort(a, n);
? ? printf("排序好的數(shù)組為：");
? ? for(inti =0; i < n; i++) {
? ? ? ? printf(" %d", a[i]);
? ? }
? ? printf("\n");
? ? return0;
}
?分析：
最壞時(shí)間復(fù)雜度為數(shù)組為逆序時(shí)县匠，為O(n^2)风科。最優(yōu)時(shí)間復(fù)雜度為數(shù)組正序時(shí)，為O(n)乞旦。平均時(shí)間復(fù)雜度為O(n^2)贼穆。輔助空間O(1)。穩(wěn)定性：穩(wěn)定兰粉。
2.希爾(shell)排序
基本思想為在直接插入排序的思想下設(shè)置一個最小增量dk,剛開始dk設(shè)置為n/2故痊。進(jìn)行插入排序，隨后再讓dk=dk/2,再進(jìn)行插入排序玖姑，直到dk為1時(shí)完成最后一次插入排序愕秫，此時(shí)數(shù)組完成排序。
#include//? ? 進(jìn)行插入排序//? ? 初始時(shí)從dk開始增長焰络，每次比較步長為dkvoidInsrtsort(int*a,intn,int dk) {
? ? for(inti = dk; i < n; ++i) {
? ? ? ? intj = i - dk;
? ? ? ? if(a[i] < a[j]) {//? ? 比較前后數(shù)字大小inttmp = a[i];//? ? 作為臨時(shí)存儲? ? a[i] = a[j];
? ? ? ? ? ? while(a[j] > tmp) {//? ? 尋找tmp的插入位置a[j+dk] = a[j];
? ? ? ? ? ? ? ? j -= dk;
? ? ? ? ? ? }
? ? ? ? ? ? a[j+dk] = tmp;//? ? 插入tmp? ? ? ? }
? ? }
}voidShellSort(int*a,int n) {
? ? intdk = n /2;//? ? 設(shè)置初始dkwhile(dk >=1) {
? ? ? ? Insrtsort(a, n, dk);
? ? ? ? dk /=2;
? ? }
}int main() {
? ? inta[] = {5,12,35,42,11,2,9,41,26,18,4 };
? ? intn =sizeof(a) /sizeof(int);
? ? ShellSort(a, n);
? ? printf("排序好的數(shù)組為：");
? ? for(intj =0; j < n; j++) {
? ? ? ? printf("%d ", a [j]);
? ? }
? ? return0;
}
分析：
最壞時(shí)間復(fù)雜度為O(n^2)戴甩；最優(yōu)時(shí)間復(fù)雜度為O(n)；平均時(shí)間復(fù)雜度為O(n^1.3)闪彼。輔助空間O(1)甜孤。穩(wěn)定性：不穩(wěn)定。希爾排序的時(shí)間復(fù)雜度與選取的增量有關(guān)，選取合適的增量可減少時(shí)間復(fù)雜度缴川。
三.選擇排序
1.直接選擇排序
基本思想：依次選出數(shù)組最小的數(shù)放到數(shù)組的前面囱稽。首先從數(shù)組的第二個元素開始往后遍歷，找出最小的數(shù)放到第一個位置二跋。再從剩下數(shù)組中找出最小的數(shù)放到第二個位置战惊。以此類推，直到數(shù)組有序扎即。
#includevoidSelectSort(int*a,int n) {
? ? for(inti =0; i < n; i++)
? ? {
? ? ? ? intkey = i;//? ? 臨時(shí)變量用于存放數(shù)組最小值的位置for(intj = i +1; j < n; j++) {
? ? ? ? ? ? if(a[j] < a[key]) {? ?
? ? ? ? ? ? ? ? key = j;//? ? 記錄數(shù)組最小值位置? ? ? ? ? ? }
? ? ? ? }
? ? ? ? ? ? if(key != i)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? inttmp = a[key]; a[key] = a[i]; a[i] = tmp;//? ? 交換最小值? ? ? ? ? ? }
? ? }
}int main() {
? ? inta[] = {12,4,15,2,6,22,8,10,1,33,45,24,7 };
? ? intn =sizeof(a) /sizeof(int);
? ? SelectSort(a, n);
? ? printf("排序好的數(shù)組為： ");
? ? for(intk =0; k < n; k++)
? ? ? ? printf("%d ", a[k]);
? ? printf("\n");
? ? return0;
}
分析：
最差吞获、最優(yōu)、平均時(shí)間復(fù)雜度都為O(n^2)谚鄙。輔助空間為O(1)各拷。穩(wěn)定性：不穩(wěn)定。
2.堆(Heap)排序
基本思想：先把數(shù)組構(gòu)造成一個大頂堆（父親節(jié)點(diǎn)大于其子節(jié)點(diǎn)）闷营，然后把堆頂（數(shù)組最大值烤黍，數(shù)組第一個元素）和數(shù)組最后一個元素交換，這樣就把最大值放到了數(shù)組最后邊傻盟。把數(shù)組長度n-1,再進(jìn)行構(gòu)造堆速蕊，把剩余的第二大值放到堆頂，輸出堆頂(放到剩余未排序數(shù)組最后面)娘赴。依次類推规哲，直至數(shù)組排序完成。
下圖為堆結(jié)構(gòu)及其在數(shù)組中的表示诽表“π浚可以知道堆頂?shù)脑貫閿?shù)組的首元素，某一個節(jié)點(diǎn)的左孩子節(jié)點(diǎn)為其在數(shù)組中的位置*2竿奏，其右孩子節(jié)點(diǎn)為其在數(shù)組中的位置*2+1袄简，其父節(jié)點(diǎn)為其在數(shù)組中的位置/2（假設(shè)數(shù)組從1開始計(jì)數(shù)）。
下圖為怎么把一個無序的數(shù)組構(gòu)造成一個大堆頂結(jié)構(gòu)的數(shù)組的過程泛啸，注意其是從下到上绿语，從右到左，從右邊第一個非葉子節(jié)點(diǎn)開始構(gòu)建的平痰。
#include// 創(chuàng)建大堆頂汞舱，i為當(dāng)節(jié)點(diǎn)伍纫，n為堆的大小//? ? 從第一個非葉子結(jié)點(diǎn)i從下至上宗雇，從右至左調(diào)整結(jié)構(gòu)//? ? 從兩個兒子節(jié)點(diǎn)中選出較大的來與父親節(jié)點(diǎn)進(jìn)行比較//? ? 如果兒子節(jié)點(diǎn)比父親節(jié)點(diǎn)大，則進(jìn)行交換voidCreatHeap(inta[],inti,int? n) {
? ? //? ? 注意數(shù)組是從0開始計(jì)數(shù)莹规，所以左節(jié)點(diǎn)為2*i+1赔蒲，右節(jié)點(diǎn)為2*i+2for(; i >=0; --i)
? ? {
? ? ? ? intleft = i *2+1;//左子樹節(jié)點(diǎn)intright = i *2+2;//右子樹節(jié)點(diǎn)intj =0;
? ? ? ? //選出左右子節(jié)點(diǎn)中最大的if(right < n) {
? ? ? ? ? ? a[left] > a[right] ? j= left : j = right;
? ? ? ? }
? ? ? ? else? ? ? ? ? ? j = left;
? ? ? ? //交換子節(jié)點(diǎn)與父節(jié)點(diǎn)if(a[j] > a[i]) {
? ? ? ? ? ? inttmp = a[i];
? ? ? ? ? ? a[i] = a[j];
? ? ? ? ? ? a[j] = tmp;
? ? ? ? }
? ? }
}//? ? 進(jìn)行堆排序，依次選出最大值放到最后面voidHeapSort(inta[],int n) {
? ? //初始化構(gòu)造堆CreatHeap(a, n/2-1, n);
//交換第一個元素和最后一個元素后，堆的大小減1
? ? for(intj = n-1; j >=0; j--) {
? ? ? ? //最后一個元素和第一個元素進(jìn)行交換inttmp = a[0];
? ? ? ? a[0] = a[j];
? ? ? ? a[j] = tmp;
? ? ? ? inti = j /2-1;
? ? ? ? CreatHeap(a, i, j);
? ? }
}int main() {
? ? inta[] = {10,6,5,7,12,8,1,3,11,4,2,9,16,13,15,14 };
? ? intn =sizeof(a) /sizeof(int);
? ? HeapSort(a, n);
? ? printf("排序好的數(shù)組為：");
? ? for(intl =0; l < n; l++) {
? ? ? ? printf("%d ", a[l]);
? ? }
? ? printf("\n");
? ? return0;
}
分析：
最差舞虱、最優(yōu)‘平均時(shí)間復(fù)雜度都為O(nlogn)欢际，其中堆的每次創(chuàng)建重構(gòu)花費(fèi)O(lgn)，需要創(chuàng)建n次矾兜。輔助空間O（1）损趋。穩(wěn)定性：不穩(wěn)定。
四.歸并排序
基本思想：歸并算法應(yīng)用到分治策略椅寺，簡單說就是把一個答問題分解成易于解決的小問題后一個個解決浑槽，最后在把小問題的一步步合并成總問題的解。這里的排序應(yīng)用遞歸來把數(shù)組分解成一個個小數(shù)組返帕，直到小數(shù)組的數(shù)位有序桐玻，在把有序的小數(shù)組兩兩合并而成有序的大數(shù)組。
下圖為展示如何歸并的合成一個數(shù)組荆萤。
下圖展示了歸并排序過程各階段的時(shí)間花費(fèi)镊靴。
#include #include // 合并兩個已排好序的數(shù)組voidMerge(inta[],intleft,intmid,int right)
{
? ? intlen = right - left +1;//? ? 數(shù)組的長度int*temp =newint[len];// 分配個臨時(shí)數(shù)組intk =0;
? ? inti = left;// 前一數(shù)組的起始元素intj = mid +1;// 后一數(shù)組的起始元素while(i <= mid && j <= right)
? ? {
? ? ? ? //? ? 選擇較小的存入臨時(shí)數(shù)組temp[k++] = a[i] <= a[j] ? a[i++] : a[j++];?
? ? }
? ? while(i <= mid)
? ? {
? ? ? ? temp[k++] = a[i++];
? ? }
? ? while(j <= right)
? ? {
? ? ? ? temp[k++] = a[j++];
? ? }
? ? for(intk =0; k < len; k++)
? ? {
? ? ? ? a[left++] = temp[k];
? ? }
}// 遞歸實(shí)現(xiàn)的歸并排序voidMergeSort(inta[],intleft,int right)?
{
? ? if(left == right)? ?
? ? ? ? return;
? ? intmid = (left + right) /2;
? ? MergeSort(a, left, mid);
? ? MergeSort(a, mid +1, right);
? ? Merge(a, left, mid, right);
}int main() {
? ? inta[] = {5,1,9,2,8,7,10,3,4,0,6 };
? ? intn =sizeof(a) /sizeof(int);
? ? MergeSort(a, 0, n -1);
? ? printf("排序好的數(shù)組為：");
? ? for(intk =0; k < n; ++k)
? ? ? ? printf("%d ", a[k]);
? ? printf("\n");
? ? return0;
}
分析：
最差、最優(yōu)链韭、平均時(shí)間復(fù)雜度都為O(nlogn)偏竟，其中遞歸樹共有l(wèi)gn+1層，每層需要花費(fèi)O(n)敞峭。輔助空間O(n)苫耸。穩(wěn)定性：穩(wěn)定。
