排序算法探讨.docVIP

　　排序大的分类可以分为两种：内排序和外排序。在排序过程中，全部记录存放在内存，则称为内排序，如果排序过程中需要使用外存，则称为外排序。下面讲的排序都是属于内排序。 　　内排序有可以分为以下几类： 　　(1)、插入排序：直接插入排序、二分法插入排序、希尔排序。 　　(2)、选择排序：简单选择排序、堆排序。 　　(3)、交换排序：冒泡排序、快速排序。 　　(4)、归并排序 　　(5)、基数排序 ? 一、插入排序 ?思想：每步将一个待排序的记录，按其顺序码大小插入到前面已经排序的字序列的合适位置，直到全部插入排序完为止。 ?关键问题：在前面已经排好序的序列中找到合适的插入位置。 ?方法： –直接插入排序 –二分插入排序 –希尔排序 ①直接插入排序（从后向前找到合适位置后插入） 　　1、基本思想：每步将一个待排序的记录，按其顺序码大小插入到前面已经排序的字序列的合适位置（从后向前找到合适位置后），直到全部插入排序完为止。 　　2、实例 public class insertSort2 { public static void main(String[] args) { int[] a={1,45,7,8,56,41,21}; int j; for(int p=1;pa.length;p++) { int temp=a[p]; for(j=p;j0 tempa[j-1];j--) a[j] = a[j-1]; a[j]=temp; } } } 　　4、分析 直接插入排序是稳定的排序。关于各种算法的稳定性分析可以参考　 　文件初态不同时，直接插入排序所耗费的时间有很大差异。若文件初态为正序，则每个待插入的记录只需要比较一次就能够找到合适的位置插入，故算法的时间复杂度为O(n)，这时最好的情况。若初态为反序，则第i个待插入记录需要比较i+1次才能找到合适位置插入，故时间复杂度为O(n2)，这时最坏的情况。 直接插入排序的平均时间复杂度为O(n2)。 ②二分法插入排序（按二分法找到合适位置插入） 　　1、基本思想：二分法插入排序的思想和直接插入一样，只是找合适的插入位置的方式不同，这里是按二分法找到合适的位置，可以减少比较的次数。 　　2、实例 　　3、java实现 2 3 public class 二分插入排序 { 4 public static void main(String[] args) { 5 int[] a={49,38,65,97,176,213,227,49,78,34,12,164,11,18,1}; 6 10 //二分插入排序 11 sort(a); 12 System.out.println(); 13 System.out.println(排序之后：); 14 for (int i = 0; i a.length; i++) { 15 System.out.print(a[i]+ ); 16 } 17 } 18 19 private static void sort(int[] a) { 20 for (int i = 0; i a.length; i++) { 21 int temp = a[i]; 22 int left = 0; 23 int right = i-1; //而不是a.length;一个个插入到前面。 24 int mid; 25 while(left=right){ 26 mid = (left+right)/2; 27 if(tempa[mid]){ 28 right = mid-1; 29 }else{ 30 left = mid+1; 31 } 32 } 33 for (int j = i-1; j = left; j--) { 34 a[j+1] = a[j]; 35 } 36 if(left != i){ 37 a[left] = tem