Rumah >Java >javaTutorial >八大排序算法实践
对于排序算法,这些年用到的也不多,基本处于拿来用的状态,一直没有花时间稍微深入了解。最近下定决心自己动手写写,加深理解。查看了不少资料,有不少分析的很到位,帮助快速理解,在此感谢!
1、概念理解及实现
package com.demo.algorithm.sort; /** * 排序算法合集 * @author sheungxin * */ public class NumberSort { /** * 插入排序-直接插入排序 * 工作原理:构建有序序列,对于未排序的数据,在已排序序列中从后向前扫描,找到相应位置并插入 * 参考:http://blog.csdn.net/morewindows/article/details/6665714 * @param array * @param asc 0:升序 1:降序 */ public static void straightInsertSort(int[] array,int asc){ int tmp,n; //从第二位元素开始,第一位认为已被排序 for(int m=1;m<array.length;m++){ tmp=array[m]; //在已排序序列中从后向前扫描,若该元素>(<)新元素,将该新元素向后移一位 for(n=m-1;n>=0&&(asc==1&&tmp>array[n]||asc==0&&tmp<array[n]);n--){ array[n+1]=array[n]; } //上述循环在该元素<=(>=)新元素或者扫描到首位时结束,将该元素插入在结束位置后面 array[n+1]=tmp; } display(array); } /** * 插入排序-希尔排序,实质就是分组排序,又称缩小增量排序 * 工作原理:先将整个待排序元素序列分割成若干个子序列(由相隔某个“增量”元素组成)分别进行直接插入排序, * 然后依次缩减增量再进行排序,待整个序列中元素基本有序(增量足够小)时,再进行一次全元素直接插入排序。 * 优势:直接插入排序在元素基本有序的情况下,效率最高 * 参考:http://blog.csdn.net/morewindows/article/details/6668714 * @param array * @param asc 0:升序 1:降序 */ public static void shellSort(int[] array,int asc){ int len=array.length; //依次缩减增量,直到增量为1 for(int gap=len/2;gap>0;gap/=2){ //根据步长把待排序元素分为gap组 for(int i=0;i<gap;i++){ //分别对每组元素进行直接插入排序,从i开始以增加gap得到一组元素 for(int j=i+gap;j<len;j+=gap){ int tmp=array[j]; int k=j-gap;//上一个节点 //在已排序序列中从后向前扫描,若该元素>(<)新元素,将该新元素向后移一位 while(k>=0&&(asc==1&&tmp>array[k]||asc==0&&tmp<array[k])){ array[k+gap]=array[k]; k-=gap;//向前扫描,移到下标 } //上述循环在该元素<=(>=)新元素或者扫描到首位时结束,将该元素插入在结束位置后面 array[k+gap]=tmp; } } } display(array); } /** * 选择排序:简单选择排序 * 原理:从无序区中选择一个最小的元素之间放到有序区的最后 * 参考:http://blog.csdn.net/morewindows/article/details/6671824 * @param array * @param asc 0:升序 1:降序 */ public static void selectSort(int[] array,int asc){ int tmp,ix; for(int i=0;i<array.length;i++){ ix=i;//最小或最大元素的位置 //从无序区中选择一个最小或最大的元素的位置 for(int j=i+1;j<array.length;j++){ if((asc==0&&array[ix]>array[j])||(asc==1&&array[ix]<array[j])){ ix=j; } } //交换位置 if(ix!=i){ tmp=array[i]; array[i]=array[ix]; array[ix]=tmp; } } display(array); } /** * 选择排序:堆排序 * 原理:二叉堆近似二叉树,父节点总是大于或等于(小于或等于)任何一个子节点 * 参考:http://blog.csdn.net/morewindows/article/details/6709644 * http://blog.csdn.net/kimylrong/article/details/17150475 * @param array * @param asc 0:升序 1:降序 */ public static void heapSort(int[] array,int asc){ //构建二叉堆,从最后一个父节点开始 for(int i=array.length/2-1;i>=0;i--){ buildHeap(array, array.length, i, asc); } //使用堆根节点构建有序序列 for(int i=array.length-1;i>=1;i--){ //依次把根节点向后交换构建有序序列 swapArray(array, 0, i); //根节点交换位置后,从0,i-1重新构建堆 buildHeap(array, i, 0, asc); } display(array); } /** * 构建二叉堆 * @param array 二叉堆数组 * @param heapSize 二叉堆大小 * @param index 当前父节点位置 * @param asc 0:升序 1:降序 */ private static void buildHeap(int[] array,int heapSize,int index,int asc){ //比较父节点、左右叶子节点,找出最大或最小节点位置 int left = index * 2 + 1; int right = index * 2 + 2; int ix=index; if(left<heapSize&&(asc==1&&array[index]>array[left]||asc==0&&array[index]<array[left])){ ix=left; } if(right<heapSize&&(asc==1&&array[ix]>array[right]||asc==0&&array[ix]<array[right])){ ix=right; } if(ix!=index){ swapArray(array, index, ix);//交换父节点和叶子节点位置,满足最大/小堆性质 //递归向下交换,非最下层父节点与叶子节点交换会破坏下层最大/小堆性质 buildHeap(array, heapSize, ix, asc); } } /** * 交换排序:冒泡排序 * 参考: http://blog.csdn.net/morewindows/article/details/6657829 * @param array * @param asc 0:升序 1:降序 */ public static void bubbleSort(int[] array,int asc){ for(int i=0;i<array.length;i++){ for(int j=1;j<array.length-i;j++){ if((asc==0&&array[j-1]>array[j])||(asc==1&&array[j-1]<array[j])){ swapArray(array, j-1, j); } } } /**有点像交换排序、直接插入排序,交换次数过多 //从第二个元素开始依次与其左边元素进行比较 for(int m=1;m<array.length;m++){ //从左边最远的元素开始比较 for(int n=0;n<m;n++){ //满足条件交换位置 if((asc==0&&array[m]>array[n]) ||(asc==1&&array[m]<array[n])){ swapArray(array, m, n); } } }**/ display(array); } /** * 交换排序:快速排序,在同为O(N*logN)的几种排序算法中效率较高,经常被使用 * 原理:从元素序列中取一个数作为基准数,左右分别放大于或小于的元素,再对左右区间重复上述操作,直到各区间只有一个数 * 参考: http://blog.csdn.net/morewindows/article/details/6684558 * @param array * @param asc 0:升序 1:降序 */ public static void quickSort(int[] array,int l,int r,int asc){ if(l<r){ int tmp=array[l];//把第一个节点作为基准数,视为第一个空位 int i=l; int j=r; //以基准数为标准,左右分别放大于或小于的节点 while(i<j){ //寻找右边小于(大于)基准数的节点位置 while(i<j&&(asc==0&&array[j]>=tmp||asc==1&&array[j]<=tmp)){ j--; } //把右边找到的节点放到左边的空位 array[i]=array[j]; //寻找右边大于(小于)基准数的节点位置 while(i<j&&(asc==0&&array[i]<=tmp||asc==1&&array[i]>=tmp)){ i++; } //把左边找到的节点放到右边的空位 array[j]=array[i]; } //把基准数放在中间节点 array[i]=tmp; //对中间点左边的元素重复上述操作 quickSort(array, l, i-1, asc); //对中间点右边的元素重复上述操作 quickSort(array, i+1, r, asc); } display(array); } /** * 归并排序:将两个(或两个以上)有序表合并成一个新的有序表 * 原理:将序列不断拆分,再反向两两合并形成有序序列 * 时间复杂度:O(nlogn) * 参考:http://www.cnblogs.com/jingmoxukong/p/4308823.html * @param array * @param l 左指针 * @param r 右指针 * @param asc 0:升序 1:降序 */ public static void mergeSort(int[] array,int l,int r,int asc){ //找出中间点,左右拆分为两个序列 int m=(l+r)/2; if(l<r){ //左边序列,递归拆分直到间隔为0 mergeSort(array, l, m, asc); //右边,递归拆分直到间隔为0 mergeSort(array, m+1, r, asc); //左右归并 merge(array, l, m, r, asc); } display(array); } /** * 左右归并为有序集合 * @param array * @param l 左指针 * @param m 中间指针 * @param r 右指针 */ private static void merge(int[] array,int l,int m,int r,int asc){ int[] tmp=new int[r-l+1]; int i=l;//左指针 int j=m+1;//右指针 int k=0; //把较小的数先移到临时数组中 while(i<=m&&j<=r){ if(asc==0&&array[i]<array[j]||asc==1&&array[i]>array[j]){ tmp[k++]=array[i++]; }else{ tmp[k++]=array[j++]; } } //把左边剩余的数移到数组中 while(i<=m){ tmp[k++]=array[i++]; } //把右边剩余的数移到数组中 while(j<=r){ tmp[k++]=array[j++]; } //把临时数组中的数覆盖原数组,形成有序集合 for(k=0;k<tmp.length;k++){ array[l+k]=tmp[k]; } } /** * 基数/桶排序:将序列分到有限数量的桶子里,再分别排序 * 原理:将序列分到有限数量的桶子里,再分别排序 * 时间复杂度:O(nlog(r)m),r为所采用的基数,m为堆数 * 参考:http://www.cnblogs.com/jingmoxukong/p/4308823.html * @param array * @param l 左指针 * @param r 右指针 * @param asc 0:升序 1:降序 */ public static void radixSort(int[] array,int digit,int asc){ final int radix=10;//基数,阿拉伯数字0~9,视为10个桶 int i=0; int j=0; int[] count=new int[radix];//存放各个桶存放数据的个数 int[] tmp=new int[array.length]; //按照从低到高位进行排序 for(int d=1;d<=digit;d++){ //置空各个桶的统计数据 for(i=0;i<radix;i++){ count[i]=0; } //根据位数d,统计各个桶存放数据的个数 for(i=0;i<array.length;i++){ j=array[i]/((Double)Math.pow(10, d-1)).intValue()%10;//d位上的数据 count[j]++; } //把count[i]的值由存放的个数改变了有边界的索引 for(i=1;i<radix;i++){ count[i]+=count[i-1]; } //将数据依次装入临时桶里,从右向左扫描 for(i=array.length-1;i>=0;i--){ j=array[i]/((Double)Math.pow(10, d-1)).intValue()%10;//d位上的数据 tmp[count[j]-1]=array[i];//count[j]-1为第J个桶右边界的下标 count[j]--;//桶j装入数据索引减1 } //按照桶中数据顺序放入原数据序列中 for(i=0;i<array.length;i++){ if(d==digit){ if(asc==0){ array[i]=tmp[i]; }else{ array[i]=tmp[array.length-i-1]; } }else{ array[i]=tmp[i]; } } } display(array); } /** * 数组中指定位置的值交换位置 * @param array * @param i * @param j */ private static void swapArray(int[] array,int i,int j){ array[i]=array[j]^array[i]; array[j]=array[i]^array[j]; array[i]=array[i]^array[j]; } /** * 输出数组 * @param array */ private static void display(int[] array){ StringBuilder builder=new StringBuilder("["); for(int i=0;i<array.length;i++){ builder.append(array[i]); if(i<array.length-1){ builder.append(","); }else{ builder.append("]"); } } System.out.println(builder.toString()); } public static void main(String[] args) { int[] array=new int[]{11,56,35,62,97,21,36,33,86,81,35}; //straightInsertSort(array, 0); //shellSort(array, 0); //selectSort(array, 0); //heapSort(array, 0); //bubbleSort(array,0); //quickSort(array, 0, array.length-1, 0); //mergeSort(array, 0, array.length-1,1); radixSort(array, 3, 0); } }
2、排序算法对比图
引用
http://blog.csdn.net/hguisu/article/details/7776068
3、选择排序算法准则
影响排序的因素有很多,平均时间复杂度低的算法并不一定就是最优的。相反,有时平均时间复杂度高的算法可能更适合某些特殊情况。同时,选择算法时还得考虑它的可读性,以利于软件的维护。一般而言,需要考虑的因素有以下四点:
1)、待排序的记录数目n的大小;
2)、记录本身数据量的大小,也就是记录中除关键字外的其他信息量的大小;
3)、关键字的结构及其分布情况;
4)、对排序稳定性的要求。
设待排序元素的个数为n.
1)、当n较大,则应采用时间复杂度为O(nlog2n)的排序方法:快速排序、堆排序或归并排序序。
a、快速排序:是目前基于比较的内部排序中被认为是最好的方法,当待排序的关键字是随机分布时,快速排序的平均时间最短;
b、堆排序 :如果内存空间允许且要求稳定性的;
c、归并排序:它有一定数量的数据移动,所以我们可能过与插入排序组合,先获得一定长度的序列,然后再合并,在效率上将有所提高。
2)、当n较大,内存空间允许,且要求稳定性 =》归并排序
3)、当n较小,可采用直接插入或直接选择排序。
a、直接插入排序:当元素分布有序,直接插入排序将大大减少比较次数和移动记录的次数;
b、直接选择排序 :元素分布有序,如果不要求稳定性,选择直接选择排序
4)、一般不使用或不直接使用传统的冒泡排序。
5)、基数排序:它是一种稳定的排序算法,但有一定的局限性:
a、关键字可分解;
b、记录的关键字位数较少,如果密集更好;
c、如果是数字时,最好是无符号的,否则将增加相应的映射复杂度,可先将其正负分开排序。
引用
http://blog.csdn.net/hguisu/article/details/7776068