插入排序——C语言

admin2024-07-08  14

假设我们现在有一个数组,对它进行排序,插入排序的算法如同它的名字一样,就是将元素一个一个插入到合适的位置,那么,该如何做呢? 

插入排序——C语言,第1张

如果我们要从小到大进行排序的话,步骤如下:

1.对于第一个数来说,一个数无法考虑顺序问题,所以要从第二个数开始进行插入,进行排序。

2.排序的思想是:从头开始遍历,如果该数小于一个数,那么该数就插入到较大数的前面。

如图:

插入排序——C语言,第2张

我们现在让 i 充当要插入的数,j 表示遍历插入的数要比较的数,此时 i 指向的数大于 j 指向的数,所以位置不发生改变。

接着 i ++这时 i 指向的数值为1,小于 j 指向的数值,所以要将1插入到7的前面。说是插入,其实是先让7 8 向后覆盖,然后把1放到最开始7 的位置,循环覆盖的范围是j到i。

插入排序——C语言,第3张

覆盖过程如下: 

插入排序——C语言,第4张

完成插入操作之后,i 接着加加,接着让 j 从0 开始遍历比较,当j等于1的时候,要插入的元素小于遍历的元素,此时在完成插入操作,循环覆盖的范围是j到i。

插入排序——C语言,第5张

接下来我们就可以开始写代码了,我们可以先写出类似于这样的代码:

void InsertSort(int* array, int size) {
	for (int i = 1; i < size; i++) {————  i表示要插入的数  
		for (int j = 0; j < i; j++) {————  j表示要比较的数(插入的数之前的)
			取得要插入的数 num
			if (array[j] > 要插入的数) {
                将数插入到array[j]之前
			}
		}
	}
}

接着补全代码:

void InsertSort(int* array, int size) {
	for (int i = 1; i < size; i++) {
		for (int j = 0; j < i; j++) {
			int num = array[i];
			if (array[j] > num) {
				for (int k = i; k > j; k--) {
					array[k] = array[k-1];
				}
				array[j] = num;
			}
		}
	}
}

        或者我们可以换一种方式,刚才的代码是从头开始进行比较,我们也可以从后向前进行比较,如果遇到比插入的数大的值就接着向前进行寻找,同时进行覆盖,如果遇到比插入的数小的值就跳出循环,最后实现调换位置。

代码如下:

void InsertSort(int *array,int size) {
	for (int i = 0; i < size - 1; i++) {
        (因为要排序size-1次,所以循环size-1次)
		int end = i;
		int tmp = array[end + 1];
		while (end >= 0)
		{	
			if (tmp < array[end]) {
                (如果要插入的值比array[end]值小,第一次循环是前一个值,第二次循环是前两个值)
				array[end + 1] = array[end];
                (向后覆盖数值,相当于后移比插入值大的数)
				end--;
                (向前继续寻找)
			}
			else {
				break;
			}
		}
		array[end + 1] = tmp;
        (循环结束,把插入值插入到正确的位置,即比自己小的数的后面)
	}
}

这两种方式都可以完成对数的插入排序。

这就是文章的全部内容了,希望对你有所帮助,如有错误欢迎指出。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明原文出处。如若内容造成侵权/违法违规/事实不符,请联系SD编程学习网:675289112@qq.com进行投诉反馈,一经查实,立即删除!