欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

冒泡算法的改進具體實現(xiàn)

 更新時間:2013年12月25日 16:51:29   作者:  
這篇文章主要介紹了冒泡算法的改進具體實現(xiàn),有需要的朋友可以參考一下

冒泡排序算法的思想:

首先將第一個記錄的關(guān)鍵字和第二個關(guān)鍵字進行比較,若為逆序則將兩個記錄進行交換。
然后比較第二個記錄和第三個記錄的關(guān)鍵字,直至第n-1個記錄和第n個記錄進行比較為止,一趟過后最大的元素會沉入最底部。
然后進行第二趟排序,對前 n-1 個記錄進行同樣1、2的操作,結(jié)果就是關(guān)鍵字次大的記錄被安排到n-1位置上。
依次進行第 i 趟排序,對前 n-i 個記錄進行同樣的1、2的操作,直到一趟沒有進行過任何比較的操作,排序結(jié)束。
先看一下基礎(chǔ)冒泡算法:

復(fù)制代碼 代碼如下:

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類型如下:

復(fù)制代碼 代碼如下:

typedef struct _SQLIST{
    int* elem;
    int len;   //實際長度
    int size;  //分配空間
}SqList, *pSqList;

typedef _SQLIST MergeType;

核心思想是每次選出最大的數(shù)沉入底部,直至沒有數(shù)據(jù)可比較。

首先計算一下它的時間復(fù)雜度,這里以最壞的情況來計算的話:

(n-1)+(n-2)+……+ 1 + 0 = n*(n-1)/ 2  = O(n^2)

最好的情況就是已經(jīng)排序好,不需要進行比較
首先看到其不足之一:就是頻繁交換元素。如何避免,可以存放在一個合適的位置,精簡算法一:

復(fù)制代碼 代碼如下:

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;
}

看到這里每次仍然需要頻繁的進行賦值操作,當(dāng)然只是微不足道的,但是賦值也會增加cpu執(zhí)行的時間,所以精簡算法二:

復(fù)制代碼 代碼如下:

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是不一樣的,當(dāng)然也可以使用一樣的,看如下具體的實現(xiàn):

復(fù)制代碼 代碼如下:

#define SWAP(a, b) \
{                 \
 int temp = (a); \
 (a) = (b);        \
 (b) = temp;     \
}

復(fù)制代碼 代碼如下:

inline void swap(int& a, int& b)
{
 int temp = a;
 a = b;
 b = temp;
}

第一個是采用宏替換,當(dāng)然主要是增加預(yù)處理的時間,主要是用宏會出現(xiàn)意想不到的錯誤
第二個是函數(shù),這里使用了引用,可以減少指針使用的形參變量副本的創(chuàng)建,但是這里使用了inline,所以還是替換

測試程序:

復(fù)制代碼 代碼如下:

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ù)輸入:

復(fù)制代碼 代碼如下:

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ù)輸出:

復(fù)制代碼 代碼如下:

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++內(nèi)存分配及變長數(shù)組的動態(tài)分配

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

    下面小編就為大家?guī)硪黄獪\談C++內(nèi)存分配及變長數(shù)組的動態(tài)分配。小編覺得挺不錯的,現(xiàn)在就分享給大家,也給大家做個參考。一起跟隨小編過來看看吧
    2016-09-09
  • C語言實現(xiàn)學(xué)籍管理系統(tǒng)

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

    這篇文章主要為大家詳細介紹了C語言實現(xiàn)學(xué)籍管理系統(tǒng),文中示例代碼介紹的非常詳細,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2022-03-03
  • C++中對象的動態(tài)建立與釋放詳解及其作用介紹

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

    這篇文章主要介紹了C++中對象的動態(tài)建立與釋放詳解及其作用介紹,本文給大家介紹的非常詳細,對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值,需要的朋友可以參考下
    2021-09-09
  • 一篇文章教你在C++中操作符可分為哪幾種類和用法

    一篇文章教你在C++中操作符可分為哪幾種類和用法

    這篇文章主要介紹了C++編程中操作符的種類和用法,是C++入門學(xué)習(xí)中的基礎(chǔ)知識,需要的朋友可以參考下,希望能夠給你帶來幫助
    2021-09-09
  • 基于稀疏圖上的Johnson算法的詳解

    基于稀疏圖上的Johnson算法的詳解

    本篇文章介紹了,稀疏圖上的Johnson算法的詳解。需要的朋友參考下
    2013-05-05
  • 最新評論