堆排序
写得很烂，也可能是错的，自己看看就好了……
typedef int debug_int [50]; debug_int* p; void print(int a[], int length) { for (int i = 0; i< length; ++i) { cout<<a[i]<<" "; } cout<<endl; } void heapadjust(int a[], int s, int length) { int temp; int child_pos; for (int i = s; 2*i+1 < length ; i = child_pos) { child_pos = 2*i +1; if (child_pos != length - 1 && a[child_pos] < a[child_pos +1] ) { ++child_pos; } if (a[i] < a[child_pos]) { temp = a[i]; a[i] = a[child_pos]; a[child_pos] = temp; } else break; } } void heapsort(int a[], int length) { for (int i = length/2 - 1 ; i >= 0 ; --i) { heapadjust(a, i, length); print(a, length); } cout<<"************************"<<endl; for (int i = length - 1; i>0; --i) { swap(a[i], a[0]); heapadjust(a, 0, i); print(a, length); } } void main() { int a[50]; p = &a; int i = 0; while(cin>>a[i]) { ++i; } heapsort(a, i); cout<<"------------------"<<endl; print(a, i); }
快速排序
template<class T> size_t Partition(T a[], int low, int high) { T pivotkey = a[low]; int old_high = high; int old_low = low; while(low < high) { while(low < high && a[high] >= pivotkey) --high; a[low] = a[high]; //swap(a[low], a[high]); while(low < high && a[low] <= pivotkey) ++low; a[high] = a[low]; //swap(a[low], a[high]); //if (low < high) //{ // swap(a[low], a[high]); //} } if (low <= old_high) { a[low] = pivotkey; } return low; } template<class T> void Qsort(T a[], int low, int high) { int location; if (low < high) { location = Partition(a, low, high); Qsort(a, low, location - 1); Qsort(a, location + 1, high); } }
atoi
long __cdecl atol( const char *nptr ) { int c; /* current char */ long total; /* current total */ int sign; /* if '- ', then negative, otherwise positive */ /* skip whitespace */ while ( isspace((int)(unsigned char)*nptr) ) ++nptr; c = (int)(unsigned char)*nptr++; sign = c; /* save sign indication */ if (c == '- ' || c == '+ ') c = (int)(unsigned char)*nptr++; /* skip sign */ total = 0; while (isdigit(c)) { total = 10 * total + (c - '0 '); /* accumulate digit */ c = (int)(unsigned char)*nptr++; /* get next char */ } if (sign == '- ') return -total; else return total; /* return result, negated if necessary */ } int __cdecl atoi( const char *nptr ) { return (int)atol(nptr); }
二分查找
int binaryfind(int a[], int n, int val) { int low = 0; int high = n - 1; if (n <= 0) { return -1; } while(low <= high) { int mid = low + (high - low)/2; if (a[mid] == val) { return mid; } else if (a[mid] > val) { high = mid -1; } else { low = mid + 1; } } return -1; }
链表反向和合并
//定义数据结构 struct Node { Node(int i):data(i),next(0){} int data; Node* next; }; void ListReverse(Node* &p) { Node* oldhead = p->next; Node* newhead = p; if (p == NULL) { return; } newhead->next = NULL; while(oldhead) { Node* temp = oldhead->next; oldhead->next = newhead; newhead = oldhead; oldhead = temp; } p = newhead; } Node* ListMerge(Node* p1, Node* p2) { if (p1 == NULL) { return p2; } if (p2 == NULL) { return p1; } Node* head = p1; p1 = p1->next; Node* cur = head; while(p1 && p2) { if (p1->data <= p2->data) { head->next = p1; head = head->next; p1 = p1->next; } else { head->next = p2; head = head->next; p2 = p2->next; } } if (p1 != NULL) { head->next = p1; } if (p2 != NULL) { head->next = p2; } return cur; }
判断大小端机器
int isSmallEndian() { static union u{ char c[2]; short i; }U = {0x0001}; return U.c[0]; }
变参函数
void printInt(int n, ...) { va_list ap; va_start(ap, n); for (int i = 0; i < n; ++i) { int temp = va_arg(ap, int); cout<<temp<<' '; } va_end(ap); cout<<endl; }
strstr
char* strstr(const char *str1, const char *str2) { char *s1, *s2; _ASSERT(str1 && str2); //空字符串是任何字符串的子串 if ('/0' == *str2){ return (char*)str1; } while (*str1) { s1 = (char*)str1; s2 = (char*)str2; while ((*s1 == *s2) && *s1 && *s2){ s1++; s2++; } //匹配成功 if ('/0' == *s2){ return (char*)str1; } str1++; } return NULL; }
strcpy
char * strcpy (char * dst, char * src) { char * cp = dst; while( *cp++ = *src++ ) ; /* Copy src over dst */ return( dst ); }
strcat
char * strcat (char * dst, char * src) { char * cp = dst; while( *cp ) ++cp; /* Find end of dst */ while( *cp++ = *src++ ) ; /* Copy src to end of dst */ return( dst ); }
strcmp
int strcmp2 (const char *src, const char *dst) { int ret = 0 ; while(!(ret = *(unsigned char *)src - *(unsigned char *)dst) && *dst) { ++src; ++dst; } if ( ret < 0 ) ret = -1 ; else if ( ret > 0 ) ret = 1 ; return( ret ); }
统计二进制位为1的个数
//算法：统计x转化为2进制的位中为1的个数 //来源：网上 int func(int x) { int countx = 0; while(x) { countx ++; x = x&(x-1); } return countx; } int func(int x) { int countx = 0; for(int i=0;i<32;i++){ if((x>>i)&1) countx ++; } return countx; }
