1. 插入排序概念
插入排序的基本方法是:每一步将一个待排序的元素,按其排序码的大小,插入到前面已经排好序的一组元素的适当位置上去,直到元素全部插入为止。
可以选择不同的方法在已经排好序数据表中寻找插入位置。根据查找方法不同,有多种插入排序方法,下面要介绍的是直接插入排序。
2. 直接插入排序基本思想
直接插入插排的基本思想是:当插入第i(i >= 1)时,前面的V[0],V[1],……,V[i-1]已经排好序。这时,用V[I]的排序码与V[i-1],V[i-2],…的排序码顺序进行比较,找到插入位置即将V[i]插入,原来位置上的元素向后顺移。
在图一中给出了直接插入排序的过程。
设在元素表中有n = 6个元素,为了使描述书简介直观,在图中只画出各元素的排序码。其中有两个排序码相同,前一个直接写为25,后一个标记为25*。
假定其中V[0],…,V[i-1]已经是一组有序的元素,V[i],V[i+1],……,V[n-1]是带插入的元素。排序过程从i = 1起,每执行完一趟之后i增加1,把第i各元素插入到前面有序的元素序列中去,使插入后的元素序列V[0],V[1],……,V[i-1]仍保持有序。
图一(b)是一趟排序过程(i = 4)的示例。此时,从V[0]到V[3]已经排好序,算法先比较V[4]与V[3],因为V[4]
3. 直接插入排序源代码
template
void InsertSort(T* array, int n) { //array待排序数组,n:数组元素数量
int i, j; //循环变量
T temp; //存储待排序元素
for (i = 1; i < n; i++) {
j = i;
temp = array[i]; //待排序元素赋值给临时变量
while (j > 0 && temp < array[j - 1]) { //当未达到数组的第一个元素或者待插入元素小于当前元素
array[j] = array[j - 1]; //就将该元素后移
j--; //下标减一,继续比较
}
array[j] = temp; //插入位置已经找到,立即插入
}
}
4. 直接插入排序时间复杂度分析
若设待排序的元素个数为n,则该算法会执行n-1趟。
因为排序码比较次数和元素移动次数与元素排序码的初始排列有关,所以在最好的情况下,即在排序前元素已经按排序码大小从小到大排好了,每趟只需与前面的有序元素序列
最后一个元素的排列吗进行比较,总的排序码比较次数为n-1,元素移动次数为0。
而在最差的情况下,及第i趟时第i个元素必须与前面i个元素都做排序码的比较,并且每做一次就叫就要做一次数据移动,则在最坏的情况下排序码的排序码比较次数KCN和元素移动次数RMN分别为:
从上面的讨论可以看出来,直接插入排序的运行时间和待排序元素的原始排序顺序密切相关。
如果待排序元素序列中出现各种可能排列的概率相同,则可以取上述最好和最坏情况的平均情况,在平均情况下的排序码比较次数和元素移动次数约为n^2/4。
因此,直接插入排序的时间复杂度为O(n^2)。并且直接插入排序是一种稳定的排序方法。
代码之路任重道远,愿跟你们努力习之
把简单题目想复杂了
怎么没能早点看到你这篇文章呢
跟着大佬输出,感觉能量满满