选择排序的思想也比较简单,就是从所有数据中选出最小的一个,排好第一位;然后再选一个次小的,排好第二位;依次类推下去…
形象一点说像极了平时大家钟爱的打牌运动,笔者斗地主时喜欢装逼,总是要先把牌取完,然后再一把揭开慢慢整理,大眼一扫,MD 竟然有个 3!!!没办法,拿出来放到最左边。再扫一眼 3 后面的牌,我擦,竟然还有个 4,抽出来,放到 3 后面吧… 直到排好王炸,哈哈,又赢了 5000 金豆(得意脸)
条件:
数据量较小
原理:
(1)选出最小的;
(2)选出次小的;
….
时间复杂度:
同样没什么好说的,n^2。
实现:
- public class ChoSort {
- /** * name: main*description:*return: void*/
- public static void main(String[] args) { // TODO Auto-generated method stub int[] a = { 1, 5, 8, 4, 7, 3, 0, 2, 9, 6, 11, 13, 12, 141, 14, 15, 17, 16, 18, 21, 20, 19, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 40, 39, 38, 37 }; choSort(a); print(a); } public static void print(int[] array) { for (int i = 0; i < array.length; i++) { System.out.print(array[i] + ", "); } System.out.println(); } /** 核心:min的赋值 */ public static void choSort(int[] array) { int min; for (int i = 0; i < array.length; i++) { min = i; for (int j = i + 1; j < array.length; j++) { if (array[j] < array[min]) { min = j; } } int temp = array[min]; array[min] = array[i]; array[i] = temp; } } }
上一篇冒泡排序中提到,冒泡排序看似很简单,却容易写变味,成了效率较低的选择排序,如下面示例的这样
- /** 交换次数和比较次数都是O(n2) */
- public static void badChoSort(int[] array) {
- for (int i = 0; i < array.length; i++) {
- for (int j = i + 1; j < array.length; j++) {
- if (array[i] > array[j]) {
- int temp = array[j];
- array[j] = array[i];
- array[i] = temp;
- }
- }
- }
- }
分析一下代码,choSort 的核心是最外面的循环确定最终的排序次位,内层的循环则通过比较剩余的元素与当前次位元素的大小,找出剩余最小的元素下标,交换之,则完成一个次位的排序。一个次位的排序过程中,它的比较次数虽然是 n-1,但是交换次数却是 1,牺牲了 O(1)的空间。而类似 badChoSort 的写法,一个次位的排序过程中,比较次数是 n-1,交换次数也是 n-1,虽然节省了空间,但得不偿失,尤其在数据量较大的情况下,更有可能影响效率。就爱阅读 www.92to.com 网友整理上传, 为您提供最全的知识大全, 期待您的分享,转载请注明出处。
来源: http://www.92to.com/bangong/2016/12-05/13909381.html