面试笔试必用-必须掌握的Java排序算法

xiaxia_00 贡献于2011-12-27

作者 yangfan  创建于2011-01-21 09:30:00   修改者User  修改于2011-03-08 17:16:00字数9582

文档摘要:Java排序算法1)分类:1)插入排序(直接插入排序、希尔排序)2)交换排序(冒泡排序、快速排序)3)选择排序(直接选择排序、堆排序)4)归并排序5)分配排序(箱排序、基数排序)所需辅助空间最多:归并排序所需辅助空间最少:堆排序平均速度最快:快速排序不稳定:快速排序,希尔排序,堆排序。1)选择排序算法的时候1.数据的规模;
关键词:

 Java排序算法 1)分类: 1)插入排序(直接插入排序、希尔排序) 2)交换排序(冒泡排序、快速排序) 3)选择排序(直接选择排序、堆排序) 4)归并排序 5)分配排序(箱排序、基数排序) 所需辅助空间最多:归并排序 所需辅助空间最少:堆排序 平均速度最快:快速排序 不稳定:快速排序,希尔排序,堆排序。 1)选择排序算法的时候 1.数据的规模 ; 2.数据的类型 ; 3.数据已有的顺序 一般来说,当数据规模较小时,应选择直接插入排序或冒泡排序。任何排序算法在数据量小时基本体现不出来差距。考虑数据的类型,比如如果全部是正整数,那么考虑使用桶排序为最优。 考虑数据已有顺序,快排是一种不稳定的排序(当然可以改进),对于大部分排好的数据,快排会浪费大量不必要的步骤。数据量极小,而起已经基本排好序,冒泡是最佳选择。我们说快排好,是指大量随机数据下,快排效果最理想。而不是所有情况。 3)总结: ――按平均的时间性能来分: 1)时间复杂度为O(nlogn)的方法有:快速排序、堆排序和归并排序,其中以快速排序为最好; 2)时间复杂度为O(n2)的有:直接插入排序、起泡排序和简单选择排序,其中以直接插入为最好,特 别是对那些对关键字近似有序的记录序列尤为如此; 3)时间复杂度为O(n)的排序方法只有,基数排序。 当待排记录序列按关键字顺序有序时,直接插入排序和起泡排序能达到O(n)的时间复杂度;而对于快速排序而言,这是最不好的情况,此时的时间性能蜕化为O(n2),因此是应该尽量避免的情况。简单选择排序、堆排序和归并排序的时间性能不随记录序列中关键字的分布而改变。 ――按平均的空间性能来分(指的是排序过程中所需的辅助空间大小): 1) 所有的简单排序方法(包括:直接插入、起泡和简单选择)和堆排序的空间复杂度为O(1); 2) 快速排序为O(logn ),为栈所需的辅助空间; 3) 归并排序所需辅助空间最多,其空间复杂度为O(n ); 4)链式基数排序需附设队列首尾指针,则空间复杂度为O(rd )。 ――排序方法的稳定性能: 1) 稳定的排序方法指的是,对于两个关键字相等的记录,它们在序列中的相对位置,在排序之前和 经过排序之后,没有改变。 2) 当对多关键字的记录序列进行LSD方法排序时,必须采用稳定的排序方法。 3) 对于不稳定的排序方法,只要能举出一个实例说明即可。 4) 快速排序,希尔排序和堆排序是不稳定的排序方法。 4)插入排序: 包括直接插入排序,希尔插入排序。 直接插入排序: 将一个记录插入到已经排序好的有序表中。 1, sorted数组的第0个位置没有放数据。 2,从sorted第二个数据开始处理: 如果该数据比它前面的数据要小,说明该数据要往前面移动。 首先将该数据备份放到 sorted的第0位置当哨兵。 然后将该数据前面那个数据后移。 然后往前搜索,找插入位置。 找到插入位置之后讲 第0位置的那个数据插入对应位置。 O(n*n), 当待排记录序列为正序时,时间复杂度提高至O(n)。 希尔排序(缩小增量排序 diminishing increment sort):先将整个待排记录序列分割成若干个子序列分别进行直接插入排序,待整个序列中的记录基本有序时,再对全体记录进行一次直接插入排序。 插入排序Java代码: public class InsertionSort { // 插入排序:直接插入排序,希尔排序 public void straightInsertionSort(double [] sorted){ int sortedLen= sorted.length; for(int j=2;j=0;k--){ if(sorted[k]>sorted[0]){ sorted[k+1]=sorted[k]; }else{ insertPos=k+1; break; } } sorted[insertPos]=sorted[0]; } } } public void shellInertionSort(double [] sorted, int inc){ int sortedLen= sorted.length; for(int j=inc+1;j=0;k-=inc){ if(sorted[k]>sorted[0]){ sorted[k+inc]=sorted[k]; //数据结构课本上这个地方没有给出判读,出错: if(k-inc<=0){ insertPos = k; } }else{ insertPos=k+inc; break; } } sorted[insertPos]=sorted[0]; } } } public void shellInsertionSort(double [] sorted){ int[] incs={7,5,3,1}; int num= incs.length; int inc=0; for(int j=0;j0;j--){ int end= j; for(int k=1;k10e-6){ sorted[k+1]=tempB; } } } } public void QuickExchangeSortBackTrack(double [] sorted, int low,int high){ if(low= sorted[0])--high; sorted[low]= sorted[high]; while(low=0 && j>=0){ double temp= sorted[i]; sorted[i]=sorted[j]; sorted[j]=temp; } } public int getMinIndex(double [] sorted, int i){ int sortedLen= sorted.length; int minJ=1; double min= Double.MAX_VALUE; for(int j=i;j10e-6){ ++j; } if(temp<=sorted[j]){ break; } sorted[start]=sorted[j]; start=j; } sorted[start]=temp; } } public void heapSelectionSort(double [] sorted){ int sortedLen = sorted.length; for(int i=sortedLen/2;i>0;i--){ heapAdjust(sorted,i,sortedLen); } for(int i=sortedLen;i>1;--i){ exchange(sorted,1,i); heapAdjust(sorted,1,i-1); } } public static void main(String [] args){ Random random= new Random(6); int arraysize=9; double [] sorted=new double[arraysize]; System.out.print("Before Sort:"); for(int j=1;j> util; public void distribute(double [] sorted, int nth){ if(nth<=keyNum && nth>0){ util=new Vector>(); for(int j=0;j<10;j++){ Vector temp= new Vector (); util.add(temp); } for(int j=0;j=nth){ return Character.getNumericValue(nn.charAt(len-nth)); }else{ return 0; } } public void collect(double [] sorted){ int k=0; for(int j=0;j<10;j++){ int len= util.get(j).size(); if(len>0){ for(int i=0;imax){ max= sorted[j]; } } return Integer.toString((int)max).length(); } public void radixSort(double [] sorted){ if(keyNum==-1){ keyNum= getKeyNum(sorted); } for(int i=1;i<=keyNum;i++){ distribute(sorted,i); collect(sorted); } } public static void main(String[] args) { Random random = new Random(6); int arraysize = 21; double[] sorted = new double[arraysize]; System.out.print("Before Sort:"); for (int j = 0; j < arraysize; j++) { sorted[j] = (int) (random.nextDouble() * 100); System.out.print((int) sorted[j] + " "); } System.out.println(); RadixSort sorter = new RadixSort(); sorter.radixSort(sorted); System.out.print("After Sort:"); for (int j = 0; j < sorted.length; j++) { System.out.print((int) sorted[j] + " "); } System.out.println(); } } =====》总结:上述Java代码中,基本上用的都是double数组,如果想要应用其他的数组,只需要将double数组改成 Comparable接口数组,凡是实现了Comparable接口的都可以用。而在C++中,是用模板类来解决这个问题。

下载文档到电脑,查找使用更方便

文档的实际排版效果,会与网站的显示效果略有不同!!

需要 5 金币 [ 分享文档获得金币 ] 8 人已下载

下载文档