当前位置: 首页 > 网站开发 > 正文

简单选择排序

1 星2 星3 星4 星5 星 (2 次投票, 评分: 5.00, 总分: 5)
Loading ... Loading ...
baidu_share

简单选择排序的基本思想:第i趟简单选择排序是指通过n-i次关键字的比较,从n-i+1个记录中选出关键字最小的记录,并和第i个记录进行交换。共需进行i-1趟比较,直到所有记录排序完成为止。例如:进行第i趟选择时,从当前候选记录中选出关键字最小的k号记录,并和第i个记录进行交换。
实现代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void SelectSort(int array[] , int length)    // 简单选择排序  
{  
    int i , j , k;  
 
    for(i = 0 ; i < length-1 ; ++i)  
    {  
        k = i;  
        for(j = i + 1 ; j < length ; ++j)      // 从后面选择一个最小的记录  
        {  
            if(array[j] < array[k])  
                k = j;  
        }  
        if(k != i)       // 与第i个记录交换  
            swap(array[i] , array[k]);  
    }  
}

(1)关键字比较次数
 无论文件初始状态如何,在第i趟排序中选出最小关键字的记录,需做n-i次比较,因此,总的比较次数为:
n(n-1)/2=0(n2)

(2)记录的移动次数
 当初始文件为正序时,移动次数为0
 文件初态为反序时,每趟排序均要执行交换操作,总的移动次数取最大值3(n-1)。
 直接选择排序的平均时间复杂度为O(n2)。

(3)直接选择排序是一个就地排序

(4)稳定性分析
 直接选择排序是不稳定的。

【例】反例[2,2,1]

本文固定链接: http://www.chepoo.com/simple-selection-sort.html | IT技术精华网

【上一篇】
【下一篇】

简单选择排序:等您坐沙发呢!

发表评论