二、直接插入排序的三种实现

---

 

---

[舞动的排序算法
插入排序]{.ul}

1.思路

每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子序列中的适当位置，知道全部记录插入完成为止

设数组为a[0…n-1]

1)初始时，a[0]自成1个有序区，无序区为a[1…n-1]。令i=1

2)将a[i]并入当前的有序区a[0…i-1]中形成a[0…i]的有序区间

3)i++并重复第二步直到i==n-1，排序完成

第一种实现方法

1. void InsertSort1(int a[], int n)

2. {

3. int i, j, k;

4. for (i = 1; i < n; i++)

5. {

6. //为a[i]在前面的a[0…i-1]有序区间中找一个合适的位置

7. for (j = i - 1; j >= 0; j–)

8. {

9. //查到比前面数比a[i]小的那个位置就跳出

10. if (a[j] < a[i])

11. break;

12. }

13. //如果这个位置不为前面i-1个数的最后一位，则执行下列函数

14. if (j != i - 1)

15. {

16. int temp = a[i];

17. //将数往后推动

18. for (k = i - 1; k > j; k–)

19. {

20. a[k + 1] = a[k];

21. }

22. //把那个数插入到该有的位置

23. a[k + 1] = temp;

24. }

25. }

26. }

 

第二种实现方法

1. void InsertSort2(int a[], int n)

2. {

3. int i, j;

4. for (i = 1; i < n; i++)

5. {

6. //判断前面一个数是否大于后面的数

7. if (a[i] < a[i - 1])

8. {

9. //将后面这个数赋给临时变量

10. int temp = a[i];

11. //判断i前面的数是否大于临时变量,则前面的值后移

12. for (j = i - 1; j >= 0 && a[j] > temp; j–)

13. {

14. a[j + 1] = a[j];

15. }

16. //到了当前位置之后把临时变量赋给它

17. a[j + 1] = temp;

18. }

19. }

20. }