冒泡算法的改良詳細完成。本站提示廣大學習愛好者：（冒泡算法的改良詳細完成）文章只能為提供參考，不一定能成為您想要的結果。以下是冒泡算法的改良詳細完成正文
冒泡排序算法的思惟：
起首將第一個記載的症結字和第二個症結字停止比擬，若為逆序則將兩個記載停止交流。
然後比擬第二個記載和第三個記載的症結字，直至第n-1個記載和第n個記載停止比擬為止，一趟事後最年夜的元素會沉入最底部。
然落後行第二趟排序，對前 n-1 個記載停止異樣1、2的操作，成果就是症結字次年夜的記載被支配到n-1地位上。
順次停止第 i 趟排序，對前 n-i 個記載停止異樣的1、2的操作，直到一趟沒有停止過任何比擬的操作，排序停止。
先看一下基本冒泡算法：
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; //現實長度
int size; //分派空間
}SqList, *pSqList;
typedef _SQLIST MergeType;
焦點思惟是每次選出最年夜的數沉入底部，直至沒稀有據可比擬。
起首盤算一下它的時光龐雜度，這裡以最壞的情形來盤算的話：
（n-1）+（n-2）+……+ 1 + 0 = n*（n-1）/ 2 = O(n^2)
最好的情形就是曾經排序好，不須要停止比擬
起首看到其缺乏之一：就是頻仍交流元素。若何防止，可以寄存在一個適合的地位，精簡算法一：
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;
}
看到這裡每次依然須要頻仍的停止賦值操作，固然只是眇乎小哉的，然則賦值也會增長cpu履行的時光，所以精簡算法二:
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;
}
這裡的兩個swap是紛歧樣的，固然也能夠應用一樣的，看以下詳細的完成：
#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;
}
第一個是采取宏調換，固然重要是增長預處置的時光，重要是用宏會湧現意想不到的毛病
第二個是函數，這裡應用了援用，可以削減指針應用的形參變量正本的創立，然則這裡應用了inline，所以照樣調換
測試法式：
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); /*輸出數據*/
BubbleSortEx(&pList);/*冒泡排序*/
PrintList(&pList);/*輸入數據*/
free(pList.elem);
pList.elem = NULL;
return 0;
}
數據輸出：
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;
}
數據輸入：
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;
}
