排序算法005-插入排序


一、什么是插入排序?


插入排序原理很简单,讲一组数据分成两组,我分别将其称为有序组与待插入组。每次从待插入组中取出一个元素,与有序组的元素进行比较,并找到合适的位置,将该元素插到有序组当中。就这样,每次插入一个元素,有序组增加,待插入组减少。直到待插入组元素个数为0。当然,插入过程中涉及到了元素的移动。

为了排序方便,我们一般将数据第一个元素视为有序组,其他均为待插入组。


二、插入排序步骤演示

happysneaker.com

动画演示:

happysneaker.com



三、代码实现


C 实现:

#include<stdio.h>
  void InsertionSort(int *num,int n) 
  {
  	int i = 0;
  	int j = 0;
  	int tmp = 0;
  	for(i = 1;i<n;i++)
  	{
      tmp = num[i];//从待插入组取出第一个元素。 
	  j = i-1; //i-1即为有序组最后一个元素(与待插入元素相邻)的下标 
	  while(j>=0&&tmp<num[j])  //注意判断条件为两个,j>=0对其进行边界限制。第二个为插入判断条件 
	  {
	    num[j+1] = num[j];//若不是合适位置,有序组元素向后移动 
		j--; 
	  }
	  num[j+1] = tmp;//找到合适位置,将元素插入。 
	}
  }
  
  int main() 
  {
  	int i = 0;
  	int num[8]={9,3,4,2,6,7,5,1};
  	InsertionSort(num,8); 
  	/*这个函数必须知道元素的个数,所以将元素个数传入。
	有心者可以在函数内部用sizeof求出元素个数 */
  	for(i=0;i<8;i++)
  	{
     	printf("%d ",num[i]);
	}
  	return 0;
  }

happysneaker.com



Java 实现:

import java.util.Arrays;
import java.util.Random;

public class InsertSort{

    private static void insertSort(Integer[] data) {    

        // i 是无序
        for (int i = 1; i < data.length; i++) {        
            int value = data[i];        
            int j = i - 1;        

            // 这个 for 循环也会把大于 value 移位到后面
            // 如果 data[j] < value, 此时 j+1 就是插入的位置
            // 因为有了移位,所以 j+1 的值已经移到后面了
            // 注意 3,5, 如果插入0,位置在 j+1 = 0 
            // 如果 3,5,插入4,位置在 j + 1 = 1 处
            // 如果 3,5,插入7,位置在 j+1 = i 处,保持不变
            for (; j >= 0; j--) {            
                if (data[j] > value) {
                    data[j + 1] = data[j];
                } else {                
                    break;
                }
            }
                    
            data[j + 1] = value;
        }
    }
                
        
                
    public static void main(String[] args) {
        Random r = new Random(System.currentTimeMillis());
        Integer[] data = new Integer[10];    
                
        for (int ii = 0; ii < 10; ii++) {        
            for (int i = 0; i < data.length; i++) {
                data[i] = r.nextInt(20);
            }
            System.out.println("------------------------");
            System.out.println(Arrays.toString(data));
            insertSort(data);
            System.out.println(Arrays.toString(data));
        }
    }
}


运行结果:

happysneaker.com


Unity那些事儿
请先登录后发表评论
  • 最新评论
  • 总共0条评论