首页 > 代码库 > 排序-简单选择排序
排序-简单选择排序
- 思想:第i趟简单选择排序是指通过n-i次keyword的比較，从n-i+1个记录中选出keyword最小的记录，并和第i个记录进行交换。
共需进行i-1趟比較，直到全部记录排序完毕为止。
比如：进行第i趟选择时，从当前候选记录中选出keyword最小的k号记录，并和第i个记录进行交换。
- 基本实现代码
for (int i=0; i<nLen-1; i++) { for(int j=i+1; j<nLen; j++) { if(Compare(pData[i], pData[j])) { Swap(pData[i], pData[j]); } } }这样的实现是总是把当前最小的置于排序的位置,缺点是须要交换多次.int n = 0; for (int i=0; i<nLen-1; i++) { n = i; for(int j=i+1; j<nLen; j++) { if(Compare(pData[n], pData[j])) { n = j; } } Swap(pData[i], pData[n]); }针对上一个算法的缺点,做一点改进:记录当前最小的位置,之后做一次交换 - 測试结果
20265 5770 12311 31633 23346 5839 12909 6759 32618 20794 0 5770 20265 12311 31633 23346 5839 12909 6759 32618 20794 1 5770 5839 20265 31633 23346 12311 12909 6759 32618 20794 2 5770 5839 6759 31633 23346 20265 12909 12311 32618 20794 3 5770 5839 6759 12311 31633 23346 20265 12909 32618 20794 4 5770 5839 6759 12311 12909 31633 23346 20265 32618 20794 5 5770 5839 6759 12311 12909 20265 31633 23346 32618 20794 6 5770 5839 6759 12311 12909 20265 20794 31633 32618 23346 7 5770 5839 6759 12311 12909 20265 20794 23346 32618 31633 8 5770 5839 6759 12311 12909 20265 20794 23346 31633 32618
未改进的执行结果,排序不稳定10815 18874 18420 9071 2551 14632 23080 9881 16740 1370 0 1370 18874 18420 9071 2551 14632 23080 9881 16740 10815 1 1370 2551 18420 9071 18874 14632 23080 9881 16740 10815 2 1370 2551 9071 18420 18874 14632 23080 9881 16740 10815 3 1370 2551 9071 9881 18874 14632 23080 18420 16740 10815 4 1370 2551 9071 9881 10815 14632 23080 18420 16740 18874 5 1370 2551 9071 9881 10815 14632 23080 18420 16740 18874 6 1370 2551 9071 9881 10815 14632 16740 18420 23080 18874 7 1370 2551 9071 9881 10815 14632 16740 18420 23080 18874 8 1370 2551 9071 9881 10815 14632 16740 18420 18874 23080
改进的排序的执行结果,排序稳定效率有所提升 - 时间复杂度:两层循环，分别为n，所以整个算法的时间复杂度为O(n*n)
排序-简单选择排序
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。