插入排序是通過構建有序序列，對于未排序數據，在已排序序列中從后向前掃描，找到相應位置并插入。
基本步驟:
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 閱讀(1561)
評論(0) 編輯 收藏