[C/C++ 演算法]- Shell 排序法 – 改良的插入排序
[C/C++ 演算法]- Shell 排序法 – 改良的插入排序
剛才找資料時發現一個C/C++的教學網站，趕快發揮(C/P)的長才將它備份來，有需要的同好，歡迎來(C/P)一下^^。
拷貝來源：
http://openhome.cc/Gossip/AlgorithmGossip/
http://openhome.cc/Gossip/AlgorithmGossip/ShellSort.htm
#include <stdio.h>
#define LEN 10
#define SWAP(x,y) {int t; t = x; x = y; y = t;}
void sort(int*, int, int(*)(int, int));
void insertion(int*, int, int, int, int(*)(int, int));
void insert(int*, int, int, int, int(*)(int, int));
int ascending(int, int);
int descending(int, int);
void print(int*, int);
int main(void) {
int number[LEN] = {89, 12, 65, 97, 61, 81, 27, 2, 61, 98};
sort(number, LEN, ascending);
print(number, LEN);
sort(number, LEN, descending);
print(number, LEN);
return 0;
}
void sort(int* number, int len, int(*compar)(int, int)) {
int gap;
for(gap = len / 2; gap > 0; gap /= 2) {
int begin;
for(begin = 0; begin < gap; begin++) {
insertion(number, len, begin, gap, compar);
}
}
}
void insertion(int* number, int len,
int begin, int gap, int(*compar)(int, int)) {
int i;
for(i = begin + gap; i < len; i += gap) {
insert(number, begin, gap, i, compar);
}
}
void insert(int* number, int begin, int gap, int i, int(*compar)(int, int)) {
int j;
for(j = i - gap;
j >= begin && compar(number[j], number[j + gap]) > 0 ; j -= gap) {
SWAP(number[j], number[j + gap]);
}
}
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++ 演算法]- Shell 排序法 – 改良的插入排序”
排序法的性能評估指標:
穩定：如果a原本在b前面，而a=b，排序之後a仍然在b的前面。
不穩定：如果a原本在b的前面，而a=b，排序之後a可能會出現在b的後面。
時間複雜度：對排序數據的總的操作次數。反映當n變化時，操作次數呈現什麼規律。
空間複雜度：是指算法在計算機內執行時所需存儲空間的度量，它也是數據規模n的函數。
PS. 個人認為目前最為推薦 [ 效率(速度)&額外記憶體使用量&穩定度 ] 的排序法 – 归并排序/歸併排序/合併排序 (Merge Sort)