Board logo

标题: JAVA实现部分排序方法 [打印本页]

作者: qingqing3721    时间: 2011-6-27 23:40     标题: JAVA实现部分排序方法

public class SortTest { public static void main(String[] args)  { int[] a={3,5,2,1,9,10,8,7,6,1,2,4}; //bubbleSort(a); //selectSort(a); insertSort(a); for(int k=0;ka.length;k++) { System.out.print(a[k]+" "); }  } /** * 交流办法 * @param a * @param i * @param j */ public static void swap(int[] a,int i,int j) { int temp=a; a=a[j]; a[j]=temp; } /** * 冒泡排序 * @param a */ public static void bubbleSort(int[] a) { for(int i=0;ia.length;i++) { for(int j=i;ja.length;j++) { if(aa[j]) { swap(a,i,j); } } } } /**  * 直接选择排序法----选择排序的一种 办法:每一趟从待排序的数据元素中选出最小(或最大)的一个元素,  * 顺序放在已排好序的数列的最后,直到全部待排序的数据元素排完。 功能:比较次数O(n^2),n^2/2 交流次数O(n),n  * 交流次数比冒泡排序少多了,由于交流所需CPU时间比比较所需的CUP时间多,所以选择排序比冒泡排序快。  * 但是N比较大时,比较所需的CPU时间占次要地位,所以这时的功能和冒泡排序差不太多,但毫无疑问一定要快些。  *  * @param data  * 要排序的数组  * @param sortType  * 排序类型  * @return  */ public static void selectSort(int[] data) { int index; for (int i = 0; i  data.length; i++) { index = i; for (int j = i+1; j data.length ; j++) { if (data[index]  data[j]) { index = j; } } // 交流在地位i和index(最大值)两个数 swap(data, i, index); } } /**  * 拔出排序 办法:将一个记载拔出到已排好序的有序表(有能够是空表)中,从而得到一个新的记载数增1的有序表。 功能:比较次数O(n^2),n^2/4  * 复制次数O(n),n^2/4 比较次数是前两者的一般,而复制所需的CPU时间较交流少,所以功能上比冒泡排序提高一倍多,而比选择排序也要快。  *  * @param data  * 要排序的数组  * @param sortType  * 排序类型  */ public static void insertSort(int[] data) { // 比较的轮数 for (int i = 1; i  data.length; i++) { // 保证前i+1个数排好序 for (int j = 0; j  i; j++) { if (data[j]  data) { // 交流在地位j和i两个数 swap(data, i, j); } } } } /** * 反转数组的办法 * * @param data * 源数组 */ public void reverse(int[] data) { int length = data.length; int temp = 0;// 暂时变量 for (int i = 0; i  length / 2; i++) { temp = data; data = data[length - 1 - i]; data[length - 1 - i] = temp; } } /** * 疾速排序 疾速排序使用分治法(Divide and conquer)策略来把一个序列(list)分为两个子序列(sub-lists)。 步骤为: * 1. 从数列中挑出一个元素,称为 "基准"(pivot), 2. * 重新排序数列,一切元素比基准值小的摆放在基准前面,一切元素比基准值大的摆在基准的前面 * (相反的数可以到任一边)。在这个联系之后,该基准是它的最后地位。这个称为联系(partition)操作。 3. * 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。 * 递回的最底部情形,是数列的大小是零或一,也就是永远都已经被排序好了 * 。虽然不时递回下去,但是这个算法总会完毕,由于在每次的迭代(iteration)中,它至少会把一个元素摆到它最后的地位去。 * */ public static void quitSort(int[] a, int low, int hight)// 疾速排序法 { int i, j, k = 0; if (low  hight)// 先保管 { i = low; j = hight; k = a; while (i  j) { while (i  j  a[j]  k) { j--; } if (i  j) {// 从后往前排序 a = a[j]; i++; } while (i  j  a  k) { i++; } if (i  j) {// 从前往后排序 a[j] = a; j--; } } a = k; quitSort(a, low, i - 1); quitSort(a, i + 1, hight); } }文章由歌瑞尔内衣整理,收集辛苦,希望能保留出处,谢谢斑竹大哥。




欢迎光临 编程开发论坛 (http://bbs.lihuasoft.net/) Powered by Discuz! 6.0.0