2022年数据结构《排序算法的C++代码实现》 .pdf

《2022年数据结构《排序算法的C++代码实现》 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构《排序算法的C++代码实现》 .pdf（8页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、/ 头文件包含及命名空间引用#include using namespace std; / 函数声明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);/快速

2、排序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

3、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/ 堆

4、排序; /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=Begin=endl; Display(sortD,sizeof(sortD)/sizeof(int),false); sortfutioni(sortD,sizeof(sortD)/sizeof(int);名师资料总结 - - -精品资料欢迎下载 -

5、 - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 8 页 - - - - - - - - - Display(sortD,sizeof(sortD)/sizeof(int),true); cout=End= end) return; if(nbegin n2*begin) r = 2*begin; if(2 * begin + 1 = end & nr 0; i-) maxheapify(n,i,end); / 堆排序接口void heap_sort(int n,int length) cout=Using Heap

6、 Sort= 1); memcpy(n,temp_n+1,length * sizeof(int); delete temp_n; / 基数排序接口void base_sort(int n,int length) cout=Using Merge Sort=endl;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

7、; i base; i+) boxi = new node; current = head = new node; /排序数据输入到当前链表中int max(0); for(i = 0;i next = new node; current - data = ni; if(max = ni) max = ni; / 找出最大的数 int k(0); while(max) max /= base; k+; / 计算最大数的位数int radix = 1; int order(0); node *p = 0; node *pnext = 0; for(i = 0; i next;/ 链表第一个节点名

8、师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 8 页 - - - - - - - - - / 拆链表while(current) order = (current - data / radix) % base; p = boxorder; while(p - next) p = p - next; p - next = current; current = current - next; p - next - next = 0; / 找到第一个节点int j (0); f

9、or(j = 0; j next) break; / 合链表head - next = p; while(p - next) p = p - next; /next node while(+j next) p - next = pnext; p = p - next; while( p - next) p = p - next; radix *= base; for(j = 0; j next = 0; /排序后将结果写入n 数组中current = head; for(i = 0; current = current - next ; i+) ni = current - data; /de

10、alloc pre = current = head; while(pre) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 8 页 - - - - - - - - - current = pre - next; delete pre; pre = current; for(i = 0; i base; i+) delete boxi; delete box; / 归并排序接口void merge_sort(int n,int length) cout=Using Mer

11、ge Sort=endl;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(nbigin1 nbigin2) tempi+ = nbigin1+; else tem

12、pi+ = nbigin2+; while(bigin1 = end1) tempi+ = nbigin1+; while(bigin2 = end2) tempi+ = nbigin2+; i = 0; while(first + i = last) return; int mid = (first + last)/ 2; mergesort(n,first,mid); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 8 页 - - - - - - - - - merg

13、esort(n,mid + 1,last); Merge(n,first,mid,last); / 快速排序void quicksort(int n,int first,int last) if(first = last) return ; int firstnum = first; int lastnum = last; int temp = nfirstnum; while(firstnum = temp & firstnum lastnum) lastnum-; nfirstnum = nlastnum; while(nfirstnum = temp & firstnum lastnum

14、) firstnum+; nlastnum = nfirstnum; nfirstnum = temp; quicksort(n,first,firstnum - 1); quicksort(n,lastnum + 1,last); / 快速排序接口void quick_sort(int n,int length) cout=Using Quick Sort=endl;quicksort(n,0,length - 1); / 希尔排序void shell_sort(int n,int length) cout=Using Shell Sort= 1) for(int i = dk; i 0 &

15、 temp nj - dk;j -= dk) nj = nj - dk; nj = temp; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 8 页 - - - - - - - - - dk = dk/2; / 冒泡排序void bubble_sort(int n,int length) cout=Using Bubble Sort=endl; int temp(0); for(int i = 0; i length; i+) for(int j = 0; j nj +

16、 1) temp = nj; nj = nj + 1; nj+1 = temp; / 选择排序void selection_sort(int n,int length) cout=Using Selection Sort=endl;int Guard(0); int k(0); for(int i = 0; i length - 1 ; i+) Guard = ni; k = i; for(int j = i + 1; j = length ; j+) if(nj nk) k = j; ni = nk; nk = Guard; / 插入排序void insertion_sort(int n,i

17、nt length) int temp(0); int i(0),j(0); cout=Using Insertion Sort=endl; for( i = 1; i 0 & temp nj-1; j-) nj = nj - 1; nj = temp; / 输出函数void Display(int n,int length,bool state) if(state) coutSorted Num:endl; else coutBefort Sort:endl; for(int i = 0; i length;i+) coutni ; coutendl; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 8 页 - - - - - - - - -