java的算法排序法.docx

课XXXXX 学院 课 程设计 作 者： XXX 辅导老 师： XXX 系 部： 信息工程系 专 业： JAVA 面向对象程序设计 题 目： JAVA 的排序算法 2010-12-23 JAVA 排序算法 第 第 PAGE 10 页 /共 23 页 排序算法 （序） 在我们编写程序的时候，经常会碰到算法问题。所谓算法（ Alglrithm），就是在有限的步骤内求解某一问题所使用的一组定义明确的规则。算法的好坏直 接影响到程序运行的效率，因此，选择一个好的算法 对于编写高效的程序是至关重要的。 以下为算法的主要排序法 直接插入排序 3. 折半插入排序 4. 起泡排序 6. 简单选择排序 8. 希尔排序 10. 快速排序 12. 堆排序 15. 二路归并排序 18. 基数排序 20. 时间复杂度和空间复杂度对照表 23. 直接插入排序 一、 基本思想： 将数组分成两个小的数组，每次从后面的数组中取出索引最小的数组元素，插入到前面数组的适当位置，使得插入到前面的数组后，它前面的数组元素都比它小，而后面的元素都比它大。通常在开始进行排序的时候，就数组的第一个元素作为一个数组，而将后面的所有元素当成第一个数组。 二、 排序过程演示： int[] arr ={52,22,7,100,23,19,123,10}; (选择第一个元素作为前面的数组)： step 1: 【22 52】 7 100 23 19 123 10 step 2: 【7 22 52】 100 23 19 123 10 step 3: 【7 22 52 100】 23 19 123 10 step 4: 【7 22 23 52 100】 19 123 10 step 5: 【7 19 22 23 52 100】 123 10 step 6: 【7 19 22 23 52 100 123】 10 step 7: 【7 10 19 22 23 52 100 123】 三、 算法代码： public class InjectionSort{ //插入排序方法 public static void injictionSort(int[] Number){ //第一个元素作为一部分，对后面的部分进行循环for(int j=1;jNumber.length;j++){ int tmp=Number[j]; int i=j-1; while(tmpNumber[i]){ Number[i+1]=Number[i]; i--; if(i==-1){ break; } } Number[i+1]=tmp; } } public static void main(String[] args){ int[] num={2,1,5,876,12,56}; injictionSort(num); for(int i=0;inum.length;i++){ System.out.println(num[i]); } } } 小结： 比较总次数 n－1＝O（n） 移动次数 2*(n－1)＝O（n） 最好的情况下,数组是有序的,不需要执行 while 语句，时间复杂度为 O(n); 最坏的情况下 t(n)=1+2+3+…….+(n-1)=1/2(n*n)-1/2n;时间复杂度为 O(n*n); 由此可知：平均复杂度=O(n*n) 折半插入排序 一、 基本思想： 每次将一个待排序的数据元素，插入到前面已经排好序的数列中的适当位置，通过择半查找的方法，使数列依然有序；直到待排序数据元素全部插入完为止。 二、 排序过程演示 int[] arr={13 675 45 22 121 233 22 43 2 6} step 1: 【13 675 45 22 121 233 22 43 2 6】 step 2: 【13 45 675 22 121 233 22 43 2 6】 step 3: 【13 22 45 675 121 233 22 43 2 6】 step 4: 【13 22 45 121 675 423 22 43 2 6】 step 5: 【13 22 45 121 233 675 22 43 2 6】 step 6: 【13 22 22 45 121 233 675 43 2 6】 step 7: 【13 22 22 43 45 121 233 675 2 6】 step 8: 【2 13 22 22 43 45 121 233 675 6】 step 9: 【2 6 13 22 22 43 45 121 233 675】 三、 算法代码： public class HalfInsert{ public static void