C++入门手写直接插入排序_直接插入排序手写c++

/* Note:Your choice is C IDE */
#include "stdio.h"
#define MAX 100
struct slist
{
	int a[MAX];
	int len;	
}; 
//直接插入排序  传 结构体指针   不要返回值 
void  fun(struct slist *s)
{
	int i,j,t;
	//10个需要9趟  循环9遍
	for(i=1;i<s->len;i++)  //i 1.表示循环的遍数  2.表示无序区下标
	{
		t=s->a[i]; //第i趟 取s->a[i] 放在变量t里面。
		//有序区下标范围[0,i-1]   
		for(j=i-1;j>=0&&t<s->a[j];j--) //j 代表有序区下标
		{
			s->a[j+1]=s->a[j];//有序区元素后移
		}
		//空余的地方
		s->a[j+1]=t;
	}	
	//输出
	for(i=0;i<s->len;i++)
	{
		printf("%d\t",s->a[i]);	
	}
}
void main()
{
	int i;
	struct slist s;
	s.len=0;	
    for(i=0;i<10;i++)
    {
    	printf("请输入第%d个元素:",s.len+1);
    	scanf("%d",&s.a[s.len]);
    	s.len++;	
    }
    //直接插入排序
    fun(&s);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

直接插入排序，也是一个比较常用的排序，它的实现原理，是从第二位开始，每一个拿出数，和前面所有的数比较，达到换位的条件时，不是直接交换，而是让数据向后占用位置，当比较到不需要前面的数据向后占位的时候说明这次比较可以结束了，将先前拿出的那个数放到最后空余出来的位置上

直接插入排序，新手程序员可能有一个不解，就是什么导致了不发生向后占位的时候就表明本次排序结束了，其实关于这点，大家想一想，直接插入排序在最开始那一趟的时候就一定是从第二位开始拿出数据向前比较的，那么也就是说后面的排序，每当停止占位的时候，那前面没有比较的数据，其实一定是有序的，大家可以仔细考虑一下我说的话