//整理者：LXZ-2008 百度文库笔名：锡永
//时间:2011/9/29
//学校:CUMT 2012届毕业 计算机科学与技术学院 计算机科学与技术专业 //内容：数据结构中常见的8种排序算法的C++代码实现 //全是内排序，稳定的排序算法：冒泡，插入，归并，基数 //不稳定的排序算法：希尔，快速，堆，选择
//邮箱：706625262@qq.com(仅供交流，不做技术支持)
//备注：我想大家在大二的时候可能已经熟悉这些排序了，但是不知道
// 大四时还能不能快速地写出这些排序算法，这些思想上掌握了，也不见得复杂 // 通过一次失败的机试，让我清楚编程时简洁的重要性，以及重温这些经典排序算法 // 以及快速编程的重要性。这次我花了3天重温了这些经典排序算法， // 并自己根据思想重新写了一下。
//头文件包含及命名空间引用 #include
//函数声明
void bubble_sort(int n[],int length);//冒泡排序 void selection_sort(int n[],int length);//选择排序 void insertion_sort(int n[],int length);//插入排序 void shell_sort(int n[],int length);//希尔排序
void quick_sort(int n[],int length);//快速排序接口 void quicksort(int n[],int first,int last);//快速排序 void merge_sort(int n[],int length);//归并排序接口
void mergesort(int n[],int first,int last);//归并排序
void Merge(int n[],int first,int middle,int last);//归并排序中的合并 void base_sort(int n[],int length);//基数排序接口 void heap_sort(int n[],int length);//堆排序接口
void buildmaxheap(int n[],int begin,int end);//建立最大堆 void maxheapify(int n[],int begin,int end);//调整最大堆 void Display(int n[],int length,bool state);//输出函数
typedef void ( * SortFuntion) (int n[],int length);//排序函数指针类型
//排序算法函数列表 SortFuntion sortfution[] = {
bubble_sort,//冒泡排序 selection_sort,//选择排序
insertion_sort,//插入排序 shell_sort,//希尔排序 quick_sort,//快速排序 merge_sort,//归并排序 base_sort,//基数排序
heap_sort//堆排序
};
//main funtion int main(){
int sortS[] = {8,6,2,18,4,3,26,61,72,15}; int sortD[] = {8,6,2,18,4,3,26,61,72,15};
/*
for(int i = 0; i < sizeof(sortfution)/sizeof(SortFuntion); i++){ cout<<\Display(sortD,sizeof(sortD)/sizeof(int),false); sortfution[i](sortD,sizeof(sortD)/sizeof(int)); Display(sortD,sizeof(sortD)/sizeof(int),true); cout<<\memcpy(sortD,sortS,sizeof(sortfution)); }
*/
Display(sortD,sizeof(sortD)/sizeof(int),false);//输出排序前的序列 heap_sort(sortD,sizeof(sortD)/sizeof(int));//排序
Display(sortD,sizeof(sortD)/sizeof(int),true);//输出排序后的序列 return 0;
}
//调整最大堆
void maxheapify(int n[],int begin,int end){ }
int r(begin);
if(2 * begin > end) return;
if(n[begin] < n[2*begin]) r = 2*begin;
if(2 * begin + 1 <= end && n[r] < n[2 * begin + 1]) r = 2*begin + 1; if(r!=begin){ int temp = n[begin]; }
n[begin] = n[r]; n[r] = temp; maxheapify(n,r,end);
//建立最大堆
void buildmaxheap(int n[],int begin,int end){ for(int i = begin; i > 0; i--) maxheapify(n,i,end);
}
//堆排序接口
void heap_sort(int n[],int length){ cout<<\ }
int *temp_n = new int[length + 1]; int end(length);
memcpy(temp_n+1,n,length * sizeof(int)); buildmaxheap(temp_n,length/2,length); do{
temp_n[0] = temp_n[1]; temp_n[1] = temp_n[end]; temp_n[end] = temp_n[0]; maxheapify(temp_n,1,--end);
}while(end >= 1);
memcpy(n,temp_n+1,length * sizeof(int)); delete []temp_n;
//基数排序接口
void base_sort(int n[],int length){
cout<<\ const int base = 10; //node class node {
public:
int data; node *next; node(){next = 0;}
}*current = 0 ,*head = 0,*pre; //malloc
node **box = new node *[base]; int i;
for(i = 0; i < base; i++) box[i] = new node; current = head = new node; //排序数据输入到当前链表中 int max(0);
for(i = 0;i < length; i++){ current = current -> next = new node;
current -> data = n[i]; if(max <= n[i]) max = n[i]; //找出最大的数
}
int k(0); while(max){ max /= base; k++; }//计算最大数的位数 int radix = 1; int order(0); node *p = 0; node *pnext = 0; for(i = 0; i < k; i++){
current = head -> next;//链表第一个节点 //拆链表
while(current){
order = (current -> data / radix) % base; p = box[order]; while(p -> next) p = p -> next; p -> next = current; current = current -> next; p -> next -> next = 0;
}
//找到第一个节点 int j (0);
for(j = 0; j < base; j++){
if(p = box[j]->next){ break;
} }
//合链表 head -> next = p; while(p -> next) p = p -> next; //next node while(++j < base){ if(pnext = box[j] -> next)
{
p -> next = pnext; p = p -> next; while( p -> next) p = p -> next;
}
}
radix *= base;
}
for(j = 0; j < base; j++){
box[j] -> next = 0; } }
//排序后将结果写入n数组中 current = head;
for(i = 0; current = current -> next ; i++){ }
n[i] = current -> data;
//dealloc
pre = current = head; while(pre){ }
current = pre -> next; delete pre; pre = current;
for(i = 0; i < base; i++) delete box[i]; delete []box;
//归并排序接口
void merge_sort(int n[],int length){ cout<<\ mergesort(n,0,length - 1); }
//归并排序中的合并
void Merge(int n[],int first,int middle,int last){ int bigin1 = first, bigin2 = middle + 1;
int end1 = middle,end2 = last; int *temp = new int [last-first + 1]; int i(0);
while(bigin1 <= end1 && bigin2 <= end2){ }
if(n[bigin1] < n[bigin2]) temp[i++] = n[bigin1++]; else
temp[i++] = n[bigin2++];
while(bigin1 <= end1) temp[i++] = n[bigin1++]; while(bigin2 <= end2) temp[i++] = n[bigin2++]; i = 0;