什么是插入排序?
插入排序是指在待排序的元素中,假设前面n-1(其中n>=2)个数已经是排好顺序的,现将第n个数插到前面已经排好的序列中,然后找到合适自己的位置,使得插入第n个数的这个序列也是排好顺序的。 按照此法对所有元素进行插入,直到整个序列排为有序的过程,称为插入排序 。
代码实现
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 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68
| int main() { int arr[] = { 10,9,8,7,6,5,4,3,2,1 }; int sz = sizeof(arr) / sizeof(arr[0]); int i, j; int tmp; for (i = 1; i < 10; i++) { for (j = i; (j > 0) && (arr[j]<arr[j-1]); j--) { tmp = arr[j]; arr[j] = arr[j - 1]; arr[j - 1] = tmp; } printf("第%d轮:", i); printArr(arr,sz); }
return 0; }
int printArr(int arr[], int sz) { int i; for (i = 0; i < sz; i++) { printf("%d ", arr[i]); } printf("\n"); return 0; }
输出: 第1轮:9 10 8 7 6 5 4 3 2 1 第2轮:8 9 10 7 6 5 4 3 2 1 第3轮:7 8 9 10 6 5 4 3 2 1 第4轮:6 7 8 9 10 5 4 3 2 1 第5轮:5 6 7 8 9 10 4 3 2 1 第6轮:4 5 6 7 8 9 10 3 2 1 第7轮:3 4 5 6 7 8 9 10 2 1 第8轮:2 3 4 5 6 7 8 9 10 1 第9轮:1 2 3 4 5 6 7 8 9 10
int main() { int arr[] = { 5,2,4,6,1,3,7,9,8,10 }; int i, j, temp; for (i = 1; i < 10; i++) { j = i - 1; temp = arr[i]; while (temp < arr[j] && j >= 0) { arr[j + 1] = arr[j]; j--; } arr[j + 1] = temp; }
for (i = 0; i < 10; i++) { printf("%d ", arr[i]); }
return 0; }
|
写成函数
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
| int insertionSort(int arr[], int sz) { int i, j; int tmp; for (i = 1; i < 10; i++) { for (j = i; (j > 0) && (arr[j]<arr[j-1]); j--) { tmp = arr[j]; arr[j] = arr[j - 1]; arr[j - 1] = tmp; } } return 0; }
|