您好,登錄后才能下訂單哦!
這篇文章主要介紹了C語言如何實(shí)現(xiàn)交換排序算法的相關(guān)知識,內(nèi)容詳細(xì)易懂,操作簡單快捷,具有一定借鑒價(jià)值,相信大家閱讀完這篇C語言如何實(shí)現(xiàn)交換排序算法文章都會有所收獲,下面我們一起來看看吧。
對于很多同學(xué)來說冒泡排序是再熟悉不過了,冒泡的思想在于:不斷的比較兩個元素并交換,大的在右邊,小的在左邊;
有一個數(shù)組{5, 1, 4, 2, 8, 4}
第一輪
arr[0] = 5和 arr[1] = 1比較 5 > 1,交換;
arr[2] = 4和 arr[1] = 5比較 5 > 4,交換;
arr[2] = 5和 arr[3] = 2比較 5 > 2,交換;
arr[3] = 5和 arr[4] = 8比較 5 < 8,不交換;
arr[4] = 8和 arr[5] = 4比較 8 > 4,交換;
第二輪
從arr[1]開始重復(fù)上述的步驟;
... ...直到循環(huán) N - 1 次,排序結(jié)束;
#include <stdio.h> #include<stdlib.h> //冒泡排序 void bubbleSort(int a[], int n) { //一共要掃描n-1趟 for(int i = 0; i < n - 1; i++) { //用來比較 交換 for(int j = 0; j < n - i - 1; j++) { if(a[j] > a[j + 1]) { int temp = a[j + 1]; a[j + 1] = a[j]; a[j] = temp; } } } } int main() { int arr[] = {5, 1, 4, 2, 8, 4}; int length = sizeof(arr) / sizeof(arr[0]); bubbleSort(arr, length); for(int i = 0; i < length; i++) { printf("%d", arr[i]); } system("pause"); return 0; }
那么問題來了,問題一:這里我們發(fā)現(xiàn)對于這個數(shù)組而言在第二輪排序就已經(jīng)排好了整體甚至穩(wěn)定的有序,剩下的循環(huán)就相當(dāng)于浪費(fèi)了,那么有沒有一種方法能夠判斷數(shù)組已經(jīng)有序?
還有這樣一個數(shù)組{4, 2, 1, 5, 6, 8}
問題二:我們發(fā)現(xiàn){5, 6, 8}的部分是已經(jīng)有序了的,對于已經(jīng)有序的部分還要繼續(xù)比較,那么能不能確定出有序的部分和無序的部分的邊界呢?
針對問題一,我們可以添加一個標(biāo)志,用來標(biāo)識數(shù)組是否有序:當(dāng)某一輪排序沒有發(fā)生交換,就可以認(rèn)為數(shù)組已經(jīng)有序了;
針對問題二,我們可以記錄冒泡排序的過程中最后一次發(fā)生交換的地方index,如在下圖中index==1,每一次后面的排序只要從第一個到index就可以了;
值得注意的是,不管怎樣去優(yōu)化,最壞情況的時(shí)間復(fù)雜度都是O(n^2),即數(shù)組逆序的情況;
雖然用棧實(shí)現(xiàn)冒泡排序可能在實(shí)際中沒有應(yīng)用場景(也沒必要用),但是可能會有面試的時(shí)候要求用?;蛘咂渌慕Y(jié)構(gòu)去實(shí)現(xiàn)冒泡排序來考查對算法和思想熟練度,所以這里也提供用棧實(shí)現(xiàn)冒泡排序的思路;
void bubbleSort(int a[], int n) { //定義兩個棧S1和S2 stack<int>stk1, stk2; //將數(shù)組中的所有元素入棧S1 for (int i = 0; i < n; i++) { stk1.push(a[i]); } //循環(huán)N次 每一次找出最大的元素(就像真冒泡一樣 最大的元素浮在最上面) for (int i = 0; i < n; i++) { //如果S1不為空 while (!stk1.empty()) { //如果S2為空就把棧S1頂?shù)脑厝霔2 if (stk2.empty()) { stk2.push(stk1.top()); stk1.pop(); } else { int temp = 0;//用于接收需要交換的元素 if (stk1.top() < stk2.top()) { //如果S1的棧頂小于S2的棧頂 把S1的棧頂壓在S2的棧頂下面 temp = stk2.top(); stk2.pop(); stk2.push(stk1.top()); stk1.pop(); stk2.push(temp); } else { stk2.push(stk1.top()); stk1.pop(); } } } //把最大的元素從后往前更新回原數(shù)組中 a[n - i - 1] = stk2.top(); stk2.pop(); //把剩下的元素倒棧 重復(fù) for (int j = stk2.size(); j > 0; j--) { stk1.push(stk2.top()); stk2.pop(); } } }
選取一個基準(zhǔn)(可以認(rèn)為是要放到排序以后正確的位置的元素,可以是第一個元素、最后一個 中間的、隨機(jī)的都可以);
把數(shù)組中的元素做一個劃分,每一趟劃分將作為基準(zhǔn)的值x放到排序后數(shù)組正確的位置,并將所有比x小的放到左邊,比x大的放到右邊;
有一個數(shù)組{1, 8, 3, 9, 4, 5, 4, 7}
假定選擇元素arr[7] = 7為基準(zhǔn),就是要把7放在正確的位置,那么只有兩種情況:
要么7本身就是正確的位置,要么就在前面;
第一步:初始化指針 i = -1,j = 0,把 j 指向的元素和7比較 ,當(dāng)1 < 7,將 i++, 交換 i 和 j 指向的元素,j++;
第二步:把 j 指向的元素和7比較 ,當(dāng)8 > 7,將 j++;
第三步:把 j 指向的元素和7比較 ,當(dāng)3 < 7,將 i++, 交換 i 和 j 指向的元素,j++;
第四步:把 j 指向的元素和7比較 ,當(dāng)4 < 7,將 i++, 交換 i 和 j 指向的元素,j++;
第五步:把 j 指向的元素和7比較 ,當(dāng)5 < 7,將 i++, 交換 i 和 j 指向的元素,j++;
第五步:把 j 指向的元素和7比較 ,當(dāng)4 < 7,將 i++, 交換 i 和 j 指向的元素,j++;
第六步:當(dāng)j到7遍歷結(jié)束,讓i++的位置和7交換,第一趟排序結(jié)束;
如此一來,基準(zhǔn)7就找到了它在數(shù)組中的正確位置,并且把數(shù)組劃分成了兩邊【0,5)和(5,7】這時(shí)再選一個基準(zhǔn)再進(jìn)行上述步驟,如下圖所示:
是不是覺得很眼熟?沒錯這就是一棵二叉樹:
既然是二叉樹,那么排出一棵斜樹自然就是最壞的情況;要緩解這個問題,可以以中間的值為基準(zhǔn)來減少這種情況的發(fā)生;
即復(fù)雜度與數(shù)組長度和基準(zhǔn)的選擇有關(guān),尾基準(zhǔn)是O(n^2)因?yàn)閚趟每一趟劃分需要O(n),而平衡樹是O(nlogn),通過數(shù)學(xué)方法能夠得到更優(yōu)的基準(zhǔn)選擇,但無論選什么為基準(zhǔn)都應(yīng)該能滿足:基準(zhǔn)左邊小、右邊大;
我們之前說過,快速排序其實(shí)是一個不穩(wěn)定排序(不穩(wěn)定的排序就意味著交換的次數(shù)多,如果需要按多條件排序就會亂),而我們又說過任何一個不穩(wěn)定的排序算法都有辦法使其變得穩(wěn)定,用到的是以空間換時(shí)間的思想;
也就是我們可以用一個變量對原來的順序做標(biāo)記;
既然是通過不斷劃分?jǐn)?shù)組來減少比較的次數(shù),這一聽就知道用到了分治的思想,也就是可以用遞歸來實(shí)現(xiàn)代碼:
#include <stdio.h> #include<stdlib.h> //快排 void quickSort(int a[], int low, int high) { if(low < high) { int i = low;//這里以i下標(biāo)的值為基準(zhǔn) int j = high; int k = a[low];//k是用來記錄基準(zhǔn)的值 while(i < j) { //從右往左找第一個比k要小的值 while(i < j && a[j] >= k) { j--; } if(i < j) { a[i++] = a[j]; } //從左往右找第一個比k要大的值 while(i < j && a[i] < k) { i++; } if(i < j) { a[j--] = a[i]; } } a[i] = k; //遞歸 quickSort(a, low, i - 1); quickSort(a, i + 1, high); } } int main() { int arr[] = {1, 8, 3, 9, 4, 5, 4, 7}; int length = sizeof(arr) / sizeof(arr[0]); quickSort(arr, 0, length - 1); for(int i = 0; i < length; i++) { printf("%d ", arr[i]); } system("pause"); return 0; }
運(yùn)行結(jié)果
關(guān)于“C語言如何實(shí)現(xiàn)交換排序算法”這篇文章的內(nèi)容就介紹到這里,感謝各位的閱讀!相信大家對“C語言如何實(shí)現(xiàn)交換排序算法”知識都有一定的了解,大家如果還想學(xué)習(xí)更多知識,歡迎關(guān)注億速云行業(yè)資訊頻道。
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。