资源预览内容
第1页 / 共11页
第2页 / 共11页
第3页 / 共11页
第4页 / 共11页
第5页 / 共11页
第6页 / 共11页
第7页 / 共11页
第8页 / 共11页
第9页 / 共11页
第10页 / 共11页
亲,该文档总共11页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
经典排序算法总结代码)仍分享目录/*冒泡法2/*快速排序3/*插入排序4/*希尔(shell)排序5/*选择排序6/*堆排序7/*归并排序9附:排序算法原理::zh.wikiDedia.org/wiki/Calegory:%E6%8E%92%E5%BA%8F%E7%AE%flash演示:97%E6%B3%95:/tyut.edu /kecheng 1/siteO 1 /suanfayanshi/list.asp?id=7贝出来粘到合并序列尾memcpy(temp+k, array+begin2,(end2-begin2+1 )*sizeof(T);memcpy(array+low, temp, (high-low+1 )*sizeof(T);/ 将排序好的序列拷贝回数组中delete temp;)templatevoid merge_sort(T array J, unsigned int first, unsigned int last)(int mid = 0;if(firstlast) /mid = (first+last)/2; /*注意防止溢出*/ mid = first/2 + last/2;/mid = (first & last) + (first A last) 1); merge_sort(array, first, mid); merge_sort(array, mid+l,last); merge(array,first,mid,last);template void Print(T* r,int n)for (int i=0;ivn;i+)(cout ri endl;) int main()(cout Welcome.0 endl; double r = (1.5,3.2,5,6,9.2,7,2,4,8; /BubbleSort(r,9);QuickSort(r,0,8);/insert_sort(r,9);/shell_sort(r,9);/SelectSort(r,9);/HeapSort(r,9);/ merge_sort(r,0,8);Print(r,9);return 0;#include #include using namespace std;/* 冒泡法 左右元素相比,往后冒泡 */template void BubbleSort(T* r, int n) T temp;int ij;for (i=0;ivn-l;i+)(for (j=O;jvn-i-l;j+)(if(rjrU+l)(temp = rj;+1; rj+l = temp;/*快速排序左边比他小,右边比他大,每次得到一个最左边数据的 位置*/templatevoid QuickSort(T a,int low,int high)(if(low high)T elem = alow;int 1 = low, r = high;while(l = elem) r;if (1 r)(al+ = ar;while(l r & al = elem) 1+;if (1 r)(ar- = al;ar = elem;QuickSort(a,low,r-l);QuickSort(a,r+ l,high);/*插入排序向右移,aj+l=aj*/ template void insert_sort(T af,int n)int i,j;T elem;for (i= l;i=0 & elem aj) aU+H = aj;j-;aj+l = elem;/*希尔shell)排序 把插入排序的改成d即可*/templatevoid shell_insert(T array,int d,int len) int i,j;T elem;for (i = d;i = 0 & elem arrayj) array j+d = array j;j = j -d;array j+d = elem;templatevoid sheIl_sort(T array,int len) (int inc = len;doinc = inc/2; shell_insert(array,inc,len);while (inc 1);/*选择排序逐一比拟,最小的放前面*/ template void SelectSort(T a,int n) (int i,j,elemNum;T elem;for (i=();ivn-l;i+)(elemNum = i;for (j= i+ l;jvn;j+)if (afj v afelemNum) (elemNum = j;)if (elemNum != i)elem = ai; ai = aelemNum; afelemNum = elem;/*堆排序as=a2*s & as=a2*s+l*/ templatevoid Max_heap(T a,int S,int len)(int1= 2*S;int r = 2*S+1;int maxi = S;T elem;if (1 amaxl)maxi = 1;)if (r v len & ar amaxl)(maxi = r;)if (maxi != S)(elem = aSJ;aS = amaxT; afmaxl = elem; Max_heap(a,maxi,len);)template void HeapSort(T a,int n) (inti;T elem;for (i = n/2;i=0;i-)Max_heap(a,i,n);)for (i= n-l;i=l;i)elem = a0; a0 = ai; ai = elem; n = n-1; Max_heap(a,O,n);/*归并排序左边小左边,左边+;右边小取右边,右边+*/ templatevoid merge(T array, int low, int mid, int high)int k;T *temp = new Thighlow+1; /申请空间,使其大小 为两个己经排序序列之和,该空间用来存放合并后的序 列int begin 1 = low;int endl 二 mid;int begin2 = mid + 1;int end2 = high;for (k = 0; begin! = endl & begin2 = end2; +k) 比拟两个指针所指向的元素,选择相对小的元素放入 到合并空间,并移动指针到下一位置(if(array begin 1 =array begin2)tempk = array begin 1+;else tempk = array begin2+;if(beginl = endl)/假设第一个序列有剩余,直接拷 贝出来粘到合并序列尾memcpy(temp+k, array+beginl,(end 1-begin 1+1 )*sizeof(T);if(begin2 = end2) 假设第二个序列有剩余,直接拷
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号