数据结构--简单排序_插入排序

插入排序算法：

渐进时间复杂度O(N^2)

比冒泡排序快一倍

插入排序方法：

要把第一个元素当成是有序的。（所以写代码的时候外层循环是从1开始的）

首先将第二个元素拿出来，放到临时数据的地方，然后和第一个进行比较，谁小就放在前面

然后将第三个元素拿出来，放到临时数据的地方，再依次和第二个元素比较，第一个元素比较。放到指定的位置

然后将第四个元素拿出来，放到临时数据的地方，再依次和第三个元素比较，第二个元素比较，第一个元素比较，放到指定的位置。

依次类推。

举例：

例如一组数据按照插入排序算法进行排序

12,34,2,45,6

==================================================================================================

第一次排序：

12,2,45,6   将第二个元素拿出来当成是临时数据，也就是temp=34，然后和第一个元素比较，12小于34所以排序为：

12,34,2,45,6

==================================================================================================

第二次排序

12,34,45,6  将第三个元素拿出来当成是临时数据，也就是temp=2,然后依次和第二个元素比较，第一个元素比较，所以排序为：

2,12,34,45,6

==================================================================================================

第三次排序

2,12,34,6  将第四个元素拿出来当成是临时数据，也就是temp=45,然后依次和第三个元素比较，（因为都是有序的所以不用再和第二个元素和第一个元素比较），所以排序为:

2,12,34,45,6

==================================================================================================

第四次排序

2,12,34,45 将第五个元素拿出来当成是临时数据，也就是temp=6,然后依次和第四个元素比较，第三个元素比较，第二个元素比较，第一个元素比较，所以排序为：

2,6,12,34,45

==================================================================================================

java代码：

public class InsertSort {

	private long[] a;
	public int elements;
	
	public InsertSort(int max) {
		// TODO Auto-generated constructor stub
		a=new long[max];
		elements=0;
	}
	
	public void insert(long value){
		a[elements]=value;
		elements++;
	}
	
	public void display(){
		for(int j=0;j<elements;j++)
			System.out.print(a[j]+" ");
		System.out.println();
	}
	
	public void insertSort(){
		int out,in;//定义一个外层循环和内层循环的变量
		for(out=1;out<elements;out++){//外层循环从第一个元素开始
			long temp=a[out];//将该元素赋值给临时数据
			in=out;
			while(in>0&&a[in-1]>temp){//内层循环必须比0大
				a[in]=a[in-1];
				in--;
			}
			a[in]=temp;
		}
	}
	
	public static void main(String[] args) {
		InsertSort insertSort=new InsertSort(100);
		
		insertSort.insert(125);
		insertSort.insert(233);
		insertSort.insert(12);
		insertSort.insert(332);
		insertSort.insert(11);
		
		System.out.println("没有排序前：");
		insertSort.display();
		
		System.out.println("排序后：");
		insertSort.insertSort();
		insertSort.display();
	}
}
           

或者：

/*
简单插入排序函数 
*/
void insertSort(int *arr[],int len){
    int i;
    int j;
    int temp;  //定义一个临时变量，用于交换数据时存储 
    for(i=1;i<len;i++){  //因为我们要对该待排序列的每一个元素都和前面的已排好序的序列进行插入，所以我们会对序列进行遍历 
        for(j=0;j<i;j++){  //第二层循环主要用于对已排好序的序列进行扫描，和要插入进来的数据进行逐一比较，然后决定插入到哪里 
            if(arr[j]>arr[i]){//从前往后对已排好序的元素和待插入元素进行大小比较，然后直到找到一个元素比被插入元素大，则交换位置 
                temp=arr[i];
                arr[i]=arr[j];
                arr[j]=temp;
            }
        }
    }
}