假设小明用某个排序算法对整数序列（82,45,25,15,21）进行排序。以下为排序过程中序列状态的变化过程：
输入：82 45 25 15 21
第一步：45 82 25 15 21
第二步：25 45 82 15 21
第三步：15 25 45 82 21
······
请问小明用的是什么排序算法？
白驹之过隙
选D。该题考查的是不同排序方法的原理，从题目中可以得出是逐步将待排序的元素插入到已排序序列的对应位置，属于插入排序。
选择排序：将第一个元素作为基准，后面的元素依次和第一个元素做比较选出最小元素，并和第一个元素交换位置，所以经过第一步排序可以确定整个序列的最小元素。A不正确。
归并排序：两两合并排序，第一步的元素25，15应该交换位置作为子序列，所以B不正确。
快速排序：需要枢轴值为比较对象，第一步排序后会将序列分为大于枢轴和小于枢轴两部分，题目选项后三个元素均小于枢轴而没有放到枢轴之前，所以C不正确。
编辑于 2019-04-11 14:21:41
回复(0)
选D。插入排序
/*
* 直接插入排序（稳定,时间复杂度：O（n^2））
* 基本思想:
* 将一个记录插入到已排序好的有序表中，从而得到一个新，记录数增1的有序表。即：先将序列的第1个记录看成是一个有序的子序列，
* 然后从第2个记录逐个进行插入，直至整个序列有序为止。
* 要点：设立哨兵，作为临时存储和判断数组边界之用。
* 如果碰见一个和插入元素相等的，那么插入元素把***的元素放在相等元素的后面。
* 所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。
*/
public class DirectInsertSort {
public void directInsertSort(int[] a){
for(int i = 1; i< a.length; i++){
int key = a[i];//复制为哨兵，即存储待排序元素
int j = i;
for(; j > 0 && key < a[j-1]; j--){ //若第i个元素大于i-1元素，直接插入。小于的话，移动有序表后插入
a[j] = a[j-1];//先后移一个元素,查找在有序表的插入位置
}
a[j] = key;//插入到正确位置
}
}
}
* 直接插入排序（稳定,时间复杂度：O（n^2））
* 基本思想:
* 将一个记录插入到已排序好的有序表中，从而得到一个新，记录数增1的有序表。即：先将序列的第1个记录看成是一个有序的子序列，
* 然后从第2个记录逐个进行插入，直至整个序列有序为止。
* 要点：设立哨兵，作为临时存储和判断数组边界之用。
* 如果碰见一个和插入元素相等的，那么插入元素把***的元素放在相等元素的后面。
* 所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。
*/
public class DirectInsertSort {
public void directInsertSort(int[] a){
for(int i = 1; i< a.length; i++){
int key = a[i];//复制为哨兵，即存储待排序元素
int j = i;
for(; j > 0 && key < a[j-1]; j--){ //若第i个元素大于i-1元素，直接插入。小于的话，移动有序表后插入
a[j] = a[j-1];//先后移一个元素,查找在有序表的插入位置
}
a[j] = key;//插入到正确位置
}
}
}
发表于 2019-04-10 18:45:57
回复(0)
问题信息
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
