简单选择排序.

Presentation on theme: "简单选择排序."— Presentation transcript:

1 简单选择排序

2 1 2 3 4 5 6 7 8 9 10 例题引入 49 38 65 97 49* 13 27 76 K=1 49>38

3 1 2 3 4 5 6 7 8 9 10 例题引入 49 38 65 97 49* 13 27 76 K=2 38<65

4 1 2 3 4 5 6 7 8 9 10 例题引入 49 38 65 97 49* 13 27 76 K=2 38<97

5 1 2 3 4 5 6 7 8 9 10 例题引入 49 38 65 97 49* 13 27 76 K=2 38<49*

6 1 2 3 4 5 6 7 8 9 10 例题引入 49 38 65 97 49* 13 27 76 K=2 38>13

7 1 2 3 4 5 6 7 8 9 10 例题引入 49 38 65 97 49* 13 27 76 K=6 38>13

8 1 2 3 4 5 6 7 8 9 10 例题引入 49 38 65 97 49* 13 27 76 K=6 13<27

9 1 2 3 4 5 6 7 8 9 10 例题引入 49 38 65 97 49* 13 27 76 K=6 13<76 第一趟排序结果：（13） *

10 以此类推： 第二趟排序结果：（13 27）65 97 49. 49 38 76 第三趟排序结果：（13 27 38）97 49
以此类推： 第二趟排序结果：（13 27） * 第三趟排序结果：（ ）97 49* 第四趟排序结果：（ *） 第五趟排序结果：（ * 49） 第六趟排序结果：（ * 49 65）97 76 第七趟排序结果：（ * ）97 例题引入

11 void SelectSort(SqList &L) { for (i=1; i<L.length; ++i) { //在L.r[i..L.length] 中选择key最小的记录 k=i; for( j=i+1;j<=L.length ; j++) if ( L.r[j].key <L.r[k].key) k=j; if(k!=i) {t=L.r[i]; L.r[i]=L.r[k]; L.r[k]=t;} } 简单选择排序的算法

12 时间复杂度方面，简单选择排序所需进行记录移动的次数较少。最好情况下，也就是完全有序的情况下，不需要移动记录，最坏情况下需要移动3(n-1)次，也就是需要交换n-1次。 但是，在关键字比较方面，无论记录序列的初始状态如何，比较次数均为： KCN==n(n-1)/2≈n2/2 所以简单选择排序的时间复杂度是O(n2)。 算法效率

13 算法效率 空间复杂度方面，只有在进行记录交换时需要一个辅助空间，所以复杂度为O(n)。

14 （1）是不稳定的排序方法。 （2）可用于链式存储结构，这个时候在比较过程中，就不再是保存当前最小关键字的下标了，而是指针。 （3）移动记录次数较少，每一记录占用空间较多时，此方法比直接插入排序方法快。
简单选择排序算法的特点