插入排序是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
基本步骤:
1. 从第一个元素开始，该元素可以认为已经被排序
2. 取出下一个元素，在已经排序的元素序列中从后向前扫描
3. 如果该元素（已排序）大于新元素，将该元素移到下一位置
4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
5. 将新元素插入到该位置后
6. 重复步骤 2 ~ 5
C++ 实现
//直接插入排序
//按自然顺序
void insertsort(Element array[], int len){
Element e;
int index;
for(int i = 1; i < len; i++){ //默认第一个元素(下标索引值0)已经有序
e = array[i]; //待排序元素
for(index = i - 1; index >= 0 && array[index] > e; index--){ //待排序元素较小
array[index + 1] = array[index]; //后移
}
array[index + 1] = e; //插入待排序元素
}
}
Java 实现
//直接插入排序,按自然顺序
public static void insertsort(int[] array){
int key, index; //key:待排序数, index:已排序下标索引值
for(int i = 1; i < array.length; i++){ //默认第一个元素(下标从0开始)已经有序
key = array[i]; //待排序元素
for(index = i - 1; index >= 0 && array[index] > key; index--){ //待排序数较小
array[index + 1] = array[index]; //后移
}
array[index + 1] = key; //插入待排序元素
}
}
C++ 实现完整代码
/**
* <!--
* File : insertsort.h
* Author : fancy
* Email : fancydeepin@yeah.net
* Date : 2013-02-05
* --!>
*/
#include <stdio.h>
#include <stdlib.h>
#define length(array) sizeof(array) / sizeof(array[0])
#define Element int
#define format "%d"
//直接插入排序
//按自然顺序
void insertsort(Element array[], int len){
Element e;
int index;
for(int i = 1; i < len; i++){ //默认第一个元素(下标索引值0)已经有序
e = array[i]; //待排序元素
for(index = i - 1; index >= 0 && array[index] > e; index--){ //待排序元素较小
array[index + 1] = array[index]; //后移
}
array[index + 1] = e; //插入待排序元素
}
}
//遍历数组
void visit(Element array[], int len){
for(int i = 0; i < len; i++){
printf(format, array[i]);
}
}
/**
* <!--
* File : InsertSort.cpp
* Author : fancy
* Email : fancydeepin@yeah.net
* Date : 2013-02-05
* --!>
*/
#include "insertsort.h"
int main() {
Element array[8] = {6, 5, 3, 1, 8, 7, 2, 4};
int len = length(array);
printf("\n排序前: ");
visit(array, len);
printf("\n直接插入排序: ");
insertsort(array, len);
visit(array, len);
/**
* 控制台输出结果:
*
* 排序前: 65318724
* 直接插入排序: 12345678
*/
return 0;
}
Java 实现完整代码
package net.yeah.fancydeepin.sort.insert;
/**
* <!--
* Author : fancy
* Email : fancydeepin@yeah.net
* Date : 2013-02-05
* --!>
*/
public class Sort {
private Sort(){}
//直接插入排序,按自然顺序
public static void insertsort(int[] array){
int key, index; //key:待排序数, index:已排序下标索引值
for(int i = 1; i < array.length; i++){ //默认第一个元素(下标从0开始)已经有序
key = array[i]; //待排序元素
for(index = i - 1; index >= 0 && array[index] > key; index--){ //待排序数较小
array[index + 1] = array[index]; //后移
}
array[index + 1] = key; //插入待排序元素
}
}
}
package test;
/**
* <!--
* Author : fancy
* Email : fancydeepin@yeah.net
* Date : 2013-02-05
* --!>
*/
import net.yeah.fancydeepin.sort.insert.Sort;
public class Test {
public static void main(String[] args) {
int[] array = {6, 5, 3, 1, 8, 7, 2, 4};
Sort.insertsort(array);
for(int obj : array){
System.out.print(obj);
}
}
}
posted on 2013-02-05 13:13
fancydeepin 阅读(1558)
评论(0) 编辑 收藏