标题:
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(a
a[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
