简单选择排序(精品).ppt

《简单选择排序(精品).ppt》由会员分享，可在线阅读，更多相关《简单选择排序(精品).ppt（6页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、在在一一组组对对象象rirn中中选选择择具具有有最最小小排排序码的对象；序码的对象；若若它它不不是是这这组组对对象象中中的的第第一一个个对对象象,则则将将它与这组对象中的第一个对象对调它与这组对象中的第一个对象对调;在在这这组组对对象象中中去去除除这这个个具具有有最最小小排排序序码码的的对对象象。在在剩剩下下的的对对象象ri+1rn中中重重复复执执行行第第、步步,直直到到剩剩余余对对象象只只有有一一个为止。个为止。简单选择排序是一种简单的排序方法简单选择排序是一种简单的排序方法,它它的基本步骤是：的基本步骤是：简单选择排序简单选择排序(Select Sort)P277：算法：算法10.9 21

2、212525494925*25*161608081 2 3 4 5 6212125*25*i=1 14949252516162525161608084949080825*25*49492121i=2 2i=3 30808161625*25*25252121初始初始初始初始最小者最小者 0808交换交换交换交换21,0821,08最小者最小者 1616交换交换交换交换25,1625,16最小者最小者 2121交换交换交换交换49,2149,21494925*25*1 2 3 4 5 625*25*i=5 5252516160808494925*25*49492121结果结果i=4 4080816

3、1625252121最小者最小者 25*25*无交换无交换无交换无交换最小者最小者 2525无交换无交换无交换无交换2525212116160808各趟排序后的结果各趟排序后的结果1 2 3 4 5 649491616080825*25*49492121080825*25*25252121i=2时选择排序的过程时选择排序的过程i k j 49492525080825*25*16162121i k j 49 49 25 2525*25*25 2516162525i k j 16 2516 2549492525080825*25*161621211 2 3 4 5 6i k j 21 21 16

4、16k k 指示当前序列中最小者指示当前序列中最小者指示当前序列中最小者指示当前序列中最小者 简单选择排序的简单选择排序的排序码比较次数排序码比较次数 KCN 与对与对象的初始排列无关。设整个待排序对象序列象的初始排列无关。设整个待排序对象序列有有 n 个对象个对象,则第则第 i 趟选择具有最小排序趟选择具有最小排序码对象所需的比较次数码对象所需的比较次数总是总是 n-i-1 次次。总的排。总的排序码比较次数为序码比较次数为:KCN=(n-1)+(n-2)+2+1=n(n-1)/2n n对象的移动次数与对象序列的初始排列有对象的移动次数与对象序列的初始排列有关关。当这组对象的初始状态是按其排序码。当这组对象的初始状态是按其排序码从小到大有序的时候从小到大有序的时候,对象的移动次数对象的移动次数达达到最少，到最少，RMN=0。n n最坏情况是每一趟都要进行交换，最坏情况是每一趟都要进行交换，总的对总的对象移动次数象移动次数为为 RMN=3(n-1)。n n总的时间复杂度是：总的时间复杂度是：O(n2)n n简单选择排序是一种简单选择排序是一种不稳定不稳定的排序方法。的排序方法。