资源描述
选择排序是排序算法的一种,这里以从小到大排序为例进行讲解基本思想及举例说明简单选择排序(从小到大)的基本思想是,首先,选出最小的数,放在第一个位置;然后,选出第二小的数,放在第二个位置;以此类推,直到所有的数从小到大排序。在实现上,我们通常是先确定第i小的数所在的位置,然后,将其与第i个数进行交换。下面,以对3241进行选择排序说明排序过程,使用min_index记录当前最小的数所在的位置。第1轮排序过程(寻找第1小的数所在的位置)3241(最初,min_index=1)3241(32,所以min_index=2)3241(21,所以min_index=4,这时候确定了第1小的数在位置4)1243(第1轮结果,将3和1交换,也就是位置1和位置4交换)第2轮排序过程(寻找第2小的数所在的位置)1243(第1轮结果,min_index=2,只需要从位置2开始寻找)1243(42,所以min_index=2)1243(32,所以min_index=2)1243(第2轮结果,因为min_index位置刚好在第2个位置,无需交换)第3轮排序过程(寻找第3小的数所在的位置)1243(第2轮结果,min_index=3,只需要从位置2开始寻找)1243(43,所以min_index=4)1234(第3轮结果,将3和4交换,也就是位置4和位置3交换)至此,排序完毕。总结及实现选择排序对大小为N的无序数组RN进行排序,进行N-1轮选择过程。第i轮选取第i小的数,并将其放在第i个位置上。当第N-1次完成时,第N小(也就是最大)的数自然在最后的位置上。下面给岀选择排序的C语言实现。1. #include2. #include3. #include4. usingnamespacestd;5.6.7. voidselect_sort(inta,int&n);/采用C+中的引用操作;8.8. /选择排序实现9. voidselect_sort(inta,int&n)/n为数组a的元素个数10. 11. /进行N-1轮选择12. for(inti=1-1;i=i;j-)17. 18. if(ajamin)19. 20. min=j;21. 22. 24.23. /将第i小的数,放在第i个位置;如果刚好,就不用交换24. if(i!=min)25. 26. inttemp=ai;27. ai=amin;28. amin=temp;29. 30. 31. 34.35.32. intmain()33. 34. intnum=89,38,11,78,96,44,19,25;35. intN=sizeof(num)/sizeof(num0);/计算数组中元素的个数40.36. select_sort(num,N);42.37. for(inti=0;iN;i+)38. coutnumiendl;45.39. system(pause);40. return0;48.注意:选择排序是一种不稳定的排序算法,可能会打乱两个相同数字的原有顺序。例如,序列58529,按照从小到大排序,第一轮会将第1个数字5会和2交换,那么原序列中2个5的相对前后顺序就被破坏了,所以选择排序是一种不稳定的排序算法。
展开阅读全文