数组排序.doc

数组排序文章 java 数组排序 2009 年 09月 12日星期六下午 12:55import ; /** * 排序测试类** 排序算法的分类如下: * 1. 插入排序(直接插入排序、折半插入排序、希尔排序); * 2. 交换排序(冒泡泡排序、快速排序); * 3. 选择排序(直接选择排序、堆排序); * 4. 归并排序; * 5. 基数排序。** 关于排序方法的选择: * (1) 若n 较小(如n≤ 50) ,可采用直接插入或直接选择排序。* 当记录规模较小时, 直接插入排序较好; 否则因为直接选择移动的记录数少于直接插人,应选直接选择排序为宜。* (2) 若文件初始状态基本有序( 指正序) ,则应选用直接插人、冒泡或随机的快速排序为宜; * (3) 若n 较大,则应采用时间复杂度为 O(nlgn) 的排序方法:快速排序、堆排序或归并排序。** ***@author WangRuifeng */ public class SortTest { /** * 初始化测试数组的方法* ***@return 一个初始化好的数组*/ public int[] createArray() { Random random = new Random(); int[] array = new int[10]; for (int i= 0;i< 10; i++) { array[i] = (100) - (100);// 生成两个随机数相减, 保证生成的数中有负数} ("========== 原始序列=========="); printArray(array); return array; } /** * 打印数组中的元素到控制台* ***@param source */ public void printArray(int[] source) { for (int i: source) { (i +" "); } (); } /** * 交换数组中指定的两元素的位置* ***@param source * ***@param x* ***@param y */ private void swap(int[] source, int x, int y){ int temp = source[x]; source[x] = source[y]; source[y] = temp; } /** * 冒泡排序---- 交换排序的一种* 方法:相邻两元素进行比较,如有需要则进行交换,每完成一次循环就将最大元素排在最后(如从小到大排序) ,下一次循环是将其他的数进行类似操作。* 性能:比较次数 O(n^2),n^2/2 ;交换次数 O(n^2),n^2/4 ** ***@param source 要排序的数组* ***@param sortType 排序类型* ***@return */ public void bubbleSort(int[] source, String sortType) { if (("asc")) { // 正排序,从小排到大 for (int i= - 1;i> 0; i--) { for (int j= 0;j< i; j++) { if (source[j] > source[j + 1]) { swap(source, j,j+ 1); }}}} else if (("desc")) { // 倒排序,从大排到小 for (int i= - 1;i> 0; i--) { for (int j= 0;j< i; j++) { if (source[j] < source[j + 1]) { swap(source, j,j+ 1); }}}} else { (" 您输入的排序类型错误! "); } printArray(source);// 输出冒泡排序后的数组值} /** * 直接选择排序法---- 选择排序的一种* 方法:每一趟从待排序的数据元素中选出最小(或最大)的一个元素, 顺序放在已排好序的数列的最后,直到全部待排序的数据元素排完。* 性能:比较次数 O(n^2),n^2/2 * 交换次数 O(n),n * 交换次数比冒泡排序少多了,由于交换所需 CPU 时间比比较所需的 CUP 时间多,所以选择排序比冒泡排序快。* 但是 N 比较大时,比较所需的 CPU 时间占主要地位, 所以这时的性能和冒泡排序差不太多,但毫无疑问肯定要