插入排序总结

插入排序（Insertion-Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
排序思路:
假设按照升序排序
1.从索引为1的元素开始向前比较, 一旦前面一个元素大于自己就让前面的元素先后移动
2.直到没有可比较元素或者前面的元素小于自己的时候, 就将自己插入到当前空出来的位置

1.原理

3 6 7 4 2 1 5
分为两段，一段已经排好顺序，一段还没有排序
[3 6 7] 4 2 1 5
从4开始插到前面已经排好序的位置中去
理论上是这样，但是在真正写代码的时候还需要其他来实现插入的操作
0 1 2 3
arr 3 6 7 4 …
i
key

key =4
while(arr[i-1]>key){
=>arr[i]=arr[i-1];
i–;
}
arr[i]=key;

3 6 7 4 2 1 5
3 6 7 已经排好序
对4进行操作
3 6 7 4 2 1 5
从后往前比
4和7比，4小于7
3 6 4 7   2 1 5先不管
对于6和4 6大于4
3 4 6 7
对于4和3来说，3小于4 因此不需要交换位置
3 4 6 7 2 1 5
下面对2进行操作
[3 4 6 7] 2 1 5
对于 7和2来说，7大于2
3 4 6 2 7       1 5先不管
下面判断6 和 2

2.代码

# include<stdio.h>
void insert(int arr[],int n){
	int key = arr[n];
	int i = n;
	while(arr[i-1]>key){
		arr[i] = arr[i-1];
		i--;
		if (i==0){
			break;
		}
	}
	arr[i] = key;
}
void insertionSort(int arr[],int n){
	int i;
	for(i=1;i<n;i++){
		insert(arr,i);
	}
}
int main(){
	int arr[] = {9,1,2,3,6,5,7,8,4};
	int i;
	insertionSort(arr,9);
	for(i=0;i<9;i++){
		printf("%d\n",arr[i]);
	}
}

#include <stdio.h>
#include <stdlib.h>

/* run this program using the console pauser or add your own getch, system("pause") or input loop */

int main()
{
    // 待排序数组
    int nums[5] = {3, 1, 2, 0, 3};
    // 0.计算待排序数组长度
    int len = sizeof(nums) / sizeof(nums[0]);

    //  1.从第一个元素开始依次取出所有用于比较元素
    for (int i = 1; i < len; i++)
    {
        // 2.取出用于比较元素
        int temp = nums[i];
        int j = i;
        while(j > 0){
            // 3.判断元素是否小于前一个元素
            if(temp < nums[j - 1]){
                // 4.让前一个元素向后移动一位
                nums[j] = nums[j - 1];
            }else{
                break;
            }
            j--;
        }
        // 5.将元素插入到空出来的位置
        nums[j] = temp;
        
    }
    for(int i =0;i<len;i++)
        {
        	printf("%d ",nums[i]);
		}
}

#include <stdio.h>
#include <stdlib.h>

/* run this program using the console pauser or add your own getch, system("pause") or input loop */

int main()
{
    // 待排序数组
    int nums[5] = {3, 1, 2, 0, 3};
    // 0.计算待排序数组长度
    int len = sizeof(nums) / sizeof(nums[0]);

    //  1.从第一个元素开始依次取出所有用于比较元素
    for (int i = 1; i < len; i++)
    {
        // 2.遍历取出前面元素进行比较
        for(int j = i; j > 0; j--)
        {
            // 3.如果前面一个元素大于当前元素,就交换位置
            if(nums[j-1] > nums[j]){
                int temp = nums[j];
                nums[j] = nums[j - 1];
                nums[j - 1] = temp;
            }else{
                break;
            }
        }
    }
    for(int i =0;i<len;i++)
        {
        	printf("%d ",nums[i]);
		}
}