插入排序(C实现)

偏执的太偏执、 2024-04-17 05:59 56阅读 0赞

# 插入排序 #

> 如果有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序，这个时候就要用到一种新的排序方法——插入排序法 , 插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，插入算法把要排序的[数组][Link 1]分成两部分：第一部分包含了这个数组的所有元素，但将最后一个元素除外（让数组多一个空间才有插入的位置），而第二部分就只包含这一个元素（即待插入元素）。在第一部分排序完成后，再将这个最后元素插入到已排好序的第一部分中。
> 
> 插入排序的基本思想是：每步将一个待排序的记录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。

演示如下:

![2019082516245399.gif][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDcxMDY4_size_16_color_FFFFFF_t_70][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDcxMDY4_size_16_color_FFFFFF_t_70 1][]![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDcxMDY4_size_16_color_FFFFFF_t_70 2][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDcxMDY4_size_16_color_FFFFFF_t_70 3][]

**......**直到排序结束得到有序数列![20190825161357123.jpg][]

## 插入排序的特点 ##

> 稳定性 : 稳定
> 
> 时间复杂度 : O(N^2)
> 
> 空间复杂度 : O(N\*logN)
> 
> 数组越有序插入排序越快, 数组规模较小时插排最优

代码实现

#include<stdio.h>
    #include<stdlib.h>
    #include<time.h>
    #define N 100
    void InsertSort(int* src, int size) {
    	int tmp, j;
    	for (int i = 1; i < size; ++i) {
    		tmp = src[i];
    		for (j = i; j > 0 && src[j - 1] > tmp; --j) { 
    			src[j] = src[j - 1];
    		}
    		src[j] = tmp;
    	}
    }
    void PrintArray(int* src, int size) {
    	for (int i = 0; i < size; ++i) {
    		printf("%d ", src[i]);
    	}
    	putchar('\n');
    }
    int main() {
    	srand((unsigned int)time(0));
    	int src[N];
    	for (int i = 0; i < N; ++i) {
    		src[i] = rand() % N + 1;
    	}
    	//printf("排序前:\n");
    	//PrintArray(src, N);
    	InsertSort(src, N);
    	printf("排序后:\n");
    	PrintArray(src, N);
    	system("pause");
    	return 0;
    }

[Link 1]: https://baike.baidu.com/item/%E6%95%B0%E7%BB%84/3794097
[2019082516245399.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/452bd185223d45108f44fa9057614cce.gif
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDcxMDY4_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/648268a39e8e4c82adae3251ae1042bb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDcxMDY4_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/2019082516131820.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDcxMDY4,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDcxMDY4_size_16_color_FFFFFF_t_70 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/e8b79b7fcd6b4a6a85eb037d65e155d0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDcxMDY4_size_16_color_FFFFFF_t_70 3]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/498f9b2e95044a7eaea9e48e29bb69f5.png
[20190825161357123.jpg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/0e757b4794234ea39598e351b2eb6c5a.jpg