插入排序的基本原理

插入排序就是是对于一对原本有顺序的数组，将没有顺序的数组插入到有序的数组里面去。

这里呢，我们默认将要排序的数组靠前的数是有序的【就认为第一个数所组成的是有序的】

这里就是只有一个数，然后将后面的数和前面的数进行比较，如果比前面的数小，就和前面的数进行交换

这个有点像倒着的冒泡排序

就是第一个数字有序，然后从第二个数字开始和前面比较

单个数组的例子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <stdio.h>

void exchange(int a[], int i, int j)
//a是要交换的数组，i和j是要进行交换的位置
{
	int temp = a[i];
	a[i] = a[j];
	a[j] = temp;
}

void print(int a[], int sz) {
	for (int i = 0; i < sz; i++) {
		printf("%d", a[i]);
	}
}

int main() {
	int a[] = { 1,5,3,6,9,8,7,2,4 };//9个数

	for (int i = 1; i < sizeof(a) / sizeof(a[0]); i++) {
		for (int j = i; j > 0; j--) {//这里的j--很细节。因为如果下面的进行了一次交换后，你还需要将交换后的数据再一次和前面的数据进行比较，这个时候进行了j--。则原本的j-1，并且[j-1]相当于原来的j-2.
			if (a[j] < a[j - 1]) {
				exchange(a, j, j - 1);
			}
		}
	}
	int sz = sizeof(a) / sizeof(a[0]);
	print(a, sz);
}

偷一张图：

img

俩个数组的例子

原理是：

第一个有序的数组不变。

通过length来选取第一个数组中的元素，然后将无需数组的元素一个一个的放入有序数组后面，然后重新排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <stdio.h>

void insertionSort(int arr[], int n) {
    int i, key, j;
    
    for (i = 1; i < n; i++) {
        key = arr[i];
        j = i - 1;
        
        // 将arr[0...i-1]中大于key的元素向后移动
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        
        arr[j + 1] = key;
    }
}

int main() {
    int sortedArr[] = {2, 4, 6, 8, 10};  // 有序数组
    int unsortedArr[] = {9, 7, 5, 3, 1};  // 无序数组
    int sortedLength = sizeof(sortedArr) / sizeof(sortedArr[0]);//有序数组原本的大小
    int unsortedLength = sizeof(unsortedArr) / sizeof(unsortedArr[0]);
    
    // 将无序数组的元素插入到有序数组中
    for (int i = 0; i < unsortedLength; i++) {
        sortedArr[] = unsortedArr[i];
        sortedLength++;//通过这句话来扩大sortedArr数组，有有点点溢出的感觉
        insertionSort(sortedArr, sortedLength);  // 插入排序
    }//这里是插入一次排序一次。为什么不插完后再排序呢？
   
    
    printf("排序后的数组：");
    for (int i = 0; i < sortedLength; i++) {
        printf("%d ", sortedArr[i]);
    }
    
    return 0;
}