[C/C++ 演算法]- Heap 排序法 – 改良的選擇排序
[C/C++ 演算法]- Heap 排序法 – 改良的選擇排序
剛才找資料時發現一個C/C++的教學網站，趕快發揮(C/P)的長才將它備份來，有需要的同好，歡迎來(C/P)一下^^。
拷貝來源：
http://openhome.cc/Gossip/AlgorithmGossip/
http://openhome.cc/Gossip/AlgorithmGossip/HeapSort.htm
#include <stdio.h>
#include <stdlib.h>
#define LEN 10
#define OFFSET 1
#define SWAP(x,y) {int t; t = x; x = y; y = t;}
void heapSort(int*, int len, int(*)(int, int));
void heapTree(int*, int, int(*)(int, int));
void selectFromHeap(int*, int, int(*)(int, int));
void bubbleLeaf(int*, int, int(*)(int, int));
int isBubbleable(int*, int, int, int(*)(int, int));
void bubbleRoot(int*, int, int(*)(int, int));
int idxFromChilds(int*, int, int, int(*)(int, int));
int isRightLeafSuitable(int*, int, int, int(*)(int, int));
void print(int*, int len);
int ascending(int, int);
int descending(int, int);
int main(void) {
int num[LEN] = {10, 9, 1, 2, 5, 3, 8, 7, 12, 11};
heapSort(num, LEN, descending);
print(num, LEN);
heapSort(num, LEN, ascending);
print(num, LEN);
system("PAUSE");
return 0;
}
void heapSort(int* num, int len, int(*compar)(int, int)) {
heapTree(num, len, compar);
selectFromHeap(num, len, compar);
}
void heapTree(int* num, int len, int(*compar)(int, int)) {
int i, end;
for(i = 1, end = len + 1; i < end; i++) { bubbleLeaf(num, i, compar); }
}
void selectFromHeap(int* num, int len, int(*comp)(int, int)) {
int end;
for(end = len; end > OFFSET; end--) {
SWAP(num[1 - OFFSET], num[end - OFFSET]);
bubbleRoot(num, end, comp);
}
}
void bubbleLeaf(int* num, int eleIdx, int(*compar)(int, int)) {
int childIdx, parentIdx;
for(childIdx = eleIdx, parentIdx = eleIdx / 2;
isBubbleable(num, childIdx, parentIdx, compar);
childIdx = parentIdx, parentIdx = childIdx / 2) {
SWAP(num[parentIdx - OFFSET], num[childIdx - OFFSET]);
}
}
int isBubbleable(int* num, int childIdx,
int parentIdx, int(*compar)(int, int)) {
return childIdx > OFFSET &&
compar(num[parentIdx - OFFSET], num[childIdx - OFFSET]) < 0;
}
void bubbleRoot(int* num, int end, int(*comp)(int, int)) {
int parentIdx, childIdx;
for(parentIdx = 0 + OFFSET,
childIdx = idxFromChilds(num, parentIdx, end, comp);
childIdx < end &&
comp(num[childIdx - OFFSET], num[parentIdx - OFFSET]) > 0;
parentIdx = childIdx,
childIdx = idxFromChilds(num, parentIdx, end, comp)) {
SWAP(num[parentIdx - OFFSET], num[childIdx - OFFSET]);
}
}
int idxFromChilds(int* num, int parentIdx, int end, int(*comp)(int, int)) {
int childIdx = parentIdx * 2;
return isRightLeafSuitable(num, childIdx, end, comp) ?
childIdx + 1 : childIdx;
}
int isRightLeafSuitable(int* num, int childIdx,
int end, int(*comp)(int, int)) {
return childIdx < end - 1 &&
comp(num[childIdx + 1 - OFFSET], num[childIdx - OFFSET]) > 0;
}
void print(int* arr, int len) {
int i;
for(i = 0; i < len; i++) { printf("%d ", arr[i]); }
printf("\n");
}
int ascending(int a, int b) { return a - b; }
int descending(int a, int b) { return -ascending(a, b); }
|
One thought on “[C/C++ 演算法]- Heap 排序法 – 改良的選擇排序”
排序法的性能評估指標:
穩定：如果a原本在b前面，而a=b，排序之後a仍然在b的前面。
不穩定：如果a原本在b的前面，而a=b，排序之後a可能會出現在b的後面。
時間複雜度：對排序數據的總的操作次數。反映當n變化時，操作次數呈現什麼規律。
空間複雜度：是指算法在計算機內執行時所需存儲空間的度量，它也是數據規模n的函數。
PS. 個人認為目前最為推薦 [ 效率(速度)&額外記憶體使用量&穩定度 ] 的排序法 – 归并排序/歸併排序/合併排序 (Merge Sort)