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