}
//插入排序 /*思想： * 假设左边部分已经排序好了，从某个位置开始无序（比如4），将4赋予一个临时变量，然后再和前面的数据比较， * 大多数情况下，插入算法任然需要O（N^2）的时间，比冒泡快一倍，比选择排序也要快一点。经常被用到复杂排序的最后阶段，如快排 * * */ public class Insert_sort { public static void main(String[] args) { int [] a={3,5,2,6,4,34,8,7,5,4,23}; int[] s=insertSort(a); for(int i=0;i<s.length;i++){ System.out.print(s[i]+"--"); } } public static int[] insertSort(int[] a){ int in,out; /* * 外层的for循环中，out变量从1开始，向右移动，他标记了未排序部分的最左端的数据 * 而在内层while循环中，in变量从out变量开始，向左移动，直到t变量小于in所指的数组数据项，或是他已经不能再往左移动为止。 * while循环的每一次都想右移动了一个排序的数据项 * 在每次结束时，在将t位置的项插入后，比out变量下标号小的数据项都是局部有序的 比较次数，1+2+3+...+(N-1) = Nx(N-1)/2，而因为每一次排序发现插入点之前，平均只有全体数据项的一半真的进行了比较，所以是N*(N-1)/2 /2<br> 复制的次数大致等于比较的次数。复制和交换的时间耗费不同。相对于随机数据，这个算法比冒泡快一倍，比选择排序略快。<br> 对于已经有序或基本有序的数据来说，插入排序要好得多。对于逆序排列的数据，每次比较和移动都会执行，所以插入排序不比冒泡排序快。 * */ for(out=1;out<a.length;out++){ int t=a[out]; in=out; while(in>0 && a[in-1]>=t){ a[in]=a[in-1]; --in; } a[in]=t; } return a; } }
//选择排序 public class Select_sort { public static void main(String[] args) { int [] a={3,5,2,6,4,34,8,7,5,1,23}; int[] s=seletcSort(a); for(int i=0;i<s.length;i++){ System.out.print(s[i]+"--"); } } public static int[] seletcSort(int[] a){ int out,in,min; for(out=0;out<a.length-1;out++){ min=out; //System.out.print("--"+min+"-"+a[min]); //int [] a={3,5,2,6,4,34,8,7,5,1,23}; for(in=out+1;in<a.length;in++){ if(a[in]<a[min]){ min=in; } } int t=a[out]; a[out]=a[min]; a[min]=t; } return a; } }
//归并排序 /* * 归并时间复杂度只要O(NlogN),而冒泡排序，选择排序，插入排序都要用O(N*N) 归并排序的思想是：将一个数组分成两半，然后分别排序，然后将数组的两半合并，合并的时候需要比较大小 (合并的时候还要考虑两小数组还有没有数据，即有可能一边有，另一边没有)。 至于如何排序1/2半的数组，当然是再分成两个1/4数组，再排序。。。直到分割的小数组只有1个数据项，不用排序了。这是用到递归的思想 归并排序的缺点，需要在存储器中有另一个大小等于被排序的数据项数目的空间，用来复制分割出来的小数组。 归并算法的效率由来：需要复制log2/N层(分子数组)，每一个层都是N个数据，所以是NxlogN. * */ public class Merg_sort { public static void main(String[] args) { int [] a={3,5,2,6,4,34,8,7,5,4,23}; int[] s=mergSort(a); for(int i=0;i<s.length;i++){ System.out.print(s[i]+"--"); } } public static int[] mergSort(int[] a){ int[] temp=new int[a.length]; reMergeSort(a,temp,0,a.length-1); return a; } private static void reMergeSort(int[] a, int[] temp, int low, int hight) { if(low==hight){ return; } else{ int mid=(low+hight)/2; reMergeSort(a,temp,low,mid); reMergeSort(a,temp,mid+1,hight); merge(a,temp,low,mid+1,hight); } } private static void merge(int[] a, int[] temp, int low, int mid, int hight) { int j=0 ; int low1=low; int mid1=mid-1; int n=hight-low+1; while(low<=mid1 && mid<=hight){ if(a[low]<a[mid]){ temp[j++]=a[low++]; }else{temp[j++]=a[mid++];} } while(low<=mid1){ temp[j++]=a[low++]; } while(mid<=hight){ temp[j++]=a[mid++]; } for(j=0;j<n;j++){ a[low1+j]=temp[j]; } } }
//希尔排序 /* * 希尔排序基于插入排序，但增加了一个新的特性，大大地提高了插入排序的执行效率。(希尔是个人名。。。) 改进的地方：插入算法中，如果一个数据比较小而居于最右边，那么它需要一个一个地移动所有中间的数据项，效率比较低。 希尔排序通过加入插入排序中元素之间的间隔，并在这些有间隔的元素中进行插入排序，从而使数据项能大跨度地移动。 当这些数据项排过一趟序后，减小数据项的间隔。再进行排序，依次进行下去。间隔被称为增量，用h表示.<br> 进行过几次增量排序后，所有的元素离它再最终有序序列中的位置相差不大，数组达到"基本有序",这时再来插入排序，移动量非常小 当h值很大的时候，数据项每一趟排序需要移动元素的个数很少，但数据项移动的距离很长， 这是非常有效率的。当h减少时，每一趟排序需要移动的元素的个数增多，但是此时数据项已经接近于它们排序后最终的位置， 这对于插入排序可以更有效率。 其中，h = h x 3 +1, h = (h -1) / 3,是经验值。 * * * */ public class Sell_sort { public static void main(String[] args) { int [] aa={3,5,2,6,4,34,8,7,5,4,23}; int[] a=sellSort(aa); for(int t=0;t<a.length;t++){ System.out.print(a[t]+"--"); } } void shellsort1(int a[], int n) { int i, j, gap; for (gap = n / 2; gap > 0; gap /= 2) //步长 for (i = 0; i < gap; i++) //直接插入排序 { for (j = i + gap; j < n; j += gap) if (a[j] < a[j - gap]) { int temp = a[j]; int k = j - gap; while (k >= 0 && a[k] > temp) { a[k + gap] = a[k]; k -= gap; } a[k + gap] = temp; } } } public static int[] sellSort(int [] a){ int in,out,t; int h=1; for(h=a.length/2;h>0;h/=2) for(out=0;out<h;out++){ for(in=out+h;in<a.length;in+=h) if(a[in]<a[in-h]){ int temp=a[in]; int k=in-h; while(k>=0 && a[k]>temp){ a[k+h]=a[k]; k-=h; } a[k+h]=temp; } } return a; } static void shellsort3(int a[]) { int i, j, h; int n=a.length; for (h = n / 2; h > 0; h /= 2) { for (i = h; i < n; i++) { for (j = i - h; j >= 0 && a[j] > a[j + h]; j -= h) { int t=a[j]; a[j]=a[j+h]; a[j+h]=t; } } } for(int t=0;t<a.length;t++){ System.out.print(a[t]+"--"); } } }
