冒泡算法的改進(jìn)具體實(shí)現(xiàn)
冒泡排序算法的思想:
首先將第一個(gè)記錄的關(guān)鍵字和第二個(gè)關(guān)鍵字進(jìn)行比較,若為逆序則將兩個(gè)記錄進(jìn)行交換。
然后比較第二個(gè)記錄和第三個(gè)記錄的關(guān)鍵字,直至第n-1個(gè)記錄和第n個(gè)記錄進(jìn)行比較為止,一趟過后最大的元素會(huì)沉入最底部。
然后進(jìn)行第二趟排序,對(duì)前 n-1 個(gè)記錄進(jìn)行同樣1、2的操作,結(jié)果就是關(guān)鍵字次大的記錄被安排到n-1位置上。
依次進(jìn)行第 i 趟排序,對(duì)前 n-i 個(gè)記錄進(jìn)行同樣的1、2的操作,直到一趟沒有進(jìn)行過任何比較的操作,排序結(jié)束。
先看一下基礎(chǔ)冒泡算法:
int BubbleSort(MergeType* L)
{
int i, j;
for (i = 0; i <= L->len-1; i++)
{
for (j = 0; j < L->len-1-i; j++)
{
if (L->elem[j+1] < L->elem[j])
{
SWAP(L->elem[j+1], L->elem[j] );
}
}
}
return 0;
}
這里的MergeType類型如下:
typedef struct _SQLIST{
int* elem;
int len; //實(shí)際長(zhǎng)度
int size; //分配空間
}SqList, *pSqList;
typedef _SQLIST MergeType;
核心思想是每次選出最大的數(shù)沉入底部,直至沒有數(shù)據(jù)可比較。
首先計(jì)算一下它的時(shí)間復(fù)雜度,這里以最壞的情況來計(jì)算的話:
(n-1)+(n-2)+……+ 1 + 0 = n*(n-1)/ 2 = O(n^2)
最好的情況就是已經(jīng)排序好,不需要進(jìn)行比較
首先看到其不足之一:就是頻繁交換元素。如何避免,可以存放在一個(gè)合適的位置,精簡(jiǎn)算法一:
int BubbleSortEx(MergeType* L)
{
int i = 0, j = 0;
int max, temp;
for (i = 0; i <= L->len-1; i++)
{
temp = L->elem[0];
max = 0;
for (j = 1; j < L->len-i; j++)
{
if (L->elem[j] > temp)
{
temp = L->elem[j];
max = j;
}
}
//printf("%d:%d \n", max, temp);
swap(L->elem[L->len-1-i], L->elem[max] );
}
return 0;
}
看到這里每次仍然需要頻繁的進(jìn)行賦值操作,當(dāng)然只是微不足道的,但是賦值也會(huì)增加cpu執(zhí)行的時(shí)間,所以精簡(jiǎn)算法二:
int BubbleSortEx(MergeType* L)
{
int i, j , max;
for (int i = 0; i <= L->len-1; i++)
{
max = 0;
for (j = 1; j < L->len-i; j++)
{
if (L->elem[j] > L->elem[max])
{
max = j;
}
}
//printf("%d:%d \n", max, L->elem[max]);
swap(L->elem[L->len-1-i], L->elem[max] );
}
return 0;
}
這里的兩個(gè)swap是不一樣的,當(dāng)然也可以使用一樣的,看如下具體的實(shí)現(xiàn):
#define SWAP(a, b) \
{ \
int temp = (a); \
(a) = (b); \
(b) = temp; \
}
inline void swap(int& a, int& b)
{
int temp = a;
a = b;
b = temp;
}
第一個(gè)是采用宏替換,當(dāng)然主要是增加預(yù)處理的時(shí)間,主要是用宏會(huì)出現(xiàn)意想不到的錯(cuò)誤
第二個(gè)是函數(shù),這里使用了引用,可以減少指針使用的形參變量副本的創(chuàng)建,但是這里使用了inline,所以還是替換
測(cè)試程序:
int PrintList(MergeType *L);
int ScanfList(MergeType *L, const int nScanfType = -1);
int SortTest()
{
printf("--- %s ---\n", __FUNCTION__);
MergeType pList;
MergeType pT;
pList.elem = (int*)malloc(sizeof(int)*10);
pList.len = 10;
pList.size = 10;
ScanfList(&pList); /*輸入數(shù)據(jù)*/
BubbleSortEx(&pList);/*冒泡排序*/
PrintList(&pList);/*輸出數(shù)據(jù)*/
free(pList.elem);
pList.elem = NULL;
return 0;
}
數(shù)據(jù)輸入:
int ScanfList(MergeType *L, const int nScanfType)
{
if (!L->elem)
{
return -1;
}
printf("Old List\t: ");
for (int i = 0; i <= L->len; i++ )
{
if( i == L->len )
{
printf("\n");
break;
}
switch (nScanfType)
{
case 0:
{
break;
}
default:
L->elem[i] = 11 * i - i * i;
break;
}
printf("%d ", L->elem[i]);
}
return 0;
}
數(shù)據(jù)輸出:
int PrintList(MergeType *L)
{
if (!L->elem)
{
return -1;
}
printf("Sort List\t: ");
for (int i = 0; i <= L->len; i++ )
{
if (i == L->len)
{
printf("\n");
break;
}
printf("%d ", L->elem[i]);
}
return 0;
}
相關(guān)文章
C語(yǔ)言簡(jiǎn)明講解操作符++和--的使用方法
++和--運(yùn)算符分別是+=1和-=1的簡(jiǎn)寫。設(shè)計(jì)這樣兩個(gè)運(yùn)算符的本意是?便程序員,但i++和++i使?不恰當(dāng)有時(shí)候會(huì)造成混淆,反倒令剛?cè)腴T的C程序員有點(diǎn)混亂2022-04-04C語(yǔ)言算法金手指摩爾投票法手撕絕大多數(shù)問題
這篇文章主要為大家介紹了C語(yǔ)言算法之金手指摩爾投票法手撕絕大多數(shù)問題的示例詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助2022-02-02

淺談C++內(nèi)存分配及變長(zhǎng)數(shù)組的動(dòng)態(tài)分配

C語(yǔ)言實(shí)現(xiàn)學(xué)籍管理系統(tǒng)

C++中對(duì)象的動(dòng)態(tài)建立與釋放詳解及其作用介紹