java惯用的几种排序方式
java常用的几种排序方式
Java常用的几种排序方式
package com.vanceinfo.util; import java.lang.Math; import java.util.Random; /** *排序 * * @author javajack */ public class OrderTest { public static void main(String args[]) { OrderTest.ExecOrder(2); } /** * 交换值,交换数组的两个值 * @param array * @param i * @param j */ private static void swap(int[] array,int i, int j) { int tmp = array[i]; array[i] = array[j]; array[j] = tmp; } /** * * @param method * 1为升序,2为降序 */ public static void ExecOrder(int method) { int[] array = null; array = initArray(10, 210, 10); //int[] orderarray = bubbleOrder(array,method); int[] orderarray = doubleBubbleOrder(array,method); //int[] orderarray = insertOrder(array, method); //int [] orderarray = quickOrder(array,method); //int[] orderarray = selectOrder(array, method); for (int i = 0; i < orderarray.length; i++) { System.out.println(orderarray[i]); } } /** * 取随机数据,初始化一个数组 * * @param min * 随机数的最小值 * @param max * 最大值 * @param size * 取得随机数的数量 * @return */ public static int[] initArray(int min, int max, int size) { int[] init = new int[size]; for (int i = 0; i < size; i++) { Random ra = new Random(); init[i] = min + (int) (Math.random() * (max - min + 1)); System.out.println(i + "-------" + init[i]); } return init; } /** * 交换排序方法 * 原理:依次交换值 * @param array * @return */ public static int[] convertOrder(int[] array, int method) { for (int i = 0; i < array.length; i++) { for (int j = i + 1; j < array.length; j++) { if (method==2) { if (array[i] < array[j]) swap(array,i,j); }else if (method == 1) { if (array[i] > array[j]) swap(array,i,j); } } } return array; } /**冒泡排序方法 * 原理:从最后一个开始将小的或大的逐渐冒出 * @param array * @param method * @return */ public static int[] bubbleOrder(int[] array,int method) { for(int i=0;i<array.length;i++) { for (int j=array.length -1 ;j>i;j--) { if (method==2) { if (array[i] < array[j]) swap(array,i,j); }else if (method==1) if (array[i] > array[j]) swap(array,i,j); } } return array; } /** * 双向冒泡排序 * 原理:类似于冒泡排序,只不过是双向的 * @param array * @param method * @return */ public static int[] doubleBubbleOrder(int[] array,int method) { int left = 0; int right = array.length -1 ; while (left < right) { for(int i=left;i<=right;i++) { if (method==1) { if (array[left] > array[i]) swap(array,left,i); }else { if (array[left] < array[i]) swap(array,left,i); } } for (int i=left+1;i<=right;i++) { if (method==1) { if (array[right] < array[i]) swap(array,right,i); }else { if (array[right] > array[i]) swap(array,right,i); } } left++; right--; } return array; } /** * 快速排序方法,运用到递归 * 排序原理:随机找到一个值,然后以此值大小进行分为两个数组,大的放左边,小的放右边, * 然后再对左右两侧的数据依次排序根据 * @param array * @param method * @return */ public static int[] quickOrder(int[] array, int method) { quickDeal(array,0,array.length - 1,method); return array; } /** * * @param array * @param begin * 开始位置 * @param end * 结束位置 */ private static void quickDeal(int[] array, int begin, int end,int method) { if (end > begin) { int pos = begin + (int) (Math.random() * (end - begin + 1)); // 计算分隔位置 int posvalue = array[pos]; // 取得分隔位置的值 swap(array,pos,end); //将posvalue放到最end的位置 pos=begin; //初始化pos for (int i=begin; i < end; i++) { if (method==1) { if (array[i] < posvalue) { //当小于posvalue时,将此值移动到pos位置,也就是向前移动 swap(array,pos,i); pos++; //移动后pos增1 } }else if(method == 2) { if (array[i] > posvalue) { //当小于posvalue时,将此值移动到pos位置,也就是向前移动 swap(array,pos,i); pos++; //移动后pos增1 } } } swap(array,pos,end); //end位置的值前移 quickDeal(array,begin,pos -1,method); quickDeal(array,pos+1,end,method); } } /** * 插入排序方法 * 排序原理:抽出一个数,做为排序基序列,然后依次抽出其它数与,与此序列中的数进行比较,放入合适的位置 * @param array * @param method * @return */ public static int[] insertOrder(int[] array, int method) { for (int i = 1; i < array.length; i++) { if (method == 1) { if (array[i - 1] > array[i]) { int tmp = array[i]; // int j = i - 1; do { array[j + 1] = array[j]; j--; } while (j >= 0 && tmp < array[j]); //当j>=0并且 当前值大于数据中j位置的值时移动 array[j + 1] = tmp; //插入排序值 } } else if (method == 2) { if (array[i - 1] < array[i]) { int tmp = array[i]; int j = i - 1; do { array[j + 1] = array[j]; j--; } while (j >= 0 && tmp > array[j]); array[j + 1] = tmp; } } } return array; } /** * 选择排序方法 * 排序原理:每次选择一个最大的或最小的数放到已排序序列中 * @param array * @param method * @return */ public static int[] selectOrder(int[] array,int method) { for (int i=0;i<array.length - 1;i++) { int tmp = array[i]; int pos = i+1; //记录大值或小值的位置 for (int j=i+1;j<array.length;j++) { if (method==1) { if (array[j]<tmp) { tmp = array[j]; pos= j ;//记录大值或小值的位置 } }else if (method==2) { if (array[j]>tmp) { tmp = array[j]; pos= j ;//记录大值或小值的位置 } } } if (tmp != array[i]) swap(array,i,pos); //不相同时交换 } return array; } }