C語言常見排序算法之交換排序(冒泡排序,快速排序)
前言
本期為大家?guī)淼氖浅Ｒ娕判蛩惴ㄖ械慕粨Q排序，主要有冒泡排序，快速排序，快排分享了三種算法：挖坑法，左右指針法，前后指針法，以及兩種優(yōu)化方式：解決快排最壞情況的“三數(shù)取中”，避免遞歸次數(shù)過多的"小區(qū)間優(yōu)化"，
基本思想：所謂交換，就是根據(jù)序列中兩個記錄鍵值的比較結(jié)果來對換這兩個記錄在序列中的位 置，交換排序的特點是：將鍵值較大的記錄向序列的尾部移動，鍵值較小的記錄向序列的前部移 動。
1.交換排序——冒泡排序
冒泡排序（Bubble Sort）基本思想: 冒泡排序，類似于水中冒泡，較大的數(shù)沉下去，較小的數(shù)慢慢冒起來，假設(shè)從小到大，即為較大的數(shù)慢慢往后排，較小的數(shù)慢慢往前排。直觀表達，每一趟遍歷，將一個最大的數(shù)移到序列末尾。也是一種簡單直觀的排序算法。它重復(fù)地走訪過要排序的數(shù)列，一次比較兩個元素，將他們之間小的，或者大的值交換過來。遍歷數(shù)列的工作是重復(fù)地進行，直到?jīng)]有再需要交換的，也就是說該數(shù)列已經(jīng)排序完成。這個算法的名字由來是因為越小的元素會經(jīng)由交換慢慢"浮"到數(shù)列的頂端。
1.1 算法思想
比較相鄰的元素，如果前一個比后一個大，交換之。
第一趟排序第i個和第i+1個比較與交換，隨后第i+1個和第i+2個一對比較交換，這樣直到倒數(shù)第n-1個和最后n個，將最大的數(shù)移動到最后一位。
第二趟將第二大的數(shù)移動至倒數(shù)第二位……
1.2 動圖演示
算法實現(xiàn)：
#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)化程序，是定義一個變量判斷排序是否在做無效操作，當內(nèi)循環(huán)處于交換狀態(tài)時，則數(shù)據(jù)未排序完畢，否則視為，數(shù)據(jù)已有序，我們就可以break;中止掉程序，避免做無用遍歷。
1.3 冒泡最好的情況
待排序數(shù)列有序時，時間復(fù)雜度是O(N)。外循環(huán)只執(zhí)行一次，內(nèi)循環(huán)N-1,N-2,N-3……
冒泡排序的特性總結(jié)：
- 1. 冒泡排序是一種非常容易理解的排序
- 2. 時間復(fù)雜度：O(N^2)
- 3. 空間復(fù)雜度：O(1)
- 4. 穩(wěn)定
- 性：穩(wěn)定
總結(jié)：
總的來說，冒泡排序是一種可以的排序，比直接選擇排序要好，雖然有優(yōu)化程序，但是，整體算法效率跟其他排序來比，還是差一些，比較適合新手學(xué)習(xí)。
2. 交換排序——快速排序
快速排序(Quicksort)是Hoare于1962年提出的一種二叉樹結(jié)構(gòu)的交換排序方法，有時候也叫做劃分交換排序，是一個高效的算法，其基本思想為：任取待排序 元素序列中的某元素作為基準值，按照該排序碼將待排序集合分割成兩子序列，左子序列中所有 元素均小于基準值，右子序列中所有元素均大于基準值，然后最左右子序列重復(fù)該過程，直到所 有元素都排列在相應(yīng)位置上為止。這是一個分治算法，而且它就在原地交換數(shù)據(jù)排序。
是目前已知最快的排序算法，會比一般的排序更節(jié)省時間。
2.1 快速排序——挖坑法
算法實現(xiàn)：
#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;
}
快排的缺點
根據(jù)上面的代碼，我們來分析一下快排的缺點：
如何解決快排對有序數(shù)據(jù)排序效率很差的方法？
三數(shù)取中法
所謂三數(shù)取中，不是取最大值，最小值，以及他們的中間值，而是取左邊（begin）、右邊（end）和中間（begin+end）/2;
在有序的情況下中間的值剛好就是二分，將取出的值作為坑位，就不會出現(xiàn)最差的這種情況。我們依舊使用區(qū)間的開頭作為“坑值”，但是要使用三數(shù)取中的邏輯。
選坑位：
int begin = left; int end = right; //使用三數(shù)取中選“坑值”，用mid存儲其下標 int mid = GetMidIndex(a, begin, end); //將區(qū)間首值當作坑位 //坑值與首值交換，避免算法混亂 //一般我們會將區(qū)間首值作為坑值 Swap(&a[begin], &a[mid]);//傳地址調(diào)用 //存儲坑值 int key = a[begin];
三數(shù)取中 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;
}經(jīng)過三數(shù)取中的處理，就不會出現(xiàn)快排的最壞情況，但也幾乎不會成為最好的情況，有利有弊，我們在面試的過程中只需要寫基礎(chǔ)版的快排即可，以防時間不夠。
小區(qū)間優(yōu)化：
關(guān)于如果處理數(shù)據(jù)多，相應(yīng)的遞歸次數(shù)多，會不會影響操作快排的性能？
當我們在使用快排對大量數(shù)據(jù)進行排序時，我們可以采用小區(qū)間優(yōu)化，減少遞歸次數(shù)，達到優(yōu)化程序得到目的。
對當待處理數(shù)據(jù)大于10的子序列進行快排遞歸。
對當待處理數(shù)據(jù)低于10的子序列進行直接插入排序進行排序，避免遞歸次數(shù)過多。
這個10不是固定的，可以根據(jù)處理的數(shù)據(jù)量調(diào)整。
//區(qū)間[left,right]
//左區(qū)間[left,pivot-1] 右區(qū)間[pivot+1,right]
//左子區(qū)間和右子區(qū)間有序，我們就有序了，如何讓他們有序？分治遞歸
// 小區(qū)間優(yōu)化
if (pivot - 1 - left > 10)//對當待處理數(shù)據(jù)大于于10的子序列進行快排遞歸排序
{
//快排
QuickSort(a,left,pivot-1);
}
else
{
//采用直接插入排序，對當待處理數(shù)據(jù)低于10的子序列進行排序，避免遞歸
InsertSort(a+left,pivot-1-left+1);//為什么最后要加1,例如：區(qū)間[0,9]實際上有10個數(shù)
}
if (right - (pivot + 1) > 10)
{
QuickSort(a,pivot+1,right);
}
else
{
InsertSort(a + pivot+1, right-(pivot+1)+1);
}如果大家有想了解直接插入排序可以查看博主的另一篇：C語言常見排序算法之插入排序(直接插入排序,希爾排序)
2.3 快速排序——左右指針法
根據(jù)上圖的示例我們應(yīng)該能夠理解左右指針法是什么樣的邏輯，跟挖坑法是一樣的思想，單趟排序完畢實現(xiàn)左邊比坑位小，右邊比坑位大。但是即使左右指針法跟挖坑法的思想是一樣的，但是他們單趟的運算結(jié)果是不一樣的。
算法實現(xiàn)：
void QuickSort(int* a, int left, int right)
{
if (left < right)
{
int begin = left;
int end = right;
//選坑位
int mid = GetMidIndex(a, begin, end);//三數(shù)取中
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位置的值
算法實現(xiàn)：
//左右指針法
void QuickSort(int* a, int left, int right)
{
if (left < right)
{
//選坑位
int mid = GetMidIndex(a, left,right);//三數(shù)取中
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);
}
}
快速排序的特性總結(jié)：
- 1.快速排序整體的綜合性能和使用場景都是比較好的，所以才敢叫快速排序
- 2.時間復(fù)雜度：O(N*logN)
- 3.空間復(fù)雜度：O(logN)
- 4.穩(wěn)定性：不穩(wěn)定
總結(jié)：
快排是我們一定要掌握的一種排序算法，在面試、筆試中也是很常見的，博主分享的三種方法：挖坑法，左右指針法，前后指針法，只少要掌握一種，但是要其他的方法也要知道算法思想。還有兩種優(yōu)化方式，小區(qū)間優(yōu)化和三數(shù)取中，也要知道是什么邏輯，解決什么問題。
到此這篇關(guān)于C語言常見排序算法之交換排序(冒泡排序,快速排序)的文章就介紹到這了,更多相關(guān)C語言交換排序 內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
C++實現(xiàn)插入排序?qū)φ麛?shù)數(shù)組排序
這篇文章主要為大家詳細介紹了C++實現(xiàn)插入排序?qū)φ麛?shù)數(shù)組排序，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-05-05
這篇文章主要介紹了c++中system("pause")的作用和含義，非常不錯，具有參考借鑒價值，需要的朋友參考下吧2018-03-03
fread()函數(shù)用來從指定文件中讀取塊數(shù)據(jù),下面這篇文章主要給大家介紹了關(guān)于C語言文件操作之fread函數(shù)的相關(guān)資料,文中通過實例代碼介紹的非常詳細,需要的朋友可以參考下2022-06-06
這篇文章主要介紹了C++為什么非要引入那幾種類型轉(zhuǎn)換,文中通過示例代碼介紹的非常詳細，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2021-03-03
這篇文章主要為大家詳細介紹了DEVC++實現(xiàn)推箱子小游戲，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-01-01
今天小編就為大家分享一篇關(guān)于關(guān)于C++友元類的實現(xiàn)講解，小編覺得內(nèi)容挺不錯的，現(xiàn)在分享給大家，具有很好的參考價值，需要的朋友一起跟隨小編來看看吧2018-12-12
在本篇文章里小編給大家整理了一篇關(guān)于c/c++內(nèi)存分配大小實例講解內(nèi)容，有需要的朋友們可以跟著學(xué)習(xí)參考下。2021-11-11
今天小編就為大家分享一篇c語言 字符串的拼接和分割實例，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2019-12-12
VTK8.1?在?Qt5.9?環(huán)境下的配置編譯和安裝過程
為了實現(xiàn)realsense的PCL點云顯示，需要VTK支持。由于整個平臺在Qt環(huán)境實現(xiàn)，VTK編譯為Qt插件。整個過程并不復(fù)雜，網(wǎng)上的文章大多不全，自己梳理了一下，分享出來,需要的朋友可以參考下2022-07-07
學(xué)生成績管理系統(tǒng)C語言代碼實現(xiàn)
這篇文章主要為大家詳細介紹了C語言代碼實現(xiàn)學(xué)生成績管理系統(tǒng)，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2018-01-01