各种排序算法的及java实现研究.docx

各种排序算法的分析及java实现　　排序一直以来都是让我很头疼的事，以前上《数据结构》打酱油去了，整个学期下来才勉强能写出个冒泡排序。由于下半年要准备工作了，也知道排序算法的重要性（据说是面试必问的知识点），所以又花了点时间重新研究了一下。　　排序大的分类可以分为两种：内排序和外排序。在排序过程中，全部记录存放在内存，则称为内排序，如果排序过程中需要使用外存，则称为外排序。下面讲的排序都是属于内排序。　　内排序有可以分为以下几类：　　(1)、插入排序：直接插入排序、二分法插入排序、希尔排序。　　(2)、选择排序：简单选择排序、堆排序。　　(3)、交换排序：冒泡排序、快速排序。　　(4)、归并排序　　(5)、基数排序?一、插入排序?思想：每步将一个待排序的记录，按其顺序码大小插入到前面已经排序的字序列的合适位置，直到全部插入排序完为止。?关键问题：在前面已经排好序的序列中找到合适的插入位置。?方法：–直接插入排序–二分插入排序–希尔排序①直接插入排序（从后向前找到合适位置后插入）　　1、基本思想：每步将一个待排序的记录，按其顺序码大小插入到前面已经排序的字序列的合适位置（从后向前找到合适位置后），直到全部插入排序完为止。　　2、实例　　　　3、java实现 1package com.sort; 2 3publicclass 直接插入排序 { 4 5publicstaticvoid main(String[] args) { 6int[] a={49,38,65,97,76,13,27,49,78,34,12,64,1}; 7 System.out.println(排序之前：); 8for (int i = 0; i a.length; i++) { 9 System.out.print(a[i]+ );10 }11//直接插入排序12for (int i = 1; i a.length; i++) {13//待插入元素14int temp = a[i];15int j;16/*for (j = i-1; j=0 a[j]temp; j--) {17 //将大于temp的往后移动一位18 a[j+1] = a[j];19 }*/20for (j = i-1; j=0; j--) {21//将大于temp的往后移动一位22if(a[j]temp){23 a[j+1] = a[j];24 }else{25break;26 }27 }28 a[j+1] = temp;29 }30 System.out.println();31 System.out.println(排序之后：);32for (int i = 0; i a.length; i++) {33 System.out.print(a[i]+ );34 }35 }3637 }?　　4、分析　　直接插入排序是稳定的排序。关于各种算法的稳定性分析可以参考/Braveliu/archive/2013/01/15/2861201.html　　文件初态不同时，直接插入排序所耗费的时间有很大差异。若文件初态为正序，则每个待插入的记录只需要比较一次就能够找到合适的位置插入，故算法的时间复杂度为O(n)，这时最好的情况。若初态为反序，则第i个待插入记录需要比较i+1次才能找到合适位置插入，故时间复杂度为O(n2)，这时最坏的情况。　　直接插入排序的平均时间复杂度为O(n2)。②二分法插入排序（按二分法找到合适位置插入）　　1、基本思想：二分法插入排序的思想和直接插入一样，只是找合适的插入位置的方式不同，这里是按二分法找到合适的位置，可以减少比较的次数。　　2、实例　　3、java实现 1package com.sort; 2 3publicclass 二分插入排序 { 4publicstaticvoid main(String[] args) { 5int[] a={49,38,65,97,176,213,227,49,78,34,12,164,11,18,1}; 6 System.out.println(排序之前：); 7for (int i = 0; i a.length; i++) { 8 System.out.print(a[i]+ ); 9