1、选择排序
给定数组arr,其长度为n。实现思路:
- 遍历数组,从0 ~ n - 1,找到最小的,找到后,和数组的第一个元素互换位置
- 继续新一轮遍历,从1 ~ n - 1,找到最小的,找到后,和数组的第二个元素互换位置
- 再来一轮遍历,从2 ~ n - 1,找到最小的,找到后,和数组的第三个元素互换位置
- ……
- 如此,遍历完数组,即可完成排序
核心思路:每次遍历,把剩下的里面最小的元素扔前面去,0到n-1的范围找最小的扔前面,再1到n-1的范围找最小的,以此类推。代码实现:
public class Sort {
/**
* 选择排序
*/
public static void selectSort(int[] arr) {
// 数组长度为1时,不用排序
if (null == arr || arr.length < 2) {
return;
}
for (int i = 0; i < arr.length; i++) {
// 最小值的索引,开始i=0
int minValueIndex = i;
for (int j = i + 1; j < arr.length; j++) {
// 如果i的下一个元素比i小,则覆盖最小值索引
minValueIndex = arr[j] < arr[minValueIndex] ? j : minValueIndex;
}
// 0 ~ n-1 的范围都比较完了,把最小值的和第一个元素互换
int temp = arr[i];
arr[i] = arr[minValueIndex];
arr[minValueIndex] = temp;
// 一轮循环结束,找到了第一小的元素,并放在了数组首位
// 接下来开下一轮循环,找第二小的元素,放在数组的第二位
}
}
}
2、冒泡排序
前面选择排序是,我找到最值后,手动给它放到数组首位。冒泡则是:第n个元素和第n+1个元素对比,交换,让大的那个放右边,接着n+1和n+2位置的元素对比,依旧大的放右边。如此,比较完一轮,就会让第一大的元素像一个气泡一样,一步步的走到了数组末尾的位置。再进行第二轮,第二大的元素也会像一个气泡一样,一步步的走到了数组倒数第二的位置。
代码实现:
public class Sort {
/**
* 冒泡排序
*/
public static void bubbleSort(int[] arr) {
// 数组长度为1时,不用排序
if (null == arr || arr.length < 2) {
return;
}
for (int end = arr.length - 1; end > 0; end--) {
// 设arr.length = n
// 外层出循环第一轮,end = n - 1, 先处理0 ~ n-1
// 外层循环第二轮,end = n - 2, 先处理0 ~ n-2
// 外层循环最后一轮,end = 1, 先处理0 ~ 1
for (int i = 0; i < end; i++) {
if (arr[i] > arr[i + 1]) {
int temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
}
}
}
}
}
3、插入排序
插入排序,正如这个名字,就像打牌一样,整牌时,比如现在最大的放在左边,那抽到一张新牌后,从右往左看,一个个比较,然后把新进来的牌插入到合适的位置。插入排序也是这个思路。也就是说,实现步骤是:
- 先保证0 ~ 0 号元素有序(即保证第一张牌有序)
- 再保证0 ~ 1号元素有序(即保证前两张牌有序)
- 再保证0 ~ 2号元素有序(即保证前三张牌有序),但前两张已经有序,此时只需处理第三张牌即可
- ……
- 保证0 ~ n - 1号元素有序,但前n - 2张已有序,此时只需处理最后一张牌,一个个比,把它插入到合适的位置即可
到这儿,想到一点,算法,即解决问题的步骤,把生活中怎么解决同样问题的行为,翻译成代码,就是答案。此外,解一道题,应该先举一个简单具体的例子,分析清楚后,再逐步扩大数据量来分析。
public class Sort {
/**
* 插入排序
*/
public static void insertSort(int[] arr) {
// 数组长度为1时,不用排序
if (null == arr || arr.length < 2) {
return;
}
// 初始end = 1,先保证0~1有序,后面end+1,就是保证0~2有序
// end控制末尾的边界
for (int end = 1; end < arr.length; end++) {
// end - 1 > 0,说明左边还有元素可以比较
// arr[end - 1] < arr[end]不满足的话,说明有序,也不用交换
int newNumIndex = end;
while (newNumIndex - 1 >= 0 && arr[newNumIndex - 1] < arr[newNumIndex]) {
int temp = arr[newNumIndex - 1];
arr[newNumIndex - 1] = arr[newNumIndex];
arr[newNumIndex] = temp;
// 交换后,和新的左边的数继续比,直到越界或者遇到比它大的数字,停止比较和交换
newNumIndex--;
}
}
}
}
优化下:
public class Sort {
/**
* 插入排序2
* 用for嵌套
*/
public static void insertSort2(int[] arr) {
if (null == arr || arr.length < 2) {
return;
}
// 初始end = 1,先保证0~1有序,后面end+1,就是保证0~2有序
// end控制末尾的边界
for (int end = 1; end < arr.length; end++) {
// pre为当前数的左侧方向的前一个数
for (int pre = end - 1; pre >= 0 && arr[pre] < arr[pre + 1]; pre--) {
int temp = arr[pre];
arr[pre] = arr[pre + 1];
arr[pre + 1] = temp;
}
}
}
}