C語言常見排序算法之交換排序(冒泡排序,快速排序)
前言
本期為大家?guī)淼氖浅R娕判蛩惴ㄖ械慕粨Q排序,主要有冒泡排序,快速排序,快排分享了三種算法:挖坑法,左右指針法,前后指針法,以及兩種優(yōu)化方式:解決快排最壞情況的“三數取中”,避免遞歸次數過多的"小區(qū)間優(yōu)化",
基本思想:所謂交換,就是根據序列中兩個記錄鍵值的比較結果來對換這兩個記錄在序列中的位 置,交換排序的特點是:將鍵值較大的記錄向序列的尾部移動,鍵值較小的記錄向序列的前部移 動。
1.交換排序——冒泡排序
冒泡排序(Bubble Sort)基本思想: 冒泡排序,類似于水中冒泡,較大的數沉下去,較小的數慢慢冒起來,假設從小到大,即為較大的數慢慢往后排,較小的數慢慢往前排。直觀表達,每一趟遍歷,將一個最大的數移到序列末尾。也是一種簡單直觀的排序算法。它重復地走訪過要排序的數列,一次比較兩個元素,將他們之間小的,或者大的值交換過來。遍歷數列的工作是重復地進行,直到沒有再需要交換的,也就是說該數列已經排序完成。這個算法的名字由來是因為越小的元素會經由交換慢慢"浮"到數列的頂端。
1.1 算法思想
比較相鄰的元素,如果前一個比后一個大,交換之。
第一趟排序第i個和第i+1個比較與交換,隨后第i+1個和第i+2個一對比較交換,這樣直到倒數第n-1個和最后n個,將最大的數移動到最后一位。
第二趟將第二大的數移動至倒數第二位……
1.2 動圖演示
算法實現:
#define _CRT_SECURE_NO_WARNINGS #include<stdio.h> #define N 10 Swap(int *p1, int * p2) { int tmp = *p1; *p1 = *p2; *p2 = tmp; } void Print(int *a) { for (int i=0;i<N;i++) { printf("%d ",a[i]); } } void BubbleSort(int* a, int n) { for (int j=0;j<n;++j) { int size = 0; for (int i=1;i<N-j;++i) { if (a[i-1]>a[i]) { Swap(&a[i-1],&a[i]); size =1; } } if (size==0) { break; } } } int main() { int a[N] = {0}; for (int i=0;i<N;++i) { a[i] = rand(); } BubbleSort(a,N); Print(a); return 0; }
其中有一段優(yōu)化程序,是定義一個變量判斷排序是否在做無效操作,當內循環(huán)處于交換狀態(tài)時,則數據未排序完畢,否則視為,數據已有序,我們就可以break;中止掉程序,避免做無用遍歷。
1.3 冒泡最好的情況
待排序數列有序時,時間復雜度是O(N)。外循環(huán)只執(zhí)行一次,內循環(huán)N-1,N-2,N-3……
冒泡排序的特性總結:
- 1. 冒泡排序是一種非常容易理解的排序
- 2. 時間復雜度:O(N^2)
- 3. 空間復雜度:O(1)
- 4. 穩(wěn)定
- 性:穩(wěn)定
總結:
總的來說,冒泡排序是一種可以的排序,比直接選擇排序要好,雖然有優(yōu)化程序,但是,整體算法效率跟其他排序來比,還是差一些,比較適合新手學習。
2. 交換排序——快速排序
快速排序(Quicksort)是Hoare于1962年提出的一種二叉樹結構的交換排序方法,有時候也叫做劃分交換排序,是一個高效的算法,其基本思想為:任取待排序 元素序列中的某元素作為基準值,按照該排序碼將待排序集合分割成兩子序列,左子序列中所有 元素均小于基準值,右子序列中所有元素均大于基準值,然后最左右子序列重復該過程,直到所 有元素都排列在相應位置上為止。這是一個分治算法,而且它就在原地交換數據排序。
是目前已知最快的排序算法,會比一般的排序更節(jié)省時間。
2.1 快速排序——挖坑法
算法實現:
#define _CRT_SECURE_NO_WARNINGS #include<stdio.h> //打印 void Print(int *a,int n) { for (int i=0;i<n;++i) { printf("%d ",a[i]); } } //挖坑法 void QuickSort(int* a,int left,int right)//升序 { if (left < right) { int begin = left; int end = right; int pivot = begin;//記錄坑位的下標 int key = a[begin];//坑值 while (begin < end) { //右邊找小,放到左邊 while (begin < end && a[end] >= key)//與坑值比較 { --end; } //小的放在左邊的坑里,自己形成了新的坑位 a[pivot] = a[end]; pivot = end; //左邊找大,放在右邊 while (begin < end && a[begin] <= key)//與坑值比較 { ++begin; } //大的放在右邊的坑里,自己形成了新的坑位 a[pivot] = a[begin]; pivot = begin; } //最后將坑值給到坑位 a[pivot] = key; //[left,right] //[left,pivot-1] [pivot+1,right] //左子區(qū)間和右子區(qū)間有序,我們就有序了,如何讓他們有序?分治遞歸 QuickSort(a, left, pivot - 1); QuickSort(a, pivot + 1, right); } else { return; } } int main() { int a[10] = {0,9,5,6,3,2,1,7,8,4}; //挖坑法 QuickSort(a,0,sizeof(a)/sizeof(a[0])-1); //打印 Print(a,sizeof(a) / sizeof(a[0])); return 0; }
快排的缺點
根據上面的代碼,我們來分析一下快排的缺點:
如何解決快排對有序數據排序效率很差的方法?
三數取中法
所謂三數取中,不是取最大值,最小值,以及他們的中間值,而是取左邊(begin)、右邊(end)和中間(begin+end)/2;
在有序的情況下中間的值剛好就是二分,將取出的值作為坑位,就不會出現最差的這種情況。我們依舊使用區(qū)間的開頭作為“坑值”,但是要使用三數取中的邏輯。
選坑位:
int begin = left; int end = right; //使用三數取中選“坑值”,用mid存儲其下標 int mid = GetMidIndex(a, begin, end); //將區(qū)間首值當作坑位 //坑值與首值交換,避免算法混亂 //一般我們會將區(qū)間首值作為坑值 Swap(&a[begin], &a[mid]);//傳地址調用 //存儲坑值 int key = a[begin];
三數取中 GetMidIndex();
int GetMidIndex(int *a,int left,int right) { //二分 int mid = (right - left) / 2; if (a[left]<a[mid]) { if (a[left]<a[right]) { if (a[mid]<a[right]) { return mid; } else //a[mid]>=a[right] { return right; } } else //a[left]>=a[right] { return left; } } else //a[left]>=a[mid] { if (a[mid]<a[right]) { if (a[left]<a[right]) { return left; } else //a[left]>=a[right] { return right; } } else //a[mid]>=a[right] { return mid; } } }
交換Swap();
//交換 void Swap(int* p1, int*p2) { int tmp = *p1; *p1 = *p2; *p2 = tmp; }
經過三數取中的處理,就不會出現快排的最壞情況,但也幾乎不會成為最好的情況,有利有弊,我們在面試的過程中只需要寫基礎版的快排即可,以防時間不夠。
小區(qū)間優(yōu)化:
關于如果處理數據多,相應的遞歸次數多,會不會影響操作快排的性能?
當我們在使用快排對大量數據進行排序時,我們可以采用小區(qū)間優(yōu)化,減少遞歸次數,達到優(yōu)化程序得到目的。
對當待處理數據大于10的子序列進行快排遞歸。
對當待處理數據低于10的子序列進行直接插入排序進行排序,避免遞歸次數過多。
這個10不是固定的,可以根據處理的數據量調整。
//區(qū)間[left,right] //左區(qū)間[left,pivot-1] 右區(qū)間[pivot+1,right] //左子區(qū)間和右子區(qū)間有序,我們就有序了,如何讓他們有序?分治遞歸 // 小區(qū)間優(yōu)化 if (pivot - 1 - left > 10)//對當待處理數據大于于10的子序列進行快排遞歸排序 { //快排 QuickSort(a,left,pivot-1); } else { //采用直接插入排序,對當待處理數據低于10的子序列進行排序,避免遞歸 InsertSort(a+left,pivot-1-left+1);//為什么最后要加1,例如:區(qū)間[0,9]實際上有10個數 } if (right - (pivot + 1) > 10) { QuickSort(a,pivot+1,right); } else { InsertSort(a + pivot+1, right-(pivot+1)+1); }
如果大家有想了解直接插入排序可以查看博主的另一篇:C語言常見排序算法之插入排序(直接插入排序,希爾排序)
2.3 快速排序——左右指針法
根據上圖的示例我們應該能夠理解左右指針法是什么樣的邏輯,跟挖坑法是一樣的思想,單趟排序完畢實現左邊比坑位小,右邊比坑位大。但是即使左右指針法跟挖坑法的思想是一樣的,但是他們單趟的運算結果是不一樣的。
算法實現:
void QuickSort(int* a, int left, int right) { if (left < right) { int begin = left; int end = right; //選坑位 int mid = GetMidIndex(a, begin, end);//三數取中 Swap(&a[begin], &a[mid]); int key = begin; while (begin < end) { while (begin < end && a[end] <= a[key]) --end; while (begin < end && a[begin] >= a[key]) ++begin; Swap(&a[begin], &a[end]); } Swap(&a[begin], &a[key]); //分治遞歸 QuickSort(a, left, begin - 1); QuickSort(a, begin + 1, right); } }
2.4 前后指針法
- 采用perv記錄區(qū)間第一個元素的下標,采用cur記錄區(qū)間第二個元素的下標。
- cur找小,每次遇到比key(坑值)小的值就停下來,++prev。
- 交換prev和cur位置的值
算法實現:
//左右指針法 void QuickSort(int* a, int left, int right) { if (left < right) { //選坑位 int mid = GetMidIndex(a, left,right);//三數取中 Swap(&a[left], &a[mid]); int key = left; //初始化指向 int prev = left, cur = left + 1; while (cur<=right) { if (a[cur] <= a[key])//&&++prev!=cur { ++prev; //避免無效操作 if(cur!=prev) Swap(&a[prev],&a[cur]); } ++cur; } Swap(&a[key], &a[prev]); //分治遞歸 QuickSort(a, left, prev - 1); QuickSort(a, prev + 1, right); } }
快速排序的特性總結:
- 1.快速排序整體的綜合性能和使用場景都是比較好的,所以才敢叫快速排序
- 2.時間復雜度:O(N*logN)
- 3.空間復雜度:O(logN)
- 4.穩(wěn)定性:不穩(wěn)定
總結:
快排是我們一定要掌握的一種排序算法,在面試、筆試中也是很常見的,博主分享的三種方法:挖坑法,左右指針法,前后指針法,只少要掌握一種,但是要其他的方法也要知道算法思想。還有兩種優(yōu)化方式,小區(qū)間優(yōu)化和三數取中,也要知道是什么邏輯,解決什么問題。
到此這篇關于C語言常見排序算法之交換排序(冒泡排序,快速排序)的文章就介紹到這了,更多相關C語言交換排序 內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家!