数组排序中,冒泡跟选择往往傻傻分不清楚,这次将详细了解这两种排序方法。
冒泡排序:每次比较的都是相邻间的两个数,一旦位置不对就交换位置(记住:是每次,所以时间复杂度高,效率慢,但也最稳定)。
选择排序:每次选出一个最小(大)的数,将最小(大)的数与第一个数进行位置交换,然后在剩下的数中再次找出最小(大)的数与第二个数进行位置交换,直至循环到倒数第二个数与最后一个数为止(因为每次循环只取最小(大)的一个数进行交换,所以效率比较高,而至于为什么说是不稳定的排序,下面接着说)。
排序稳定性的定义:假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中,r[i]=r[j],且r[i]在r[j]之前,而在排序后的序列中,r[i]仍在r[j]之前,则称这种排序算法是稳定的;否则称为不稳定的。
之所以说选择排序是不稳定的,正是因为排序前后,相对位置发生了变化。下边举个栗子:
相信大家看到这里就会去对比冒泡排序,这里博主就直接上图了,这里感叹一下,为了画图,博主真是殚精竭力啊~
好了,这里解释清了排序的稳定性,下面直接上代码
/***
*选择排序
*/
for(int i=0;i<arr.length-1;i++){ //这里i-1的原因是循环到最后一个就不要再与最后一个进行比较
int min = i; //假设最小的值为第一个元素
/**
*内循环控制每轮比较的次数
*/
for(int j=i+1;j<arr.length;j++){ //这里j+1的原因同上,第一个元素就不要与自己相比
if(arr[j] < arr[min]){ //获得该循环中最小的数的索引
min = j;
}
}
//找到最小值后进行元素交换
if(min != i){
int temp = arr[i];
arr[i] = arr[min];
arr[min] = temp;
}
}
/***
*冒泡排序
*/
for(int i=0;i<arr.length-1;i++){
for(int j=0;j<arr.length-1-i;j++){ //这里-1-i是为了排除后面已排完序的值,已经排完序的值就不要在比较了
if(arr[j] > arr[j+1]){
int temp = arr[i];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
最后,按照国际惯例总结一下:
- 冒泡排序是比较相邻位置的两个数,而选择排序是按顺序比较,找最大值或者最小值
- 冒泡排序每一轮比较后,位置不对都需要换位置,选择排序每一轮比较都只需要换一次位置
- 冒泡排序是通过数去找位置,选择排序是给定位置去找数
部分文章引用:
直接选择排序是不稳定的,以及怎样将它变成稳定的排序。(https://blog.csdn.net/yishengguoke/article/details/87518054)