Thursday, June 28, 2012
這兩天比較閑，復習了一下算法中的基本排序算法。
挑選了3種比較經典的排序算法進行了實現并測試。
1. 基數排序
typedef std::queue<int> BUCKET;
#define ONEBITMAX 16
void Straight_Radix(int nArray[], int nArrayNO, int nElementBits)
{
BUCKET pBucket[ONEBITMAX];
int nBucketIndex, nArrayIndex;
for (int k = 0; k < nElementBits; k++)
{
nArrayIndex = 0;
for (int i = 0; i < nArrayNO; i++)
{
nBucketIndex = (nArray[i] & (0xf << (4*k))) >> (4*k);
pBucket[nBucketIndex].push(nArray[i]);
}
for (int i = 0; i < ONEBITMAX; i++)
{
while(!pBucket[i].empty())
{
nArray[nArrayIndex++] = pBucket[i].front();
pBucket[i].pop();
}
}
}
}由于用了stl queue所以導致效率有一定降低，而且使用的16個桶占用了很多額外的空間。
O(kn)
2. 快速排序
int Partition(int nArray[], int Left, int Right)
{
int nPivot = nArray[Left];
int nMiddle, L, R;
int nTemp;
L = Left;
R = Right;
while(1)
{
while(nArray[L] <= nPivot && L<=Right)
{
L++;
}
while(nArray[R] > nPivot && R >= Left)
{
R--;
}
if (L >= R)
{
break;
}
if (nArray[L] > nArray[R])
{
nTemp = nArray[R];
nArray[R] = nArray[L];
nArray[L] = nTemp;
}
}
nMiddle = R;
nTemp = nArray[Left];
nArray[Left] = nArray[nMiddle];
nArray[nMiddle] = nTemp;
return nMiddle;
}
void Q_Sort(int nArray[], int Left, int Right)
{
if (Left < Right)
{
int nMiddle = Partition(nArray, Left, Right);
Q_Sort(nArray, Left, nMiddle - 1);
Q_Sort(nArray, nMiddle + 1, Right);
}
}
void QuickSort(int nArray[], int nArrayNO)
{
Q_Sort(nArray, 0, nArrayNO - 1);
} O(nlogn)如果當數組小于一定規模（10-20）采用插入排序，可以減少一定的時間
3. 堆排序
void Build_heap(int nArray[], int nHeapSize) //from 1 to nHeapSize
{
int nParent, nTemp, nLeft, nRight;
for (int i = nHeapSize / 2 + 1; i >= 1; i--)
{
nParent = i;
while(1)
{
nLeft = nParent * 2;
nRight = nParent * 2 + 1;
if (nLeft > nHeapSize)
{
break;
}
else if (nHeapSize == nLeft)
{
if (nArray[nParent] < nArray[nLeft])
{
nTemp = nArray[nParent];
nArray[nParent] = nArray[nLeft];
nArray[nLeft] = nTemp;
}
break;
}
else
{
if (nArray[nLeft] >= nArray[nRight])
{
if (nArray[nParent] < nArray[nLeft])
{
nTemp = nArray[nParent];
nArray[nParent] = nArray[nLeft];
nArray[nLeft] = nTemp;
nParent = nLeft;
continue;
}
}
else
{
if (nArray[nParent] < nArray[nRight])
{
nTemp = nArray[nParent];
nArray[nParent] = nArray[nRight];
nArray[nRight] = nTemp;
nParent = nRight;
continue;
}
}
break;
}
}
}
}
void Rearrange_Heap(int nArray[], int nHeapSize)
{
if (1 == nHeapSize)
{
return;
}
int nParent, nTemp, nLeft, nRight;
nParent = 1;
while(1)
{
nLeft = nParent * 2;
nRight = nParent * 2 + 1;
if (nLeft > nHeapSize)
{
break;
}
else if (nHeapSize == nLeft)
{
if (nArray[nParent] < nArray[nLeft])
{
nTemp = nArray[nParent];
nArray[nParent] = nArray[nLeft];
nArray[nLeft] = nTemp;
}
break;
}
else
{
if (nArray[nLeft] >= nArray[nRight])
{
if (nArray[nParent] < nArray[nLeft])
{
nTemp = nArray[nParent];
nArray[nParent] = nArray[nLeft];
nArray[nLeft] = nTemp;
nParent = nLeft;
continue;
}
}
else
{
if (nArray[nParent] < nArray[nRight])
{
nTemp = nArray[nParent];
nArray[nParent] = nArray[nRight];
nArray[nRight] = nTemp;
nParent = nRight;
continue;
}
}
break;
}
}
}
void HeapSort(int nArray[], int nArrayNO)
{
Build_heap(nArray, nArrayNO - 1);
int nTemp;
for (int i = nArrayNO - 1; i >= 2; i--)
{
nTemp = nArray[1];
nArray[1] = nArray[i];
nArray[i] = nTemp;
Rearrange_Heap(nArray, i - 1);
}
//insert index 0
int nIndex = 0;
for (int i = 1; i < nArrayNO; i++)
{
if (nArray[nIndex] <= nArray[i])
{
break;
}
nTemp = nArray[nIndex];
nArray[nIndex] = nArray[i];
nArray[i] = nTemp;
nIndex = i;
}
} O(nlogn)
測試：在2.7G*2 CPU，3.4G內存的pc上，隨機生成的1億個最大值為2的31次的整數作為測試用例。
測試方法：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#ifdef QSORT
#include "QuickSort.h"
#endif
#ifdef HEAPSORT
#include "HeapSort.h"
#endif
#ifdef BUCKETSORT
#include "Straight_Radix.h"
#endif
const int ARRAYNO = 100000000;
int unSortedArray[ARRAYNO];
void CreateUnSortedArray()
{
int nRand;
FILE *fp = fopen("UnSortedArray.log", "wb");
for (int i = 0; i < ARRAYNO; i++)
{
nRand = (rand() << 15) + rand();
fprintf(fp, "%d\n", nRand);
}
fclose(fp);
}
bool LoadUnSortedArray()
{
FILE *fp = fopen("UnSortedArray.log", "r");
if (NULL == fp)
{
return false;
}
char szBuffer[256];
memset(unSortedArray, 0, sizeof(int) * ARRAYNO);
memset(szBuffer, 0 , 256);
int nArrayIndex = 0;
while(fgets(szBuffer, 255, fp))
{
unSortedArray[nArrayIndex++] = atoi(szBuffer);
memset(szBuffer, 0 , 256);
}
fclose(fp);
return true;
}
bool SaveSortedArray(int nTime)
{
FILE *fp = fopen("SortedArray.log", "wb");
if (NULL == fp)
{
return false;
}
fprintf(fp, "time cost %dms\n", nTime);
for (int i = 0; i < ARRAYNO; i++)
{
fprintf(fp, "%d\n", unSortedArray[i]);
}
fclose(fp);
return true;
}
void main()
{
//CreateUnSortedArray();
if(!LoadUnSortedArray())
{
printf("Load unsortedArray failed!\n");
return;
}
int nStart = clock();
#ifdef QSORT
QuickSort(unSortedArray, ARRAYNO);
#endif
#ifdef HEAPSORT
HeapSort(unSortedArray, ARRAYNO);
#endif
#ifdef BUCKETSORT
Straight_Radix(unSortedArray, ARRAYNO, 8);
#endif
SaveSortedArray(clock() - nStart);
system("pause");
}
測試結果：()中為快速排序+插入排序的時間
|
基數排序 |
快速排序 |
堆排序 |
| time |
45093ms |
14797ms（13625ms） |
77047ms |
按理論堆排序和快速排序應該差不多，不明原因。
posted on 2012-06-28 18:02
saha 閱讀(455)
評論(1) 編輯 收藏 引用