四、直接选择排序及交换二个数据的实现

十四、时间复杂度

视频: 舞动的排序算法 选择排序

1.直接选择排序和直接插入排序的区别和联系

联系：都将数据分为有序区和无序区

区别：直接插入排序是将无序区的第一个元素直接插入到有序区以形成一个更大的有序区

直接选择排序是从无序区选一个最小的元素直接放到有序区的最前

2.思路

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

1）初始时，数组全为无序区，令i=0

2）在无序区a[i…n-1]中选取一个最小的元素，将其与a[i]交换，交换之后a[0…i]就形成了一个有序区

3）i++重复知道i==n-1完成

4, 55, 8 , 67, 2 , 7

2 4

4 55

7 8

8 67

2 4 7 8 55 67

3.算法

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

2. {

3. int i, j, nMinIndex;

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

5. {

6. nMinIndex = i;

7. for (j = i + 1; j < n; j++)

8. {

9. if (a[j] < a[nMinIndex])

10. {

11. nMinIndex = j;

12. }

13. }

14. Swap(&a[i], &a[nMinIndex]);

15. traverse(a, n);

16. }

17. }