冒泡算法的改進具體實現

2020-01-26 15:39:10

字體：大中小

來源：轉載

供稿：網友

冒泡排序算法的思想：

首先將第一個記錄的關鍵字和第二個關鍵字進行比較，若為逆序則將兩個記錄進行交換。
然后比較第二個記錄和第三個記錄的關鍵字，直至第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;
}