- 浏览: 64469 次
- 性别:
- 来自: 上海
文章分类
最新评论
-
sdylag:
0.double result = 6.0 / 83; //r ...
java对double型数字进行四舍五入 -
dyuan:
楼主,你好,能不能把ICTCLAS30.so这个库发给我呢,我 ...
ictclas linux开发注意事项 -
night_stalker:
lz 注定要杯具的,下面跑跑题:A话说,Ruby 1.9.2 ...
排列组合算法实现【学习】 -
yangtao309:
请看懂算法了的 给个留言好伐
不要看到标题 就投新手贴
只是希 ...
排列组合算法实现【学习】 -
downpour:
yangtao309 写道个人认为没有最好的方法来处理好主干与 ...
subversion 主干和分支 合并问题
排序就是将一组杂乱无章的数据按一定的规律排列起来(递增或递减)。
第一类:插入排序
基本原理,每步将一个待排序的对象,按其关键字大小,插入到前面已经排好序的一组对象适当位置上,直到对象全部插入为止。
1.直接插入排序(Insert Sort)
基本思想:
当插入第i个对象时,前面的V[1],V[2],…,V[i-1]已经排好序,此时,用v[i]的关键字与V[i-1], V[i-2],…的关键字顺序进行比较,找到插入位置即将V[i]插入,原来位置上对象向后顺移。
算法实现:
伪代码
java的实现方式
说明
算法中引入附加记录R[0]有两个作用:
其一是进入查找循环之前,它保存了R[i]的副本,使得不至于因记录的后移而丢失R[i]中的内容;
其二是在while循环“监视”下标变量j是否越界,一旦越界(即j<1),R[0]自动控制while循环的结束,从而避免了在while循环内的每一次都要检测j是否越界(即省略了循环条件j>=1)。因此,我们把R[0]称为“监视哨”。
说明二:算法复杂度
直接插入排序算法由两重循环组成,对于有n个记录的排序,内循环表明完成一趟排序所需进行的记录关键字间的比较和记录的后移。
若初始时关键字递增有序,这是最好情况。每一趟排序中仅需进行一次关键字的比较,所以总的比较次数为n-1。在while循环之前和之中,至少要移动记录两次,所以总的比较次数为2(n-1)。
若初始时关键字递减有序,这是最坏情况。这时的记录比较和移动次数分别为:
直接插入排序是一种稳定的排序方法。
原理:
关键字相同的两个对象,在整个排序过程中,不会通过比较而相互交换。
2.希尔排序(Shell Sort)
基本思想:
在插入排序中,只比较相邻的结点,一次比较最多把结点移动一个位置。如果对位置间隔较大距离的结点进行比较,使得结点在比较以后能够一次跨过较大的距离,这样就可以提高排序的速度。
设待排序的对象序列有n个对象,首先取一个整数gap<n作为间隔,将全部对象分为gap个子序列,所有距离为gap的对象放在同一个序列中,在每一个子序列中分别施行直接插入排序,然后缩小间隔gap,如取gap=gap/2,重复上述的子序列划分和排序工作,直到最后取gap为1为止。
算法实现c
java版本的算法实现
因为直接插入排序在初态为正序时所需时间最少,实际上,初态为基本有序时直接插入排序所需的比较和移动次数均较少。另一方面,当n值较小时,n和n2的差别也较小,即直接插入排序的最好时间复杂度O(n)和最坏时间复杂度O(n2)差别不大。在shell排序开始时增量较大,分组较多,每组的记录数目少,故各组内直接插入较快,后来增量逐渐缩小,分组数逐渐减少,而各组的记录数目逐渐增多,但组内元素已经过多次排序,数组已经比较接近有序状态,所以新的一趟排序过程也较块。
Shell最初的方案是 gap= n/2, gap=gap/2,直到gap=1。
Knuth的方案是gap = gap/3+1。
其它方案有:都取奇数为好;或gap互质为好等等。
对希尔排序的复杂度的分析很困难,在特定情况下可以准确地估算关键字的比较和对象移动次数,但是考虑到与增量之间的依赖关系,并要给出完整的数学分析,目前还做不到。
Knuth的统计结论是,平均比较次数和对象平均移动次数在n1.25 与1.6n1.25之间。
希尔排序是一种不稳定的排序方法。
第二类:交换排序
基本原理:两两比较待排序的对象的关键字,如果发生逆序,则交换之,直到全部对象都排好序为止。
两种常见的交换排序
1.起泡排序(Bubble Sort)
假设待排序的n个对象的序列为V[1],V[2],..., V[n],起始时排序范围是从V[1]到V[n]。
在当前的排序范围之内,自右至左对相邻的两个结点依次进行比较,让值较大的结点往下移(下沉),让值较小的结点往上移(上冒)。每趟起泡都能保证值最小的结点上移至最左边,下一遍的排序范围为从下一结点到V[n-1]。
在整个排序过程中,最多执行(n-1)遍。但执行的遍数可能少于(n-1),这是因为在执行某一遍的各次比较没有出现结点交换时,就不用进行下一遍的比较。
算法实现
基于c的伪码
java的实现
算法时间复杂度分析
考虑关键字的比较次数和对象移动次数
1、在最好情况下,初始状态是递增有序的,一趟扫描就可完成排序,关键字的比较次数为n-1,没有记录移动。
2、若初始状态是反序的,则需要进行n-1趟扫描,每趟扫描要进行n-i次关键字的比较,且每次需要移动记录三次,因此,最大比较次数和移动次数分别为:
2.快速排序(Quick Sort)
快速排序法是一种所需比较次数较少,目前在内部排序中速度较快的方法。
其思想是取待排序的结点序列中某个结点的值作为控制值,采用某种方法把这个结点放到适当的位置,使得这个位置的左边的所有结点的值都小于等于这个控制值,而这个位置的右边的所有结点的值都大于等于这个控制值。
算法实现:
c版本伪代码
java版本实现
算法时间复杂度分析:
考虑关键字的比较次数和对象移动次数
1、最坏情况是每次划分选取的基准都是当前无序区中关键字最小(或最大)的记录,划分的结果是基准的左边(或右边)为空,划分前后无序区的元素个数减少一个,因此,排序必须做n-1趟,每一趟中需做n-i次比较,所以最大比较次数为
2、最好情况是每次所取的基准都是当前无序区的“中值”记录,划分的结果是基准的左右两个无序子区的长度大致相等。
设C(n)表示对长度为n的序列进行快速排序所需的比较次数,显然,它应该等于对长度为n的无序区进行划分所需的比较次数n-1,加上递归地对划分所得的左右两个无序子区进行快速排序所需的比较次数。假设文件长度n=2k ,k=log2n,因此有:
快速排序的记录移动次数不会大于比较次数,所以,快速排序的最坏时间复杂度为O(n2);最好时间复杂度为O(nlog2n)。
可以证明,快速排序的平均时间复杂度也是O(nlog2n)。
快速排序是不稳定的排序方法。
第三类:选择排序
基本原理: 将待排序的结点分为已排序(初始为空)和未排序两组,依次将未排序的结点中值最小的结点插入已排序的组中。
选择排序:
1.直接选择排序
在一组对象V[i]到V[n-1]中选择具有最小关键字的对象
若它不是这组对象中的第一个对象,则将它与这组对象中
的第一个对象对调。
删除具有最小关键字的对象,在剩下的对象中重复第(1)、
(2)步,直到剩余对象只有一个为止。
算法实现:
c语言版本实现
java版本实现
算法复杂度分析:
1、无论初始状态如何,在第i趟排序中选择最小关键字的记录,需做n-i次比较,因此总的比较次数为:
2、当文件为正序时,移动次数为0,文件初态为反序时,每趟排序均要执行交换操作,总的移动次数取最大值3(n-1)。
直接选择排序是不稳定的排序方法。
2.堆排序(待续)
第一类:插入排序
基本原理,每步将一个待排序的对象,按其关键字大小,插入到前面已经排好序的一组对象适当位置上,直到对象全部插入为止。
1.直接插入排序(Insert Sort)
基本思想:
当插入第i个对象时,前面的V[1],V[2],…,V[i-1]已经排好序,此时,用v[i]的关键字与V[i-1], V[i-2],…的关键字顺序进行比较,找到插入位置即将V[i]插入,原来位置上对象向后顺移。
算法实现:
伪代码
Insertsort(rectype R[ ]) { int i,j; for (i=2;i<n;i++) { R[0]=R[i]; j=i-1; while (R[0].key<R[j].key) R[j+1]=R[j- -]; R[j+1]=R[0]; } }
java的实现方式
void insertSort(int[] sortIn) { for (int i = 1; i < sortIn.length; i++) { System.out.println("插入排序:" + Arrays.deepToString(new Object[]{sortIn})); int temp = sortIn[i]; int j = i - 1; while (j >= 0 && temp < sortIn[j]) { sortIn[j + 1] = sortIn[j];// 向后移动元素 j--; } sortIn[j + 1] = temp; } }
说明
引用
算法中引入附加记录R[0]有两个作用:
其一是进入查找循环之前,它保存了R[i]的副本,使得不至于因记录的后移而丢失R[i]中的内容;
其二是在while循环“监视”下标变量j是否越界,一旦越界(即j<1),R[0]自动控制while循环的结束,从而避免了在while循环内的每一次都要检测j是否越界(即省略了循环条件j>=1)。因此,我们把R[0]称为“监视哨”。
说明二:算法复杂度
引用
直接插入排序算法由两重循环组成,对于有n个记录的排序,内循环表明完成一趟排序所需进行的记录关键字间的比较和记录的后移。
若初始时关键字递增有序,这是最好情况。每一趟排序中仅需进行一次关键字的比较,所以总的比较次数为n-1。在while循环之前和之中,至少要移动记录两次,所以总的比较次数为2(n-1)。
若初始时关键字递减有序,这是最坏情况。这时的记录比较和移动次数分别为:
引用
直接插入排序是一种稳定的排序方法。
原理:
关键字相同的两个对象,在整个排序过程中,不会通过比较而相互交换。
2.希尔排序(Shell Sort)
基本思想:
在插入排序中,只比较相邻的结点,一次比较最多把结点移动一个位置。如果对位置间隔较大距离的结点进行比较,使得结点在比较以后能够一次跨过较大的距离,这样就可以提高排序的速度。
设待排序的对象序列有n个对象,首先取一个整数gap<n作为间隔,将全部对象分为gap个子序列,所有距离为gap的对象放在同一个序列中,在每一个子序列中分别施行直接插入排序,然后缩小间隔gap,如取gap=gap/2,重复上述的子序列划分和排序工作,直到最后取gap为1为止。
算法实现c
rectype R[n+d1]; int d[t]; Shellsort (rectype R[],int d) { int i,j,k,h; rectype temp; int maxint=32767; for (i=0;i<d[0];i++) R[i].key=-maxint; k=0; do { h=d[k]; for (i=h+dl;i<n+dl;i++) { temp=R[i]; j=i-h; while (temp.key<R[j].key) { p[j+h]=R[j]; j=j-h; } R[j+h]=temp; } k++; } while(h!=1); }
java版本的算法实现
/** *交换位置 */ private void swap(int a[], int i, int j) { int temp = a[i]; a[i] = a[j]; a[j] = temp; } /** * 希尔排序 Shell排序每次把数据分成若个小块,来使用插入排序,而且之后在这若个小块 * 排好序的情况下把它们合成大一点的小块,继续使用插入排序,不停的合并小块, * 知道最后成一个块,并使用插入排序。 这里每次分成若干小块是通过“增量” * 来控制的,开始时增量交大,接近N/2, 从而使得分割出来接近N/2个小块,逐渐的减小“增量“最终到减小到1。 */ void sheelSort(int[] sortIn) { int d = sortIn.length; while (d > 1) { d = (d + 1) / 2; System.out.println("希尔排序:" + Arrays.deepToString(new Object[]{sortIn})); for (int i = 0; i < sortIn.length - d; i++) { if (sortIn[i + d] < sortIn[i]) { swap(sortIn, i + d, i); } } } }
因为直接插入排序在初态为正序时所需时间最少,实际上,初态为基本有序时直接插入排序所需的比较和移动次数均较少。另一方面,当n值较小时,n和n2的差别也较小,即直接插入排序的最好时间复杂度O(n)和最坏时间复杂度O(n2)差别不大。在shell排序开始时增量较大,分组较多,每组的记录数目少,故各组内直接插入较快,后来增量逐渐缩小,分组数逐渐减少,而各组的记录数目逐渐增多,但组内元素已经过多次排序,数组已经比较接近有序状态,所以新的一趟排序过程也较块。
引用
Shell最初的方案是 gap= n/2, gap=gap/2,直到gap=1。
Knuth的方案是gap = gap/3+1。
其它方案有:都取奇数为好;或gap互质为好等等。
对希尔排序的复杂度的分析很困难,在特定情况下可以准确地估算关键字的比较和对象移动次数,但是考虑到与增量之间的依赖关系,并要给出完整的数学分析,目前还做不到。
Knuth的统计结论是,平均比较次数和对象平均移动次数在n1.25 与1.6n1.25之间。
希尔排序是一种不稳定的排序方法。
第二类:交换排序
基本原理:两两比较待排序的对象的关键字,如果发生逆序,则交换之,直到全部对象都排好序为止。
两种常见的交换排序
1.起泡排序(Bubble Sort)
假设待排序的n个对象的序列为V[1],V[2],..., V[n],起始时排序范围是从V[1]到V[n]。
在当前的排序范围之内,自右至左对相邻的两个结点依次进行比较,让值较大的结点往下移(下沉),让值较小的结点往上移(上冒)。每趟起泡都能保证值最小的结点上移至最左边,下一遍的排序范围为从下一结点到V[n-1]。
在整个排序过程中,最多执行(n-1)遍。但执行的遍数可能少于(n-1),这是因为在执行某一遍的各次比较没有出现结点交换时,就不用进行下一遍的比较。
算法实现
基于c的伪码
Bubblesort(rectype R[]) { int i, j, noswap; rectype temp; for (i=0; i<n-2; i++) { noswap=TRUE; for (j=n-1; j>=i; j- -) if (R[j+1].key<R[j].key) { temp=R[j+1]; R[j+1]=R[j]; R[j]=temp; noswap=FALSE; } if (noswap) break; } }
java的实现
/** *冒泡排序 算法思想是每次从数组末端开始比较相邻两元素,把第i小的冒泡到数组的第i个位置 */ void bubbleSort(int[] sortIn) { for (int i = 0; i < sortIn.length; i++) { System.out.println("冒泡排序:" + Arrays.deepToString(new Object[]{sortIn})); for (int j = sortIn.length - 1; j > i; j--) { if (sortIn[j] < sortIn[j - 1]) swap(sortIn, j - 1, j); } } }
算法时间复杂度分析
考虑关键字的比较次数和对象移动次数
1、在最好情况下,初始状态是递增有序的,一趟扫描就可完成排序,关键字的比较次数为n-1,没有记录移动。
2、若初始状态是反序的,则需要进行n-1趟扫描,每趟扫描要进行n-i次关键字的比较,且每次需要移动记录三次,因此,最大比较次数和移动次数分别为:
引用
2.快速排序(Quick Sort)
快速排序法是一种所需比较次数较少,目前在内部排序中速度较快的方法。
其思想是取待排序的结点序列中某个结点的值作为控制值,采用某种方法把这个结点放到适当的位置,使得这个位置的左边的所有结点的值都小于等于这个控制值,而这个位置的右边的所有结点的值都大于等于这个控制值。
算法实现:
c版本伪代码
int Partition(rectype R[],int l,int h) { int i, j; rectype temp; i=l; j=h; temp=R[i]; do {while ((R[j].key >= temp.key)&&(i<j)) j--; if (i<j) R[i++]=R[j]; while ((R[i].key<=temp.key)&&(i<j)) i++; if (i<j) R[j- -]=R[i]; } while (i!=j); R[i]=temp; return i; } Quicksort(rectype R[],int s1,int t1) { int i; if (s1<t1) { i=Partition(R,s1,t1); Quicksort (R,s1,i-1); Quicksort (R,i+1,t1); } }
java版本实现
/** *快速排序 (1)分解(2)求解(3)组合 */ void quickSort(int[] sortIn, int low, int high) { int pivotpos;// 划分后的基准记录的位置 if (low < high) {// 仅当区间长度大于1时才需排序 pivotpos = partition(sortIn, low, high);// 做划分 quickSort(sortIn, low, pivotpos - 1);// 对左区间进行递归排序 quickSort(sortIn, pivotpos + 1, high);// 对右区间进行递归排序 } } private int partition(int[] sortIn, int i, int j) { int pivot = sortIn[i]; while (i < j) { // 从右向左扫描,查找第一个关键字小于pivot的记录 while (i < j && sortIn[j] >= pivot) j--; if (i < j) { swap(sortIn, i, j);// 交换sortIn[i]和sortIn[j] i++; } System.out.println("从右向左扫描:" + Arrays.deepToString(new Object[]{sortIn})); // 从左向右扫描,查找第一个关键字大于pivot的记录 while (i < j && sortIn[i] <= pivot) i++; if (i < j) { swap(sortIn, i, j); j--; } System.out.println("从左向右扫描:" + Arrays.deepToString(new Object[]{sortIn})); } sortIn[i] = pivot;// 基准位置已被最终定位 System.out.println("标记:" + pivot); return i; }
算法时间复杂度分析:
考虑关键字的比较次数和对象移动次数
1、最坏情况是每次划分选取的基准都是当前无序区中关键字最小(或最大)的记录,划分的结果是基准的左边(或右边)为空,划分前后无序区的元素个数减少一个,因此,排序必须做n-1趟,每一趟中需做n-i次比较,所以最大比较次数为
2、最好情况是每次所取的基准都是当前无序区的“中值”记录,划分的结果是基准的左右两个无序子区的长度大致相等。
设C(n)表示对长度为n的序列进行快速排序所需的比较次数,显然,它应该等于对长度为n的无序区进行划分所需的比较次数n-1,加上递归地对划分所得的左右两个无序子区进行快速排序所需的比较次数。假设文件长度n=2k ,k=log2n,因此有:
快速排序的记录移动次数不会大于比较次数,所以,快速排序的最坏时间复杂度为O(n2);最好时间复杂度为O(nlog2n)。
可以证明,快速排序的平均时间复杂度也是O(nlog2n)。
快速排序是不稳定的排序方法。
第三类:选择排序
基本原理: 将待排序的结点分为已排序(初始为空)和未排序两组,依次将未排序的结点中值最小的结点插入已排序的组中。
选择排序:
1.直接选择排序
在一组对象V[i]到V[n-1]中选择具有最小关键字的对象
若它不是这组对象中的第一个对象,则将它与这组对象中
的第一个对象对调。
删除具有最小关键字的对象,在剩下的对象中重复第(1)、
(2)步,直到剩余对象只有一个为止。
算法实现:
c语言版本实现
Selectsort(rectype R[]) { int i, j, k; rectype temp; for (i=0;i<n-1;i++) { k=i; for (j=i+1;j<n;j++) if (R[j].key<R[k].key) k=j; if (k!=i) { temp=R[i]; R[i]=R[k]; R[k]=temp; } } }
java版本实现
/** *选择排序 在找到全局第i小的时候记下该元素位置,最后跟第i个元素交换,从而保证数组最终的有序 */ void selectSort(int[] sortIn) { int i, j, min = 0; for (i = 0; i < sortIn.length; i++) { System.out.println("选择排序:" + Arrays.deepToString(new Object[]{sortIn})); min = i; for (j = i; j < sortIn.length; j++) {// 每一趟都选择一个最小的 if (sortIn[j] < sortIn[min]) min = j; } // 交换 swap(sortIn, i, min); } }
算法复杂度分析:
1、无论初始状态如何,在第i趟排序中选择最小关键字的记录,需做n-i次比较,因此总的比较次数为:
2、当文件为正序时,移动次数为0,文件初态为反序时,每趟排序均要执行交换操作,总的移动次数取最大值3(n-1)。
直接选择排序是不稳定的排序方法。
2.堆排序(待续)
发表评论
-
排列组合算法实现【学习】
2010-08-16 11:56 1795一个从M个数字里面取N个数字的组合 没用到递归的实现,将选取的 ... -
ictclas linux开发注意事项
2010-01-08 14:04 2480ictclas linux开发注意事项 在windows上开发 ... -
J2EE开发中分页组件总结
2009-09-29 14:32 1817J2EE开发中少不了要用到分页的。在持久层Hibernate中 ... -
Java使用Memcached
2009-09-11 13:30 891转载http://space.itpub.net/583467 ... -
web开发中公用组件的开发之一---------DateUtils
2009-07-24 11:39 870web开发中公用组件的开发之一---------DateUti ... -
java操作Oracle存储过程,以及生成Excel报表
2009-06-26 14:55 4429引子 在企业应用系统中,经常会要要求生成报表。 偶 ... -
ArrayList和LinkedList的用法区别
2009-06-16 16:54 14651.ArrayList是实现了基于动态数组的数据结构,Link ... -
struts2 token令牌
2009-06-11 10:34 1808为了 防止F5刷性重复提 ... -
一个不常见的异常或错误
2009-05-27 14:35 1025在eclipse控制台打印如下信息, JDK1.5 TOMCA ... -
在postgreSQL数据库上 SSH应用开发bug记录
2009-04-11 12:23 1019前言 : 把之前开发好的项目从oracle数据库移植 ... -
i++循环与i--循环的执行效率
2009-03-17 14:36 723转载时请注明出处和作者联系方式 文章出处:http://www ... -
多线程设计要点
2009-01-04 09:36 8101.多线程中有主内存和工作内存之分, 在JVM中,有一个主内存 ... -
使用模板模式简化DAO操作Hibernate
2008-12-25 11:24 867相信使用过Spring + Hibernate开发过的人,在写 ... -
选用ibatis和hibernate的区别
2008-12-25 10:29 2117Hibernate简介 Hibernate是一个开放源代码的对 ... -
java性能优化,从细节说起
2008-12-23 14:06 894一、避免在循环条件中 ...
相关推荐
数据结构各种排序算法实现及比较 数据结构各种排序算法实现及比较 数据结构各种排序算法实现及比较
java各种排序算法实现,仅供参考。java各种排序算法实现,仅供参考。
编程实现选择、冒泡、直接插入、希尔、快速、堆、归并等几种排序算法,并计算每种算法的比较、移动次数。 完成功能的详细说明: 1.要求待排序数据从磁盘文件读入,实施排序后将数据写入另一文件。 2.实现选择、...
各种排序算法——直接顺序排序,希尔排序,起泡排序,快速排序,简单选择排序,筛选法调整堆,堆排序,一次归并,一趟归并,归并排序的非递归算法……
各种常见排序算法实现,包括简单插入排序,冒泡排序,希尔排序
数据结构排序算法实现,文档中进行了比较,而且有代码!
各种排序算法的实验代码。分别有直接排序、选择排序、二叉排序、折半排序、堆排序、冒泡排序、快速排序等。在dev c++上运行通过并完美实现功能。vc未测试。
数据结构中的多种排序算法实现程序,对学者很有帮助,我编译过运行很成功
C#实现的各种排序算法。对比了执行效率等。
各种排序算法的实现
实验四 查找和排序算法实现 1、各种排序算法的实现 2、各种查找算法实现 1、各种排序算法的实现 用随机函数生成16个2位正整数(10~99),实现插入排序、选择排序、冒泡排序、双向冒泡、快速排序、二路归并排序等多种...
Java排序算法实现 Java排序算法实现 Java排序算法实现
实现合并排序,插入排序,希尔排序,快速排序,冒泡排序,桶排序算法的java实现。
这是我们实验课做的一个东西。。C++实现。里面包括源文件,EXE,和实验报告,是用VS2008做的
有选择排序,冒泡排序,希尔排序,插入排序,归并排序算法
利用前端动画实现算法可视化,比如各种排序算法动画实现.zip
C++实现的各种排序算法的实验(源代码+实验报告),包括快速排序,堆排序等的实现
实验平台vc60,包括: 冒泡排序 直接插入排序 简单选择排序 希尔排序 二路插入排序 折半插入排序
各种排序算法java实现各种排序算法java实现各种排序算法java实现各种排序算法java实现各种排序算法java实现