要知道哪个效率高就要知道他们的排序比较方式有什么不同,我们先来比较一下! 例: 如要将数组:[12,14,26,5,8] 按升序排列成:[5,8,12,14,26]
选择排序:
第一趟:将第一个数与第二个数相比较;若第二个数较小,则第一个数与第二个数交换,否则不变;
再将第一个数与第三个数比较,若第三个数较小,则交换,否则不变;
依此类推,则第一趟排序时各数据所处位置应是:
初始:12,14,26,5,8
第一次比较后:12,14,26,5,8
(注:第一次比较后,因12<14,故不变)
第二次比较后:12,14,26,5,8
(注:第二次比较后,因12<26,故不变)
第三次比较后:5,14,26,12,8(注:第三次比较时,12是第一位数,与第四位数5相比较)
第四次比较后:5,14,26,12,8(注:第四次比较后,因8>5,故不变)
第二趟排序时,因首位数字5己是最小数,且排在第一位,就可以不再管它了,就只需对数组:[14,26,12,8] 进行排序,具体过程同上面一样。
冒泡排序:
首先将处于第一位置的数与处第二位置的数相比较,若第二位置的数较小,则交换,否则不变;此处,因14>12,故不变。
然后将第二位置的数与第三位置的数比较,若后者较小,则交换,否则不变;此例中,因14<26,故不变。
再将第三位置的数与第四位置的数比较,若后者小,则交换,否则不变;此例中,因5<26,故交换; 交换后,26为新的第四位置数。
依此类推,将第四位置数与第五位置数相比较,即完成了第一趟排序。
第一趟排序过程中各数据位置:
初始:12,14,26,5,8
第一次比较后:12,14,26,5,8
第二次比较后:12,14,26,5,8
第三次比较后:12,14,5,26,8
第四次比较后:12,14,5,8,26
第二趟排序与第一趟排序类似,只是所需排的数组是:[12,14,5,8] 因最后一个数字己经是最大,且排在最后,故不再管它。 通过上面的实例应该知道,选择排序是每一个都比较(绝对比较);而
冒泡法是相对的比较,它是相对之前的数比较;如果有一组排好序的数组 [1,2,3,4,5,6] 再用选择排序法和冒泡法,那肯定是冒泡法先执行完,因为冒泡法只要执行一趟(运用相对比较),而选择要执行五趟(用的是绝对比较);从这就可以看出冒泡法比选择排序法的效率要高!