核心思想:若有N个数从小到大排序,需进行N-1轮比较,第一轮每相邻的两个数据进行比较N-1次,最终挑选出最大的数,放到这一轮的最后位置;第二轮比较N-1-i次,挑选出这一轮最大的数,放入这一轮的最后位置;依此类推,每一轮都挑选出最大的数,故称之为冒泡排序。
第一个for循环决定循环的次数,因为要比较N-1轮,所以第一个for循环的终止条件是i<N-1;第二个for循环决定每一轮要比较的次数,因为每一轮都要选出一个最大的数,所以每一轮的比较次数都要比上一轮少一次,即for循环终止条件为j<N-1-i;
核心思想:若有N个数从小到大排序,需进行N-1轮比较,每一轮比较都找出这一轮最小值的下标,然后将这个最小值和这一轮开始假定的最小值进行交换。
第一个for循环决定要循环的次数,即要循环N-1轮;第二个for循环决定每一轮需要比较的次数,因为每一轮都会选择出一个最小值,所以每一轮的比较次数都会递减,即每一轮都是从i+1处开始比较到最后。需要注意的是内for循环每一次比较仅仅交换数组下标,只有当这一轮比较完毕,才进行一次数据交换。
冒泡排序和选择排序时间复杂度都是O(n^2),但是选择排序每循环一轮只进行一次数据交换,而冒泡排序每一轮最多需要进行N-i-1次数据交换。