Insert Sort直接插入排序
思想
- 每一轮都有一个元素在最终的位置
- 优化:
- 直观解释:插入排序
代码
#include "stdio.h"
void insert_sort(int* nums, int n) {
int i, j, tmp;
for (i = 0; i < n; i++) {
for (j = i+1; j >= 0; j--) {
if (nums[j] < nums[j-1]) {
tmp = nums[j];
nums[j] = nums[j-1];
nums[j-1] = tmp;
} else {
break;
}
}
}
}
int main() {
int nums[] = {3,2,5,1,17,4,10,13};
int n = 8, i;
insert_sort(nums, n);
for (i = 0; i < n; i++) {
printf("%d ", nums[i]);
}
return 0;
}
时间复杂度
||时间复杂度|趟|比较次数| |—-|—-|—-|—-| |最优时间复杂度|O()|1|n-1 |最坏时间复杂度|O(n^2)|n-1|n*(n-1)/2 |平均时间复杂度|O(n^2)||
稳定性
插入排序是一个稳定的排序方法