插入排序
插入排序的代碼實現(xiàn)雖然沒有冒泡排序和選擇排序那么簡單粗暴杜顺，但它的原理應該是最容易理解的了，因為只要打過撲克牌的人都應該能夠秒懂躬络。插入排序是一種最簡單直觀的排序算法，它的工作原理是通過構建有序序列提茁，對于未排序數(shù)據(jù)馁菜，在已排序序列中從后向前掃描，找到相應位置并插入丹弱。
插入排序和冒泡排序一樣铲咨，也有一種優(yōu)化算法纤勒，叫做拆半插入隆檀。
1. 算法步驟
- 將第一待排序序列第一個元素看做一個有序序列，把第二個元素到最后一個元素當成是未排序序列泉坐。
- 從頭到尾依次掃描未排序序列裳仆，將掃描到的每個元素插入有序序列的適當位置。（如果待插入的元素與有序序列中的某個元素相等纯丸，則將待插入元素插入到相等元素的后面静袖。）
insertionSort.gif
2.代碼
#include <stdio.h>
void
swap(int *a, int *b)
{
int temp = *a;
*a = *b;
*b = temp;
}
void
insertion_sort(int arr[], int len)
{
int i, j, key;
for (i = 1; i < len; i++) {
key = arr[i];
j = i - 1;
while ((j >= 0) && (arr[j] > key)) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
int
main()
{
int arr[] = {22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70};
int len = (int) sizeof(arr) / sizeof(*arr);
insertion_sort(arr, len);
int i;
for (i = 0; i < len; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
轉載于菜鳥教程
2020.10.19 14:50 深圳
