UC知道求高手帮忙做一道程序题！
来源：百度知道 编辑：UC知道 时间：2024/09/22 13:40:47
读下面的程序，说出该程序实现的功能是什么？程序实现的思路是什么？
Void InsertionSort (Type a[], int n)
{
For ( int j=2 ; j<=n ; j++) {
Type item=a[j];
int i=j-1;
While (( i>=1 ) && ( item < a[ i ]) ) {
a [i+1] = a [i];
i--;
}
a [i+1] = item;
}
}
Void InsertionSort (Type a[], int n)
{
For ( int j=2 ; j<=n ; j++) {
Type item=a[j];
int i=j-1;
While (( i>=1 ) && ( item < a[ i ]) ) {
a [i+1] = a [i];
i--;
}
a [i+1] = item;
}
}
很明显，从命名就可以看出是个插入排序的算法，其实现的功能：实现一个数列的有序性。
其基本思想如下所示：
将n个元素的数列分为已有序和无序两个部分，每次处理就是将无序数列的第一个元素与有序数列的元素从后往前逐个进行比较，找出插入位置，将该元素插入到有序数列的合适位置中。
具体步骤如下所示：
1.从有序数列{a0,a1}和无序数列{a2,a3,…,an-1}开始进行排序；
2.处理第下标为i的元素时(i=2,3,…,n-1) , 数列{a0,a1,…,ai-2，ai-1}是已有序的,而数列{ai,ai+1,…,an-1}是无序的。用ai与ai-1，ai-2,…,a0进行比较,找出合适的位置将ai插入；
3.重复第二步，共进行n-1次插入处理，数列全部有序。
算法的基本思路如下：
假定这个数组的序是排好的,然后从头往后,如果有数比当前外层元素的值大,则将这个数的位置往后挪,直到当前外层元素的值大于或等于它前面的位置为止.这使算法在排完前k个数之后,可以保证a[0…k-1]是局部有序的,保证了插入过程的正确性。
希望我的回答对你有所帮助……
还有什么疑问或是需要解释的，可以HI我……
插入排序
一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：
1. 从第一个元素开始，该元素可以认为已经被排序
2. 取出下一个元素，在已经排序的元素序列中从后向前扫描
3. 如果该元素（已排序）大于新元素，将该元素移到下一位置
4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
5. 将新元素插入到该位置中
6. 重复步骤2