最近学习算法，从一些经典的排序算法开始。
这篇讲的是我对插入排序的一些心得
来源百度百科：
插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为O(n^2)。是稳定的排序方法。
将一个数据插入到已经排好序的有序数据中
思路：
- 将一个元素插入到已有序数组中，初始时未知数组是否有序，所以将数组第一个元素看成是有序的
- 与有序数组依次比较，比他大就直接就插入。比它小就移动数组元素位置，找到合适的位置插入
- 因为第一位看成是有序，所以从第二位开始比较。需要n-1趟排序，比如10个数，需要9趟排序。
代码实现思路：
for循环镶嵌while循环。for循环控制排序趟数，while循环找到合适的插入位置（插入位置不能小于0）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
//插入排序
public static void insertSort(int[] array){
int temp;//中间变量
for (int i=1;i<array.length;i++) {//外层循环控制需要排序趟数，从1开始是因为将第0位看为有序数据
temp=array[i];
//前一位数据比当前数据要大，那么就进入循环比较
int j=i-1;
while(j >= 0 && array[j]>array[j+1]){
//较大值往后退一个位置，让当前数据与之前前位进行比较
array[j+1]=array[j];
//不断向前
j--;
}
//退出了循环说明找到了合适的位置了，将当前数据插入合适的位置中
array[j+1]=temp;
}
}
|
参考资料：
[]: https://segmentfault.com/a/1190000014008568
近期评论