数据结构-之-排序算法-模板篇~
原创文章如转载请注明：转自￥忘%风 {http://www.cnblogs.com/slave_wc}
本文地址: 数据结构-之-排序算法-模板篇~
投了个淘宝实习的简历，听说笔试会偏数据结构和算法，于是下午看了下数据结构，复习了一些排序算法。
顺便写了一个包含多种排序的类模板。以前排序基本不写，做acm都是用库里的sort。
好久没写题目了，本来会的算法就不多，也已经淡忘了差不多了。。。
笔试通知的短信都还没收到呢，额，怎么说，笔试的机会你得给个吧。。。
写篇博存下初步模板，待完善补充 . . .
代码如下：
#define MAXN 1100
typedef struct Node{
int key;
bool friend operator >= (const Node &a, const Node &b) {
return a.key >= b.key;
}
bool friend operator <= (const Node &a, const Node &b) {
return a.key <= b.key;
}
bool friend operator < (const Node &a, const Node &b) {
return a.key < b.key;
}
bool friend operator > (const Node &a, const Node &b) {
return a.key > b.key;
}
}List;
class Array {
private:
List r[MAXN]; /*--为方便堆排，0号单元不用--*/
List ret[MAXN]; /*--归并排序的辅助空间--*/
int dlta[MAXN]; /*--为希尔排序设定默认增量序列---*/
/*-----------------快速排序----------------*/
int partition(int low, int high) {
List pivotkey = r[low];
while (low < high) {
while (low < high && r[high] >= pivotkey)
--high;
r[low] = r[high];
while (low < high && r[low] <= pivotkey)
++low;
r[high] = r[low];
}
r[low] = pivotkey;
return low;
}
void quick_sort(int low, int high) {
int pivotloc;
if (low < high) {
pivotloc = partition(low, high);
quick_sort(low, pivotloc - 1);
quick_sort(pivotloc + 1, high);
}
}
/*-----------------堆排序------------------*/
void creat_heap() {
for (int i = length >> 1; i > 0; i --) {
heap_adjust(i, length);
}
}
void heap_adjust(int s, int m) {
List rc = r[s];
for (int j = s << 1; j <= m; j <<= 1) {
if (j < m && r[j] <= r[j+1]) j++;
if (rc >= r[j]) break;
r[s] = r[j];
s = j;
}
r[s] = rc;
}
void heap_sort() {
for (int i = length; i > 1; i--) {
List tmp = r[1];
r[1] = r[i];
r[i] = tmp;
heap_adjust(1, i - 1);
}
}
/*---------------2-路归并排序----------------*/
void merge(int i, int m, int n) {
//将r[i, m],r[m+1, n]合并为ret[i, n]；
int idx = i, j, k;
for (j = m + 1, k = i; i <= m && j <= n; k++) {
if (r[i] <= r[j]) ret[k] = r[i++];
else ret[k] = r[j++];
}
for ( ; i <= m; i++) ret[k++] = r[i];
for ( ; j <= n; j++) ret[k++] = r[j];
for (j = idx; j <= n; j++) {
r[j] = ret[j];
}
}
void m_sort(int s, int t) {
if (s == t) {
ret[s] = r[s];
}
else {
int m = (s + t) / 2;
m_sort(s, m);
m_sort(m + 1, t);
merge(s, m, t);
}
}
/*------------------希尔排序------------------*/
int get_dlta() {
/*-------------设定的默认增量值---------------*/
int k = length - 1;
int len = 0;
while (k > 0) {
dlta[len++] = k;
k >>= 1;
}
return len;
}
void shell_insert(int dk) {
int i, j;
for (i = dk + 1; i <= length; i++) {
if (r[i] < r[i - dk]) {
r[0] = r[i];//0号未用，做暂存
for (j = i - dk; j > 0 && r[0] < r[j]; j -= dk) {
r[j + dk] = r[j];
}
r[j + dk] = r[0];
}
}
}
void shell_sort() {
//按增量dlta[0, t - 1];做希尔排序，最后一个为1.
int len = get_dlta();
for (int k = len - 1; k >= 0; k--) {
shell_insert(dlta[k]);
}
}
/*--------------直接插入排序----------------*/
void insert_sort() {
int i, j;
for (i = 2; i <= length; i++) {
if (r[i] < r[i - 1]) {
r[0] = r[i]; //0号不用，做哨兵
for (j = i - 1; r[0] < r[j]; j--) {
r[j + 1] = r[j];
}
r[j + 1] = r[0];
}
}
}
/*----------------冒泡排序----------------*/
void bubble_sort() {
for (int i = 1; i < length; i++) {
bool change = false;
for (int j = length - 1; j >= i; j--) {
if (r[j + 1] < r[j]) {
r[0] = r[j];
r[j] = r[j + 1];
r[j + 1] = r[0];
change = true;
}
}
if (!change)
return ;
}
}
/*----------------选择排序----------------*/
void select_sort() {
for (int i = 1; i < length; i++) {
int idx = i;
for (int j = i + 1; j <= length; j++) {
if (r[j] < r[idx]) {
idx = j;
}
}
if (idx != i) {
r[0] = r[idx];
r[idx] = r[i];
r[i] = r[0];
}
}
}
public:
List *list;
int length;
enum Sort_Type {MERGE_SORT, QUICK_SORT, HEAP_SORT,
SHELL_SORT, INSERT_SORT, BUBBLE_SORT, SELECT_SORT};
Array() {
length = 0;
list = &r[1];
/*为符合一般习惯，加list指针调整，使区间为[0，length）*/
}
void clear() {
length = 0;
}
void push_back(List val) {
r[++length] = val;
}
void Sort(Sort_Type kd, int start, int end) {
if (kd == MERGE_SORT) {
m_sort(start + 1, end);
} else if (kd == QUICK_SORT){
quick_sort(start + 1, end);
}
}
void Sort(Sort_Type kd) {
if (kd == HEAP_SORT) {
creat_heap();
heap_sort();
} else if (kd == SHELL_SORT) {
shell_sort();
} else if (kd == INSERT_SORT) {
insert_sort();
} else if (kd == BUBBLE_SORT) {
//puts("----");
bubble_sort();
}else if (kd == SELECT_SORT) {
select_sort();
}
}
};
/*------简单测试了下,题hdu 1040-------------*/
int main() {
int test, n;
Array a;
List tmp;
scanf("%d", &test);
while (test--) {
a.clear();
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d", &tmp.key);
a.push_back(tmp);
}
a.Sort(a.HEAP_SORT);
a.Sort(a.BUBBLE_SORT);
a.Sort(a.SELECT_SORT);
a.Sort(a.INSERT_SORT);
a.Sort(a.SHELL_SORT);
a.Sort(a.MERGE_SORT, 0, a.length);
a.Sort(a.QUICK_SORT, 0, a.length);
printf("%d", a.list[0]);
for (int i = 1; i < a.length; i++) {
printf(" %d", a.list[i]);
}
puts("");
}
return 0;
}
推荐.NET配套的通用数据层ORM框架：CYQ.Data 通用数据层框架