1樓：
3. 歸併排序
void Merge(int* initList, int*
mergedList, const int l, const int m, const int r)
int i1 = l, i2 = m + 1, iResult =
l;for (; (i1 <= m) && (i2
<= r); iResult++)
if (initList[i1] <
initList[i2])
mergedList[iResult] =
initList[i1++];
else
mergedList[iResult] =
initList[i2++];
//copy第二個引數是終止拷貝的後乙個位置
copy(initList + i1, initList + m +
1, mergedList + iResult);
copy(initList + i2, initList + r +
1, mergedList + iResult);
void MergePass(int* initList, int*
mergedList, int mergeSize, int size)
int i = 1;
for (; i + 2 * mergeSize - 1 <=
size; i += 2 * mergeSize)
Merge(initList, mergedList, i, i +
mergeSize - 1, i + 2 * mergeSize - 1);
if ((i + mergeSize - 1) < size)
Merge(initList, mergedList, i, i + mergeSize - 1, size);
else copy(initList + i, initList +
size + 1, mergedList + i);
void MergeSort(int* a, int size)
int* mergedList = new int[size +
1];mergedList[0] = 0;
for (int mergeSize = 1; mergeSize
< size; mergeSize *= 2)
MergePass(a, mergedList,
mergeSize, size);
mergeSize *= 2;
MergePass(mergedList, a,
mergeSize, size);
deletemergedList;
4. 堆排序
void Adjust(int*a, int root, int
size)
int keep = a[root];
int child = root * 2;
for (; child <= size; child *=
2)if (childa[child]) child++;
if (a[child] > keep) a[child /
2] = a[child];
else break;
a[child / 2] = keep;
void HeapSort(int* a, int size)
for (int i = size / 2; i > 0;
i--)
Adjust(a, i, size);
for (int i = size - 1; i > 0;
i--)
swap(a[1], a[i + 1]);
Adjust(a, 1, i);
5. 時間測試程式
//獲得隨機序列函式
void Permute(int* a, int n)
for (int i = n; i >= 2; i--)
int j = rand() % i + 1;
swap(a[j], a[i]);
//測試時間函式
double
testSortTime(void(*sortP)(int*, int), int n)
LARGE_INTEGER start, stop, freq;
//初始化陣列
int* a = new int[n + 1];
for (int i = 0; i < n + 1; i++)
a[i] = i;
double runTime = 0;
QueryPerformanceFrequency(&freq);
//獲得100次迴圈+排序總時間
QueryPerformanceCounter(&start);
for (int k = 0; k < 100; k++)
Permute(a, n);
(*sortP)(a, n);
QueryPerformanceCounter(&stop);
runTime = (double)(stop.QuadPart -
start.QuadPart);
//減去100次迴圈時間
QueryPerformanceCounter(&start);
for (int k = 0; k < 100; k++)
Permute(a, n);
QueryPerformanceCounter(&stop);
runTime -= (double)(stop.QuadPart
- start.QuadPart);
runTime /= 100;//計算單次排序時間
runTime /= freq.QuadPart;//轉換成秒
runTime *= 1000;//轉換成毫秒
return runTime;
6. 主程式
#include
#include
using namespace std;
int main()
cout << "Insert"
<< endl;
cout <<
testSortTime(&InsertSort, 500) << endl;
cout <<
testSortTime(&InsertSort, 1000) << endl;
cout <<
testSortTime(&InsertSort, 2000) << endl;
cout << testSortTime(&InsertSort,
3000) << endl;
cout <<
testSortTime(&InsertSort, 4000) << endl;
cout <<
testSortTime(&InsertSort, 5000) << endl;
cout << "Quick"
<< endl;
cout <<
testSortTime(&QuickSort, 500) << endl;
cout <<
testSortTime(&QuickSort, 1000) << endl;
cout <<
testSortTime(&QuickSort, 2000) << endl;
cout <<
testSortTime(&QuickSort, 3000) << endl;
cout <<
testSortTime(&QuickSort, 4000) << endl;
cout <<
testSortTime(&QuickSort, 5000) << endl;
cout << "Merge"
<< endl;
cout <<
testSortTime(&MergeSort, 500) << endl;
cout <<
testSortTime(&MergeSort, 1000) << endl;
cout <<
testSortTime(&MergeSort, 2000) << endl;
cout <<
testSortTime(&MergeSort, 3000) << endl;
cout <<
testSortTime(&MergeSort, 4000) << endl;
cout <<
testSortTime(&MergeSort, 5000) << endl;
cout << "Heap"
<< endl;
cout <<
testSortTime(&HeapSort, 500) << endl;
cout <<
testSortTime(&HeapSort, 1000) << endl;
cout <<
testSortTime(&HeapSort, 2000) << endl;
cout <<
testSortTime(&HeapSort, 3000) << endl;
cout <<
testSortTime(&HeapSort, 4000) << endl;
cout <<
testSortTime(&HeapSort, 5000) << endl;
system("pause");
return 0;
INFP INFJ INTP INTJ 四種型別的文風區別有哪些？
本人目前in混亂，什麼都測出來過。一些想法的片段和不成文的短文 世界是由視角組成的。你存在的意義就是為世界多新增一種視角。世界因多樣而有自我意志。自我因多樣而碰撞壯大世界,壯大自己。活著就是為了體驗和感知更多視角,以參與到更大的世界中。而不論是精神還是實體都是一種途徑。而這種觀點也必然會帶來 寬容主...
Photoshop 裡面四種字型抗鋸齒方式中，哪種方式更貼近 iOS 的中文字型渲染效果？
macOS 環境下的 Photoshop 請使用 Mac 來進行抗鋸齒，這種和 iOS 一樣使用的是灰階抗鋸齒 Mac LCD 則是和 macOS 勾選了系統偏好設定裡的 使用 LCD 平滑字型 的亞畫素抗鋸齒渲染效果一致，僅將使用亞畫素抗鋸齒所產生的彩色畫素替換更好成了灰度畫素，但視覺觀感上的厚重...
infp是如何看待四種nt的？
淺藍色的 entj 目標似乎有點 友善的微笑 而且感覺有點過於自信導致他比較 愛顯擺 有點沉不住氣，但是內心應該還是挺善良，對集體比較負責任 或者只是過於自信導致 挺吵的，並沒有過多交集。intj 很軸，創意很多很大膽，我覺得蠻不錯的，雖然我身邊這種人蠻少。intp nt裡面算是喜歡的一種了，涉獵廣...