一, 直接插入排序
直接插入排序 (Straight Insertion Sort) 的基本思想是: 把 n 个待排序的元素看成为一个有序表和一个无序表. 开始时有序表中只包含 1 个元素, 无序表中包含有 n-1 个元素, 排序过程中每次从无序表中取出第一个元素, 将它插入到有序表中的适当位置, 使之成为新的有序表, 重复 n-1 次可完成排序过程.
- void insert_sort(int a[], int n)
- {
- int i, j, k;
- for (i = 1; i <n; i++)
- {
- // 为 a[i]在前面的 a[0...i-1]有序区间中找一个合适的位置
- for (j = i - 1; j>= 0; j--)
- if (a[j] <a[i])
- break;
- // 如找到了一个合适的位置
- if (j != i - 1)
- {
- // 将比 a[i]大的数据向后移
- int temp = a[i];
- for (k = i - 1; k> j; k--)
- a[k + 1] = a[k];
- // 将 a[i]放到正确位置上
- a[k + 1] = temp;
- }
- }
- }
c++ 实现代码:
- #include <iostream>
- using namespace std;
- void insertSort(int* a, int n)
- {
- int i, j, k;
- for (i = 1; i <n; i++)
- {
- // 为 a[i]在前面的 a[0...i-1]有序区间中找一个合适的位置
- for (j = i - 1; j>= 0; j--)
- if (a[j] <a[i])
- break;
- // 如找到了一个合适的位置
- if (j != i - 1)
- {
- // 将比 a[i]大的数据向后移
- int temp = a[i];
- for (k = i - 1; k> j; k--)
- a[k + 1] = a[k];
- // 将 a[i]放到正确位置上
- a[k + 1] = temp;
- }
- }
- }
- int main()
- {
- int i;
- int a[] = {20,40,30,10,60,50};
- int ilen = (sizeof(a)) / (sizeof(a[0]));
- cout << "before sort:";
- for (i=0; i<ilen; i++)
- cout << a[i] << " ";
- cout << endl;
- insertSort(a, ilen);
- cout << "after sort:";
- for (i=0; i<ilen; i++)
- cout << a[i] << " ";
- cout << endl;
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3361071.html