- 浏览: 105925 次
- 性别:
- 来自: 广州
最新评论
-
xinhemei:
我试了试,发现gmail和163的不行。好像ajax请求失败了 ...
jQuery实现邮箱自动登录 -
酒鬼_yuan:
我正在找 谢谢了
关于yui的学习
/* * To change this template, choose Tools | Templates * and open the template in the editor. */ package nc.norman.sorter; /** *折半插入排序 * @author NC * @version 1.0 */ public class BInsertSorter extends Sorter { @Override public void sort(SortArray array, boolean order) { int n = array.length; int i, j, low, high, m; for (i = 2; i <= n; i++) { array.setKey(i); //保存关键字 low = 1;//设定比较区间 high = i - 1; while (low <= high) { m = (low + high) / 2; if (array.compareToKey(m, !order)) { high = m - 1;//插入点在低半区 } else { low = m + 1;//插入点在后半区 } } //找到插入点,开始移动,插入 for (j = i - 1; j >= high + 1; j--) { array.setElement(j + 1, array.getElement(j)); array.addMoveCount(); } array.addInsertCount(); array.setElement(high + 1, array.getKey()); //插入正确的位置 } } }
/* * To change this template, choose Tools | Templates * and open the template in the editor. */ package nc.norman.sorter; /** * 冒泡排序 * 方法:相邻两元素进行比较,如有需要则进行交换,每完成一次循环就将最大元素排在最后(如从小到大排序),下一次循环是将其他的数进行类似操作。 * 性能:比较次数O(n^2),n^2/2;交换次数O(n^2),n^2/4 * @author NC * @version 1.0 */ public class BubbleSorter extends Sorter { @Override public void sort(SortArray array, boolean order) { int n = array.length; int i, j, flag = 1; for (i = n; i > 1 && flag == 1; i--) {//该趟最后一个数为关键字,假定为最大的;要求当一趟冒泡过程中不再有数据交换,则排序结束 flag = 0; for (j = 1; j <= i - 1; j++) { if (array.compare(j, j + 1, !order)) { //关键字前面的数相邻(注意是相邻)两两比较,大的就往后冒 array.swap(j, j + 1); flag = 1; } } } } }
/* * To change this template, choose Tools | Templates * and open the template in the editor. */ package nc.norman.sorter; /** *桶排序的思想就是把区间[0,1)划分成n个相同大小的子区间,或称桶,然后将n个输入数分布到各个桶中去。 * 因为输入数均匀分布在[0,1)上,所以一般不会有很多数落在 一个桶中的情况。为得到结果,先对各个桶中的数进行排序,然后按次序把各桶中的元素列 出来即可。 * @author NC */ public class BucketSorter extends Sorter { //这个方法只设正序的 @Override public void sort(SortArray array, boolean order) { sort(array.getArray(),0,array.length,array.length*2); //SortArray的随机数据是1到两倍数组长度之间 } public void sort(int[] array, int from, int len, int max) { int[] temp = new int[len]; int[] count = new int[max]; //分配到各个桶里面 for (int i = 0; i < len; i++) { count[array[from + i]]++; } //对每个桶排序 for (int i = 1; i < max; i++) { count[i] = count[i] + count[i - 1]; } //按顺序把每个桶中的元素列出来 System.arraycopy(array, from, temp, 0, len); for (int k = len - 1; k >= 0; k--) { array[--count[temp[k]]] = temp[k]; } } }
/* * To change this template, choose Tools | Templates * and open the template in the editor. */ package nc.norman.sorter; /** * 计数排序 * @author NC * @version */ public class CountSorter extends Sorter { @Override public void sort(SortArray array, boolean order) { int n = array.length; int[] ds = new int[n]; //分配临时空间 int i, j, count = 0; for (j = 1; j <= n; j++) { count = 0; for (i = 1; i <= n; i++) { if (i != j)//关键字与其他数比较 { if (array.compare(i, j, order)) { count++; } else if (array.equal(i, j) && j < i) { //j<i保证排序的稳定性,去掉时当数据有一样大时会出错 count++; } } } ds[count] = array.getElement(j); } array.setArray(ds); } }
/* * To change this template, choose Tools | Templates * and open the template in the editor. */ package nc.norman.sorter; /** * 堆排序 * @author NC * @version 1.0 */ public class HeapSorter extends Sorter { private static int heapAdjust(SortArray array, int start, int end, boolean order) { int flag = 0; int left = 0; int right = 0; int max = 0; left = start * 2; right = start * 2 + 1; while (left <= end) { max = left; if (right <= end) { if (array.compare(left, right, order)) { max = right; } else { max = left; } } if (array.compare(start, max, order)) { array.swap(start, max); flag = 1; start = max; } else { break; } left = start * 2; right = start * 2 + 1; } return flag; } private static void buildHeap(SortArray array, boolean order) { int n = array.length; int i; for (i = n / 2; i > 0; i--) { heapAdjust(array, i, n, order); } } @Override public void sort(SortArray array, boolean order) { int n = array.length; int i; buildHeap(array, order); for (i = n; i > 1; i--) { array.swap(1, i); heapAdjust(array, 1, i - 1, order); } } }
/* * To change this template, choose Tools | Templates * and open the template in the editor. */ package nc.norman.sorter; /** * 插入排序 * 方法:将一个记录插入到已排好序的有序表(有可能是空表)中,从而得到一个新的记录数增1的有序表。 * 性能:比较次数O(n^2),n^2/4 * 复制次数O(n),n^2/4 * 比较次数是前两者的一般,而复制所需的CPU时间较交换少,所以性能上比冒泡排序提高一倍多,而比选择排序也要快。 * @author NC * @version 1.0 */ public class InsertSorter extends Sorter { @Override public void sort(SortArray array, boolean order) { int n = array.length; int i, j; for (i = 2; i <= n; i++) { if (array.compare(i, i - 1, order)) {//比关键字大的话 array.setKey(i); //暂存关键字 array.setElement(i, array.getElement(i - 1)); //比关键字大,后移(前面已经比较过了) array.addMoveCount(); for (j = i - 1; j >= 1 && array.compareToKey(j, !order); j--) {//比关键字大,后移;比关键字小的话,就退出,找到要插入的位置了 array.setElement(j + 1, array.getElement(j)); array.addMoveCount(); } array.setElement(j + 1, array.getKey()); //插入正确的位置 array.addInsertCount(); } } } }
/* * To change this template, choose Tools | Templates * and open the template in the editor. */ package nc.norman.sorter; /** * 归并排序 * @author NC * @version 1.0 */ public class MergeSorter extends Sorter { //非递归归并排序 @Override public void sort(SortArray array, boolean order) { int n = array.length; int beforeLen = 1; //合并前序列的长度 int afterLen = 1;//合并后序列的长度 for (beforeLen = 1; afterLen <= n; beforeLen = afterLen) { afterLen = beforeLen << 1; //合并后序列的长度是合并前的两倍 int i = 1;//开始合并时第一个序列的起始位置下标,每次都是从1开始 while (i + afterLen - 1 <= n) {//足够分成两个子表 Merge(array, i, i + beforeLen - 1, i + afterLen - 1, order); i += afterLen; } if (i + beforeLen <= n) { Merge(array, i, i + beforeLen - 1, n, order); } } } //递归归并排序 public void mergeSort2(SortArray array, boolean order) { mergeSort(array, 1, array.length, order); } //递归归并排序 public void mergeSort2(SortArray array) { mergeSort(array, 1, array.length, Sorter.POSITIVE); } private void mergeSort(SortArray array, int left, int right, boolean order) { if (left < right) { int center = (left + right) / 2; mergeSort(array, left, center, order); mergeSort(array, center + 1, right, order); Merge(array, left, center, right, order); } } private void Merge(SortArray array, int left, int center, int right, boolean order) { //[1,2,3,4] left=1,ceter=2,right=4 int[] temp = new int[right - left + 1];//存放被合并后的元素 int i = left; int j = center + 1; int k = 0; while (i <= center && j <= right) { array.addInsertCount(); if (array.compare(i, j, order)) { temp[k++] = array.getElement(i++); } else { temp[k++] = array.getElement(j++); } } while (i <= center) { array.addInsertCount(); temp[k++] = array.getElement(i++); } while (j <= right) { array.addInsertCount(); temp[k++] = array.getElement(j++); } //把t[]的元素复制回a[] for (i = left, k = 0; i <= right; i++, k++) { array.setElement(i, temp[k]); } } }
/* * To change this template, choose Tools | Templates * and open the template in the editor. */ package nc.norman.sorter; /** * 奇偶交换排序 * @author NC * @version */ public class ParitySorter extends Sorter { @Override public void sort(SortArray array, boolean order) { int n = array.length; int i = 0, j = 0, tag = 1; for (j = 0; j < n; j++) { for (i = j % 2 + 1; i <= n - 1; i += 2) { //每次仅对奇数或偶数下标处理,步长为2 if (array.compare(i, i + 1, !order)) { array.swap(i, i + 1); tag = 0;//记录比较趟数 } } tag++; if (tag == 3) { break; } /*如果待排序列本身已经有序, 则只需执行再次内层循环即对奇偶下标元素分别扫描一次 就可判断出序列已经有序*/ } } }
/* * To change this template, choose Tools | Templates * and open the template in the editor. */ package nc.norman.sorter; /** * 快速排序 * 快速排序使用分治法(Divide and conquer)策略来把一个序列(list)分为两个子序列(sub-lists)。 * 步骤为: * 1. 从数列中挑出一个元素,称为 "基准"(pivot), * 2. 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。 * 在这个分割之后,该基准是它的最后位置。这个称为分割(partition)操作。 * 3. 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。 * 递回的最底部情形,是数列的大小是零或一,也就是永远都已经被排序好了。 * 虽然一直递回下去,但是这个算法总会结束,因为在每次的迭代(iteration)中,它至少会把一个元素摆到它最后的位置去。 * @author NC * @version 1.0 */ public class QuickSorter extends Sorter { private int partition(SortArray array, int low, int high, boolean order) { int key = array.getElement(low); //用子表的第一个记录作为枢轴记录 while (low < high) {//从表的两端交替地向中间扫描 while (low < high && array.compareNotMoreThan(array.getElement(high), key, !order)) { high--; } array.setElement(low, array.getElement(high)); while (low < high && array.compareNotMoreThan(array.getElement(low), key, order)) { low++; } array.setElement(high, array.getElement(low)); array.addExchangeCount(); } array.setElement(low, key); array.addInsertCount(); return low; } private void qSort(SortArray array, int low, int high, boolean order) { int pivotloc; if (low < high) {//保证长度大于1,递归的出口 pivotloc = partition(array, low, high, order); //将表low-high一分为2,用枢轴位置来分 qSort(array, low, pivotloc - 1, order); //对低子表递归排序 qSort(array, pivotloc + 1, high, order); //对高子表递归排序 } } @Override public void sort(SortArray array, boolean order) { int n = array.length; qSort(array, 1, n, order); } }
/* * To change this template, choose Tools | Templates * and open the template in the editor. */ package nc.norman.sorter; /** * 选择排序 * 方法:每一趟从待排序的数据元素中选出最小(或最大)的一个元素, 顺序放在已排好序的数列的最后,直到全部待排序的数据元素排完。 * 性能:比较次数O(n^2),n^2/2 * 交换次数O(n),n * 交换次数比冒泡排序少多了,由于交换所需CPU时间比比较所需的CUP时间多,所以选择排序比冒泡排序快。 * 但是N比较大时,比较所需的CPU时间占主要地位,所以这时的性能和冒泡排序差不太多,但毫无疑问肯定要快些。 * @author NC * @version 1.0 */ public class SelectSorter extends Sorter { @Override public void sort(SortArray array, boolean order) { int n = array.length; int x, k, i, j; for (i = 1; i < n; i++) { k = i; //暂时定为最小的关键字 for (j = i + 1; j <= n; ++j) { if (array.compare(j, k, order)) { k = j; //与i之后的n-i个数依次比较,记录小值下标 } } if (k != i) {//k值改变,原先定的不是最小。找到最小的,交换 array.swap(i, k); } } } }
/* * To change this template, choose Tools | Templates * and open the template in the editor. */ package nc.norman.sorter; /** * 希尔排序 * @author NC * @author 1.0 */ public class ShellInsertSorter extends Sorter { @Override public void sort(SortArray array, boolean order) { int n = array.length; int k = n / 2; while (k > 0) { shellInsert(array, k, order); k = k / 2; //分配增量 } } private void shellInsert(SortArray array, int dk, boolean order) { int n = array.length; //dk为增量 int i, j; for (i = dk + 1; i <= n; i++) { //共n-(dk+1)+1个子序列,分别进行直接插入排序 if (array.compare(i, i - dk, order)) {//比关键字大的话 array.setKey(i); //暂存关键字 for (j = i - dk; j > 0 && array.compareToKey(j, !order); j = j - dk) {//比关键字小的就退出,找到位置了。j<=0说明方序列已经是有序的 array.setElement(j + dk, array.getElement(j)); //记录后移,找到插入位置时退出 array.addMoveCount(); } array.setElement(j + dk, array.getKey()); //插入关键字 array.addInsertCount(); } } } }
源码请见上一篇的附件
相关推荐
通过几组有代表意义的随机数据的比较,算出几种这几种排序算法的关键字比较次数和关键字移动次数,以便我们分析算法效率。 1、通过修改程序,实现程序在要求的数据量下求出以下六种内部排序算法的移动次数和比较次数...
各种排序算法效率分析比较及源代码 C语言实现 各种排序包括: 直接插入排序,折半插入排序,2—路插入排序和表插入排序;希尔排序和链式基数排序;起泡排序,快速排序,归并排序;简单选择排序,树形选择排序和堆...
由资深算法研究者 编写的排序算法 动态分析 软件 帮助你 更加直观的理解排序算法过程, 并且简化 算法测试过程。不可多得的 帮手
不同排序算法时间效率的经验分析方法 验证理论分析与经验分析的一致性 void Init_Random();//数组随机数初始化函数声明 void Show_Array();//展示排序结果 void Select_Sort();//选择排序函数声明 void Bubble_...
多种排序方式实现及效率分析,方法结论清晰,有代码实现和结果分析图示。
不同排序算法时间效率的经验分析方法 验证理论分析与经验分析的一致性 当面临巨大数据量的排序的时候,还是优先选择合并排序算法和快速排序算法。而选择排序算法、冒泡排序算法和插入排序算法不太适用于大数据排序。...
数据结构各种排序方法的效率分析与比较 包括随机数列,正序数列,反序数列的比较分析
不同排序算法时间效率的经验分析方法 验证理论分析与经验分析的一致性 void Init_Random();//数组随机数初始化函数声明 void Show_Array();//展示排序结果 void Select_Sort();//选择排序函数声明 void Bubble_...
利用C51,定时器T2,分析快速排序与其它方式排序效率差异
程序包括了几种数据结构中的排序算法效率,图形界面形式介绍
可以统计各种排序算法的时间比较与移动次数,从而知道各种算法的差异
选择排序、冒泡排序、归并排序、快速排序、插入排序的算法原理。不同排序算法时间效率的经验分析方法,验证理论分析与经验分析的一致性。
各种内部排序算法的时间复杂度分析结果只给出了算法执行的时间的阶,或大概执行时间。设计和实现内部排序算法效率比较平台,通过随机的数据比较各算法的关键字比较次数和关键字移动次数,以取得直观的感受。
首先,针对具有一致性的加性语言偏好关系,构建产出导向的DEA模型,分析其相对效率得分与排序向量之间的内在关联.其次,对不满足一致性的加性语言偏好关系,建立改进仁慈型语言偏好关系交叉效率DEA模型,并提出基于...
本文实例讲述了PHP四种排序算法实现及效率分析。分享给大家供大家参考,具体如下: PHP的四种基本排序算法为:冒泡排序、插入排序、选择排序和快速排序。 下面是我整理出来的算法代码: 1. 冒泡排序: 思路:对数组...
排序问题要求我们按照...通过对大量样本的测试结果,统计不同排序算法的时间效率与输入规模的关系,通过经验分析方法,展示不同排序算法的时间复杂度,并与理论分析的基本运算次数做比较,验证理论分析结论的正确性。
一种双向冒泡排序算法的C语言实现及其效率分析.pdf
冒泡排序的分析改进算法,杨义磊,,排序算法对于计算机信息处理很重要 ,一个好的排序不仅可以使信息查找的效率提高 ,而且还直接影响着计算机的工作效率。目前排序领��
针对交叉效率不唯一而导致的决策单元(DMU)无法排序, 以及在集结各DMU 交叉效率时等权重的处理问题, 运用数据包络分析(DEA)方法, 构建基于超效率的交叉效率矩阵, 应用信息熵确定各DMU的客观权重。并以此计算各DMU的...