简单选择排序ppt课件.ppt

在一组对象rirn中选择具有最小排序码的对象；若它不是这组对象中的第一个对象, 则将它与这组对象中的第一个对象对调; 在这组对象中去除这个具有最小排序码的对象。在剩下的对象ri+1rn中重复执行第、步, 直到剩余对象只有一个为止。,简单选择排序是一种简单的排序方法, 它的基本步骤是：,简单选择排序 (Select Sort),P277：算法10.9,21,25,49,25*,16,08,1 2 3 4 5 6,21,25*,i = 1,49,25,16,25,16,08,49,08,25*,49,21,i = 2,i = 3,08,16,25*,25,21,初始,最小者 08交换21,08,最小者 16交换25,16,最小者 21交换49,21,49,25*,1 2 3 4 5 6,25*,i = 5,25,16,08,49,25*,49,21,结果,i = 4,08,16,25,21,最小者 25*无交换,最小者 25无交换,25,21,16,08,各趟排序后的结果,1 2 3 4 5 6,49,16,08,25*,49,21,08,25*,25,21,i =2时选择排序的过程,i k j,49,25,08,25*,16,21,i k j,49 25,25* 25,16,25,i k j,16 25,展台设计 http:/,编辑：cvdfbgnyhtt993456,49,25,08,25*,16,21,1 2 3 4 5 6,i k j,21 16,k 指示当前序列中最小者,简单选择排序的排序码比较次数 KCN 与对象的初始排列无关。设整个待排序对象序列有 n 个对象, 则第 i 趟选择具有最小排序码对象所需的比较次数总是 n-i-1 次。总的排序码比较次数为: KCN=(n-1) + (n-2) + 2 + 1 =n(n-1)/2,对象的移动次数与对象序列的初始排列有关。当这组对象的初始状态是按其排序码从小到大有序的时候, 对象的移动次数达到最少，RMN = 0。最坏情况是每一趟都要进行交换，总的对象移动次数为 RMN = 3(n-1)。总的时间复杂度是：O(n2)简单选择排序是一种不稳定的排序方法。,