- 浏览: 128661 次
- 性别:
- 来自: 成都
最新评论
-
yi_chao_jiang:
你好,多谢分享,问个问题,在上传数据的时候判断文件是否有上传记 ...
断点续传和下载原理分析 -
a41606709:
为什么我的tabhost显示不出来? 怎么设置在全部页面中让他 ...
TabActivity中的Tab标签详细设置 -
Zero颴:
大神篇,思路,配图都很清晰,perfect!
Android事件模型之interceptTouchEvnet ,onTouchEvent关系正解 -
QAZ503602501:
牛死人了!!!
B-树 -
mengsina:
很牛的文档。数学功底好啊
Android Matrix理论与应用详解
这里面包含了所有常见的排序操作
1.性能等比较分析
2.代码实现
sort.h
//各种排序方法总结 #ifndef SORT_H #define SORT_H template<class T> class Sort{ public: void insertSort(T r[], int n); //直接顺序排序 void shellSort(T r[], int n); //希尔排序 void bubbleSort(T r[], int n); //起泡排序 void quickSort(T r[], int first, int end); //快速排序 void selectSort(T r[ ], int n); //简单选择排序 void heapSort(T r[ ], int n); //堆排序 void mergeSort1(T r[ ], T r1[ ], int n ); //归并排序的非递归算法 void mergeSort2(T r[], T r1[], T r2[],int s, int t);//归并排序的递归算法 private: int partition(T r[], int first, int end); //快速排序一次划分 void sift(T r[], int n, int hole); //筛选法调整堆 void merge(T r[], T r1[], int s, int m, int t);//一次归并 void mergePass(T r[ ], T r1[ ], int n, int h); //一趟归并 }; #endif
sort.cpp
#include <iostream> #include "sort.h" using namespace std; //直接顺序排序 template<class T> void Sort<T>::insertSort(T r[], int n){ if(n <= 0) return; int i, j; for(i=2; i<n; i++){ r[0] = r[i]; j = i-1; while(r[0]<r[j]){ r[j+1] = r[j]; j--; } r[j+1] = r[0]; } } //希尔排序 template<class T> void Sort<T>::shellSort(T r[], int n){ if(n <= 0) return; int i,j,d; //增量d不断变化 for(int d=n/2; d>0; d = d/2){ //对于每个增量,都是直接插入排序 for(i = d+1; i<n; i+=d){ r[0] = r[i]; j = i-d; while(r[0]<r[j] && j>0){ r[j+d] = r[j]; j-=d; } r[j+d] = r[0]; } } } //起泡排序 template<class T> void Sort<T>::bubbleSort(T r[], int n){ T tmp = 0; //用于交换 int exchanged = 1; //记录是否发生交换 int bound,pos = n-1; //最后一次的交换位置 while(exchanged){ bound = pos; exchanged = 0; for(int j=0; j<bound; j++){ if(r[j]>r[j+1]){ tmp = r[j]; r[j] = r[j+1]; r[j+1] = tmp; pos = j; exchanged = 1; } } } } //快速排序一次划分 template<class T> int Sort<T>::partition(T r[], int first, int end){ T tmp; int i=first, j=end; while(i<j){ while(r[i]<r[j] && i<j) j--; if(i<j){ tmp = r[i]; r[i] = r[j]; r[j] = tmp; i++; } while(r[i]<r[j] && i<j) i++; if(i<j){ tmp = r[i]; r[i] = r[j]; r[j] = tmp; j--; } } return i; } //快速排序 template<class T> void Sort<T>::quickSort(T r[], int first, int end){ int k; if(first < end){ k = partition(r, first, end); //对左右递归排序 quickSort(r, first, k-1); quickSort(r, k+1, end); } } //简单选择排序 template<class T> void Sort<T>::selectSort(T r[ ], int n){ T tmp; int i, pos; for(i=0; i<n; i++){ pos = i; for(int j=i+1; j<n; j++){ if(r[j] < r[pos]) pos = j; } if(pos != i){ tmp = r[pos]; r[pos] = r[i]; r[i] = tmp; } } } //筛选法调整堆 template<class T> void Sort<T>::sift(T r[], int n, int hole){ int child; T tmp = r[hole]; for(; hole*2 <= n; hole = child){ child = hole*2; if(child != n && r[child+1] < r[child]){//右子树 child++; } //如果当前比hole小,交换 if(r[child]<tmp){ r[hole] = r[child]; }else{ break; } } //hole是最后交换的位置 r[hole] = tmp; } //堆排序 template<class T> void Sort<T>::heapSort(T r[ ], int n){ for(int i=n/2; i>0; i--){ sift(r, n, i); } //重复移除第一个元素,并重建堆 while(n>0){ r[0] = r[1]; r[1] = r[n]; r[n] = r[0]; n--; sift(r, n, 1); } } /* //这个写的比较容易理解,非常好!!From v_july_v template<class T> void Sort<T>::sift(T heap[], int i, int len) { int min_index = -1; int left = 2 * i; int right = 2 * i + 1; T tmp; //反正就是找其左右子树小的,然后递归 if (left <= len && heap[left] < heap[i]) min_index = left; else min_index = i; if (right <= len && heap[right] < heap[min_index]) min_index = right; if (min_index != i) { // 交换结点元素 tmp = heap[i]; heap[i] = heap[min_index]; heap[min_index] = tmp; sift(heap, min_index, len); } } // 建立小根堆 template<class T> void Sort<T>::buildHeap(T heap[], int len) { if (heap == NULL) return; int index = len / 2; for (int i = index; i >= 1; i--) sift(heap, i, len); } */ //一次归并(有序序列r(开始位置分别为s,m的两个序列),将合并结果放入r1) template<class T> void Sort<T>::merge(T r[], T r1[], int s, int m, int t){ int i=s; int j=m+1; int k=s; while (i<=m && j<=t) { if (r[i]<=r[j]) r1[k++]=r[i++]; //取r[i]和r[j]中较小者放入r1[k] else r1[k++]=r[j++]; } if (i<=m) while (i<=m) //若第一个子序列没处理完,则进行收尾处理 r1[k++]=r[i++]; else while (j<=t) //若第二个子序列没处理完,则进行收尾处理 r1[k++]=r[j++]; } //一趟归并 template<class T> void Sort<T>::mergePass(T r[ ], T r1[ ], int n, int h){ int i=0; int k; while (i<=n-2*h) //待归并记录至少有两个长度为h的子序列 { merge(r, r1, i, i+h-1, i+2*h-1); i+=2*h; } if (i<n-h) merge(r, r1, i, i+h-1, n); //待归并序列中有一个长度小于h else for (k=i; k<=n; k++) //待归并序列中只剩一个子序列 r1[k]=r[k]; } //归并排序的非递归算法 template<class T> void Sort<T>::mergeSort1(T r[ ], T r1[ ], int n ){ int h=1; int i; while (h<n) { mergePass(r, r1, n-1, h); //归并 h=2*h; mergePass(r1, r, n-1, h); h=2*h; } for(i=0;i<n;i++) cout<<r[i]<<" "; cout<<"\n"; } //归并排序的递归算法 template<class T> void Sort<T>::mergeSort2(T r[], T r1[], T r2[],int s, int t){ int m; if (s==t) { r1[s]=r[s]; } else { m=(s+t)/2; mergeSort2(r, r2, r1, s, m); //归并排序前半个子序列 mergeSort2(r, r2, r1, m+1, t); //归并排序后半个子序列 merge(r2, r1, s, m, t); //将两个已排序的子序列归并 } }
main.cpp
#include <iostream> #include "sort.cpp" using namespace std; int main(){ const int numv=11; //赋值 int a[]={0,3,56,32,78,5,24,9,64,34,7}; //插入排序的时候a[0]是作为了哨兵 int b[]={0,4,6,23,45,15,10,36,25,79,21}; //希尔排序的时候a[0]是作为了哨兵 int c[]={38,23,56,2,79,42,93,29,6,5,57}; int d[]={50,23,45,67,87,14,29,32,44,97,89}; int e[]={8,6,1,48,37,63,39,74,52,26,49}; int f[]={0,12,23,45,87,2,6,15,43,26,40}; //堆的第一个位置也是暂存 int g[]={13,10,23,45,64,34,24,7,9,3,16}; int h[]={34,23,54,76,12,13,14,11,78,8,9}; int g1[numv]; int h1[numv]; int h2[numv]; Sort<int> s; int j; /* cout << "\n直接顺序排序前:" << "\n"; for(int j=1;j<numv;j++) cout<<a[j]<<" "; cout << "\n直接顺序排序结果为:" << "\n"; s.insertSort(a,numv); for(int j=1;j<numv;j++) cout<<a[j]<<" "; cout << "\n希尔排序前:" << "\n"; for(j=1;j<numv;j++) cout<<b[j]<<" "; cout << "\n希尔排序结果为:" << "\n"; s.shellSort(b, numv); for(j=1;j<numv;j++) cout<<b[j]<<" "; cout << "\n起泡排序前:" << "\n"; for(int k=0;k<numv;k++) cout<<c[k]<<" "; cout << "\n起泡排序结果为:" << "\n"; s.bubbleSort(c, numv); for(int k=0;k<numv;k++) cout<<c[k]<<" "; cout << "\n快速排序前:" << "\n"; for(j=0;j<numv;j++) cout<<d[j]<<" "; cout << "\n快速排序结果为:" << "\n"; s.quickSort(d,0,numv-1); for(int i=0;i<numv;i++) cout<<d[i]<<" "; cout<<"\n"; cout << "\n简单选择排序前:" << "\n"; for(j=0;j<numv;j++) cout<<e[j]<<" "; cout << "\n简单选择排序结果为:" << "\n"; s.selectSort(e,numv); for(j=0;j<numv;j++) cout<<e[j]<<" "; cout << "\n堆排序前:" << "\n"; for(j=0;j<numv;j++) cout<<f[j]<<" "; cout << "\n堆排序结果为:" << "\n"; s.heapSort(f, numv); for(j=1;j<numv;j++) cout<<f[j]<<" "; */ cout << "\n归并排序非递归算法前:" << "\n"; for(j=0;j<numv;j++) cout<<g[j]<<" "; cout << "\n归并排序非递归算法的结果为:" << "\n"; s.mergeSort1(g, g1,numv ); cout << "\n归并排序递归算法前:" << "\n"; for(j=0;j<numv;j++) cout<<h[j]<<" "; cout << "\n归并排序递归算法的结果为:" << "\n"; s.mergeSort2(h,h1,h2, 0, numv-1); for(int i=0; i < numv; i++) cout<<h1[i]<<" "; cout<<"\n"; return 0; }
发表评论
-
常见字符串操作大全
2012-08-12 11:34 14161.常见的字符串操作 如计算长度,求子串等都是考验基本功的, ... -
KMP算法解析
2012-08-12 11:35 2774一.理论基础 1.什么 ... -
二叉堆的实现
2012-08-12 11:35 11741.堆的概念 这里只需要注意两点: a.堆的存储方式:就是 ... -
set和map的简单实现
2012-08-10 11:35 12761.Set的简单实现 set是利用二叉查找树来实现的,而且为 ... -
红黑树的插入总结
2012-08-10 11:25 9071.红黑树 这个在july的博客中有详尽的说明,我就不在赘述 ... -
B-树实现
2012-08-10 11:03 15871.什么是B-树? 这个在我的前一篇博客中已经详细的阐释过: ... -
平衡二叉树
2012-08-10 10:39 27941.问题描述 什么是平衡 ... -
二叉排序树
2012-08-10 10:25 14161.基本概念 二叉排 ... -
B-树
2012-07-04 22:48 56101.B-树的概念 是一种多 ... -
构造哈夫曼树
2012-07-04 10:40 11871.算法说明 就是建造哈夫曼树树,从而使得构造出的树带权路径 ... -
线索二叉树
2012-07-04 09:20 12371.算法描述 就是简单的线索二叉树的建立,遍历,查找等基本操 ... -
二叉树基本操作大全
2012-07-03 18:22 25541.二叉树的基本操作 这里我有一个疑问: 在使用构造 ... -
多种队列的实现
2012-06-29 10:09 14921.算法描述 a.数据结构与算法(Mark Allen We ... -
栈的各种实现
2012-06-28 16:34 10751.算法描述 a.实现二个栈,在一个数组里面,除非没有任何空 ... -
中缀表达式转换为后缀
2012-06-28 11:10 17501.算法描述 例如a+b*c这是常见的中缀表达式,但是 ... -
后缀表达式的值
2012-06-27 16:33 12891.算法描述 计算后缀表达式的值 2.事例 如:( ... -
Josephus问题
2012-06-21 15:30 9531.算法描述 简单的游戏:有N个人坐成一圈,编号1-N、从编 ... -
关于最长递增子序列的实际应用--动态规划
2012-06-07 11:35 1788参考链接: a.http://www.programfan. ... -
线性查找二维数组
2012-06-05 17:23 9991.算法描述 有序(行有序,列有序,且每行从左至右递增 ... -
整数的随机置换
2012-06-05 15:10 2231算法描述:生成前N个整 ...
相关推荐
【数据结构的内部排序总结】1 / 10 数据结构排序方法总结全文共10页,当前为第1页。数据结构排序方法总结全文共10页,当前为第1页。数据结构的内部排序 数据结构排序方法总结全文共10页,当前为第1页。 数据结构排序...
java集合排序方法总结共13页.pdf.zip
数据结构排序方法总结.pdf
列举了多种排序方法,包括快速排序,锦标赛排序,堆排序和归并排序
该文档中包含了常见的几种排序方法,其中说明了排序的主要思想和程序源代码,供需要者使用!
几种常用排序算法的比较和分析
js代码-常用排序方法总结
总结各类排序方法。排序问题一直是计算机技术研究的重要问题,排序算法的好坏直接影响程序的执行速度和辅助存储空间的占有量。此代码将详细分析常见的各种排序算法,并从时间复杂度、空间复杂度、适用情况等多个方面...
对冒泡排序,直接插入排序,简单选择排序,快速排序,希尔排序,堆排序这六种常用的内排序方法的掌握,通过对各种排序算法的分析,对其关键字的比较次数和移动次数进行分析,运用数据结构所学的知识将其用程序实现。
本篇文章是对C中常用的三种排序方法总结以及探讨分析的概述,需要的朋友参考下
八大排序方法详细图形解释,和算法复杂度分析,及最后总结。 1.直接插入排序 2.希尔排序 3.简单选择排序 4.堆排序 5.冒泡排序 6.快速排序 7.归并排序 8.基数排序
排序算法,就是如何使得记录按照要求排列的方法。排序算法在很多领域得到相当地重视,尤其是在大量数据的处理方面。一个优秀的算法可以节省大量的资源。在各个领域中考虑到数据的各种限制和规范,要得到一个符合实际...
排序和算法大全C++ 各种算法 排序方法总结
asort:对数组进行排序并保持索引关系 arsort:对数组进行逆向排序并保持索引关系 ksort:对数组按照键名排序,保留键名到数据的关联 krsort:对数组按照键名逆向排序,保留键名到数据的关联 natsort:对字母
本资源总结了在java中出现的各种排序方法