作者的话
作为学习者，以自己的水平发表一些认为比较好的文章供更多人学习。学习是积累的过程，不断学习，不断创新，直至达到巅峰 ！
如下是个人搜集并编写的常用排序算法经典，有：直接插入排序算法，归并排序算法，直接选择排序算法和冒泡排序算法。因水平有限，难免有所纰漏，请批评指正 ！
1.如下是工具类代码及测试方法(修正后)
package com.rick.bao.tools; import java.util.Date; import org.junit.Test; /** * * @title Java排序工具包 * @author Rick·bao * @date 2015年7月27日 * @description * Java中八大算法： * 1.插入排序：分为直接插入和Shell(希尔)排序<br/> * 2.选择排序：直接选择与堆排序<br/> * 3.交换排序：冒泡与快速排序<br/> * 4.其它排序：归并和基数排序<br/> * <br/> * 查阅大量资料，对排序算法的使用使用场景做如下总结：<br/> * 1.大记录(n>=100条)<br/> * 要求稳定(遇到相同关键字不改变次序)性好或关键字基本有序，使用归并排序算法<br/> * 不做稳定性要求且随机关键字，使用快速排序<br/> * 2.小记录(n<=100)<br/> * 记录有序(或无序)且要求稳定性好,使用直接插入排序算法<br/> * 对稳定性不做要求且无序，用直接选择排序算法<br/> */ public class Sorted { /** * @category 归并排序算法 * @param disorder 未排序数组 * @param order 已排序数组 * @param disorder_length 未排序数组长度 * @return 排序数组 */ public static int[] mergeSort(int disorder[],int order[],int disorder_length){ int h=1; while(h<disorder_length){ mergeOrder(disorder,order,disorder_length-1,h); h=2*h; mergeOrder(order,disorder,disorder_length-1,h); h=2*h; } return order; } /** * @category 归并排序算法 * @param disorder 未排序 * @param order 已排序 * @param left 左边索引 * @param right 右边索引 * @param end 末尾索引 */ private static void merge(int disorder[], int order[], int left, int right, int end) { int i = left, j = right + 1, k = left; while (i <= right && j <= end) { if (disorder[i] <= disorder[j]) { order[k++] = disorder[i++]; // 取r[i]和r[j]中较小者放入r1[k] } else { order[k++] = disorder[j++]; } } if (i <= right) { while (i <= right) { // 若第一个子序列处理完，则进行收尾处理 order[k++] = disorder[i++]; } } else { while (j <= end) { // 若第二个子序列处理完，则进行收尾处理 order[k++] = disorder[j++]; } } } /** * @category 归并排序算法 * @param disorder 未排序 * @param order 已排序 * @param disorder_length 未排序数组长度 * @param h */ private static void mergeOrder(int disorder[],int order[],int disorder_length,int h){ int i=0; while(i<=disorder_length-2*h){ //待归并记录至少有两个长度为h的子序列 merge(disorder,order,i,i+h-1,i+2*h-1); i+=2*h; } if(i<disorder_length-h){ merge(disorder,order,i,i+h-1,disorder_length); //待归并序列中有一个长度小于h } else{ for(int k=i;k<=disorder_length;k++){ //待归并序列中只剩一个子序列 order[k]=disorder[k]; } } } /** * @category 快速排序算法 * @param disorder 原数组 * @param first * @param end */ public static int[] quickSort(int[] disorder,int first,int end){ //利用递归反复划分 if(first<end){ int pivot=partition(disorder, first, end); //调用划分函数 quickSort(disorder,first,pivot-1); quickSort(disorder,pivot+1,end); } return disorder; } /** * @category 快速排序算法 * @param disorder 原数组 * @param first * @param end * @return */ private static int partition(int[] disorder,int first,int end){ int i,j; i=first;j=end; //初始化 while(i<j){ while(i<j&&disorder[i]<=disorder[j]) j--; //右侧扫描 if(i<j){ //将较小的记录交换到前面 int temp; temp=disorder[i]; disorder[i]=disorder[j]; disorder[j]=temp; } while(i<j&&disorder[i]<disorder[j]){ i++; //左侧扫描 } if(i<j){ //将较大的记录换到后面 int temp; temp=disorder[i]; disorder[i]=disorder[j]; disorder[j]=temp; } } return i;//返回分割索引 } /** * @category 直接插入排序算法 * @param disorder 数组 */ public static int[] insertSort(int[] disorder){ int temp=0;//临时变量 for(int i=1;i<disorder.length;i++){ int j=i-1; temp=disorder[i]; for(;j>=0&&temp<disorder[j];j--){ disorder[j+1]=disorder[j];//替换位置 } disorder[j+1]=temp; } return disorder; } /** * @category 直接选择排序算法 * @param disorder 数组 */ public static int[] selectSort(int[] disorder) { int i,j,index,temp; for(i=0;i<disorder.length;i++){ index=i; //初始化第i趟选择排序的最小记录的指针 for(j=i+1;j<disorder.length;j++){ //在无序区选取最小记录 if(disorder[j]<disorder[index]){ index=j; } } if(index!=i){ //将最小记录与r[i]交换 temp=disorder[i]; disorder[i]=disorder[index]; disorder[index]=temp; } } return disorder; } /** * @category 冒泡排序算法(逻辑简单，适用性不强) * @param disorder 数组 */ public static int[] bubbleSort(int[] disorder) { int temp = 0; for (int i = 0; i < disorder.length; i++) { for (int j = 0; j < disorder.length - i - 1; j++) if (disorder[j] > disorder[j + 1]) { // 进行两两比较，下面进行符合条件的交换 temp = disorder[j + 1]; disorder[j + 1] = disorder[j]; disorder[j] = temp; } } return disorder; } /** * @title 测试 * @category 入口方法 */ @Test public void test(){ int arr[] = BuilderArray.getArray(1300, 5000);//初始化数组元素 //-------------直接插入排序算法 System.out.print("---------直接插入排序算法------------ "); showArray(arr,Sorted.insertSort(arr),"直接插入排序"); // --------------归并排序算法 System.out.print("---------归并排序算法------------ "); int order[] = new int[arr.length];//归并后的新数组 showArray(arr,Sorted.mergeSort(arr, order, arr.length),"归并排序"); // --------------直接选择排序算法 System.out.print("---------直接选择排序算法------------ "); showArray(arr,Sorted.selectSort(arr),"直接选择排序"); //--------------冒泡排序算法 System.out.print("---------冒泡排序算法 ------------ "); showArray(arr,Sorted.bubbleSort(arr),"冒泡排序"); // --------------快速排序算法 System.out.print("---------快速排序算法 ------------ "); showArray(arr,Sorted.quickSort(arr, 0, arr.length-1),"快速排序"); } /** * * @title 测试 * @category 显示方法 * @param disorder * @param sorted * @param sorted_type 排序类型 */ private void showArray(int[] disorder,int[] sorted,String sorted_type) { Date begin = null; Date end = null; System.out.println("排序元素为 ："); int index = 1; for (int k : disorder){ System.out.print(k + " ,"); if(index%10==0) System.out.println(); index++; } begin = new Date(); System.out.print(" ----- 排序后： "); index = 1; for (int m : sorted){ System.out.print(m + " ,"); if(index%15==0) System.out.println(); index++; } end = new Date(); System.out.println(" "+sorted_type+",元素大小为："+disorder.length +" --耗 时(s) ：" + (end.getTime() - begin.getTime())); System.out.println(); } }
2.另外编写了一个数组生产类
package com.rick.bao.tools; import java.util.Random; /** * * @title 生产数组的工具类 * @author Rick·bao * @date 2015年7月31日 * */ public class BuilderArray { /** * 获得随机大小数组方法 * @param max_index 最大索引 * @param max_value 最大值 * @return disorder 返回数组 */ public static int[] getArray(int max_index,int max_value){ Random random = new Random(); int index = random.nextInt(max_index); int[] disorder = new int[index];//初始化一个随机大小的数组对象 for(int i=0;i<index;i++){ disorder[i]=random.nextInt(max_value); } return disorder; } }
3.如下是个人机器运行结果-摘抄几组数据
A组：
直接插入排序,元素大小为：53 --耗 时(s) ：2
归并排序,元素大小为：53 --耗 时(s) ：2
直接选择排序,元素大小为：53 --耗 时(s) ：2
冒泡排序,元素大小为：53 --耗 时(s) ：2
快速排序,元素大小为：53 --耗 时(s) ：2
B组：
直接插入排序,元素大小为：492 --耗 时(s) ：11
归并排序,元素大小为：492 --耗 时(s) ：11
直接选择排序,元素大小为：492 --耗 时(s) ：10
冒泡排序,元素大小为：492 --耗 时(s) ：11
快速排序,元素大小为：492 --耗 时(s) ：13
C组：
直接插入排序,元素大小为：1300 --耗 时(s) ：40
归并排序,元素大小为：1300 --耗 时(s) ：27
直接选择排序,元素大小为：1300 --耗 时(s) ：20
冒泡排序,元素大小为：1300 --耗 时(s) ：21
快速排序,元素大小为：1300 --耗 时(s) ：9
后记：受到数据复杂度影响，快速可能要失去优势；直接选择处于综合优势，归并是大小场合都适用。 Rick-bao 制作，仅供参考 ！