排序(Sort)

排序(Sort)是将无序的记录序列（或称文件）调整成有序的序列。

排序的目的是方便我们队数据查询记录、修改记录等操作。

排序的分类

按稳定性可分为稳定排序和非稳定排序，按待排序数据的存储位置又可分为内排序和外排序。

截止目前，各种内排序方法可归纳为以下五类：
（1）插入排序
（2）交换排序
（3）选择排序
（4）归并排序
（5）基数排序。

本次介绍的是简单常用的排序算法，直接插入排序属于内排序算法！

直接插入算法  

时间复杂度： T(n)=O(n2)

算法思路：排序过程中，数据序列分成已排序和待排序两个部分，将待排序中的数据元素和各个已排序的数据逐一比较。如果从数据大的一端开始比较的话，数据元素小于序列中的元素，则将序列中的部分元素偏移，产生一个空位，再比较下一个序列元素；数据元素大于序列中的元素，则插入填补空位。

  

   

    

     

    
    

     

      #include "stdio.h"
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      void insert_sort(int data[], int len);	//直接插入排序
     
    
   

    

     

    
    

     

      void insert_show(int data[], int len);	//显示
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      void insert_sort(int data[], int len)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	int i,j,temp;
     
    
   

    

     

    
    

     
	for (i = 1;i < len;i++)
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     

      		temp = data[i];	//设定待插入值
     
    
   

    

     

    
    

     
		for (j = i-1;j >= 0;j--)
     
    
   

    

     

    
    

     

      		{
     
    
   

    

     

    
    

     
			if (temp < data[j])
     
    
   

    

     

    
    

     

      			{
     
    
   

    

     

    
    

     

      				data[j+1] = data[j];	//元素→移动
     
    
   

    

     

    
    

     

      			}
     
    
   

    

     

    
    

     
			else
     
    
   

    

     

    
    

     

      			{
     
    
   

    

     

    
    

     
				break;
     
    
   

    

     

    
    

     

      			}
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     

      		data[j+1] = temp;	//填补空位
     
    
   

    

     

    
    

     
		insert_show(data, len);
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      void insert_show(int data[], int len)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	int i;
     
    
   

    

     

    
    

     
	for (i = 0;i < len;i++)
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     
		printf("%d,",data[i]);
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	printf("\n");
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int main(void)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	int data[] = {3, 2, 1, 4, 7};
     
    
   

    

     

    
    

     
	int len = sizeof(data)/sizeof(int);
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
	insert_show(data, len);
     
    
   

    

     

    
    

     
	insert_sort(data, len);
     
    
   

    

     

    
    

     

      }
     
    
  
 

排序过程

文章来源: blog.csdn.net，作者：hinzer，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/feit2417/article/details/81196763