插入排序

插入排序通过构建有序序列,对于未排序的数据,从已排序的序列从后向前扫描,并找到相应的位置插入。

算法描述

  1. 从第一个元素开始,默认第一个元素已排序;
  2. 取出下一个元素i,从已排序的元素序列中从后向前扫描;
  3. 对比每一个已排序的元素,将大于(小于)改元素的已排序元素向后移一个位置直到找到小于(大于)该元素的位置,将i 排在这个元素的后面;
  4. 重复2-3直到遍历结束,排序完成;

代码实现

1
2
3
4
5
6
7
8
9
10
11
public void sort(int[] arr, int n) {
for(int i = 1;i < n; i++) {
for(j = i+1; j > 0; j--) {
if(arr[j] < arr[j-1]) {
int temp = arr[j];
arr[j] = arr[j-1];
arr[j-1] = arr[j];
}
}
}
}

微信公众号

© 2018 ray