median = array[inner];
array[inner] = array[inner -1];
array[inner -1] = median;
}
}
}
}
void insert_sort(int array[], int length)
{
int inner = 0;
int outer = 0;
int median = 0;
if(NULL == array || 0 == length)
return;
for(outer = 1; outer for(inner = outer; inner >= 1; inner --){ if(array[inner] < array[inner -1]){ median = array[inner]; array[inner] = array[inner -1]; array[inner -1] = median; } } } } 那么插入排序有没有像冒泡排序那样的改进方法呢？其实没有。因为每一次插入排序的位置都是局部比较的结果，而冒泡排序每一次的内容都是全局最优的。这从数据比较的次数就可以看出来。 （3）希尔排序 希尔排序，我个人认为可以看成是冒泡排序的变种。它的基本思想是：首先按照一个序列递减的方法逐渐进行排序。比如说有10个数据，我们按照序列5、3、1的顺序进行排序。首先是5，那么我们对1和6、2和7、3和8、4和9、5和10进行排列；第二轮是3，那么对数据1、4、7、10排列，再对2、5、8进行排列，以及3、6、9排列；第三轮就和冒泡排序一样了，以此对每个数据进行排列。它的优势就是让整个队列基本有序，减少数据移动的次数，从而降低算法的计算复杂度。 void shell_sort(int array[], int length, int step) { int inner = 0; int outer = 0; int median = 0; if(NULL == array || 0 == length) return; for(; step >= 1; step -=2){ for(int index = 0; index < step; index ++){ if((length -1) < (index + step)) continue; else{ outer = index + step; while( (outer + step) <= (length - 1)) outer += step; } for(; outer >= (index + step); outer -= step){ for(inner = index; inner <= outer - step; inner += step){ if(array[inner] >= array[inner + step]){ median = array[inner]; array[inner] = array[inner + step]; array[inner + step] = median; } } } } } } void shell_sort(int array[], int length, int step) { int inner = 0; int outer = 0; int median = 0; if(NULL == array || 0 == length) return; for(; step >= 1; step -=2){ for(int index = 0; index < step; index ++){ if((length -1) < (index + step)) continue; else{ outer = index + step; while( (outer + step) <= (length - 1)) outer += step; } for(; outer >= (index + step); outer -= step){ for(inner = index; inner <= outer - step; inner += step){ if(array[inner] >= array[inner + step]){ median = array[inner]; array[inner] = array[inner + step]; array[inner + step] = median; } } } } } } 总结： （1）上面的排序都是非递归程序，理解上不难，但是细节问题需要注意，特别是长度的问题 （2）代码编写的时候务必注意测试用例的设计 （3）如果可能的情况下，多使用已经验证的代码和函数 【预告： 下一篇博客介绍快速排序的内容】