简单选择排序.ppt

①在一组对象r[i]～r[n]中选择具有最小排序码的对象；②若它不是这组对象中的第一个对象,则将它与这组对象中的第一个对象对调;③在这组对象中去除这个具有最小排序码的对象。在剩下的对象r[i+1]～r[n]中重复执行第①、②步,直到剩余对象只有一个为止。简单选择排序是一种简单的排序方法,它的基本步骤是：简单选择排序(SelectSort)P277：算法10.921254925*16081234562125*i=1492516251608490825*4921i=2i=3081625*2521初始最小者08交换21,08最小者16交换25,16最小者21交换49,214925*12345625*i=52516084925*4921结果i=408162521最小者25*无交换最小者25无交换25211608各趟排序后的结果12345649160825*49210825*2521i=2时选择排序的过程ikj49250825*1621ikj492525*251625ikj1625展台设计编辑：cvdfbgnyhtt99345649250825*1621123456ikj2116k指示当前序列中最小者简单选择排序的排序码比较次数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)简单选择排序是一种不稳定的排序方法。