title: 2022-06-28-冒泡排序&选择排序
date: 2022-06-28 23:19:00
tag: 算法
从小到大:假定第一个数是最小值,将当前这个数依次和剩下的值进行比较,若遇到比当前这个值小的,就交换位置。
冒泡排序代码
package com.leeue.learn.demo;
/**
* 冒泡排序
*
* @Date 2022/6/28 22:18
* @Author mac
*/
public class BubbleSort {
public static void main(String[] args) {
int[] sortList = {1, 3, 4, 2, 9, 1, 34, 5, 3, 7, 0, 3, 5, 9, 90, 32, 4, 5};
sort(sortList);
}
public static void sort(int[] nums) {
//1. 第一层 for 循环控制需要比较的次数,最后一次不用比较
for (int i = 0; i < nums.length - 1; i++) {
for (int j = i + 1; j < nums.length; j++) {
if (nums[i] > nums[j]) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
}
for (int i = 0; i < nums.length; i++) {
System.out.printf("" + nums[i] + " ");
}
}
}
算法复杂度
算法复杂度为 O(n2)
注意事项
- 第一层 for 循环是控制比较的次数,最后一次不用比较,前面都排序好了。最后一次也就不用再比较排序了。
- 假定第一个数是最小,第二层 for 循环从 最小的前面一个值开始进行比较
默认第一个数的下标是最小的。若第一个数的下标跟其他数比较,遇到了比其还小的数字,就记录最小下标,拿这个下标的值跟其他数比较
public class SelectSort {
public static void main(String[] args) {
int[] sortList = {1, 3, 21, 91, 11, 34, 5, 7, 0, 51, 9, 90, 32, 43, 51};
selectSort(sortList);
}
public static void selectSort(int[] nums) {
for (int i = 0; i < nums.length-1; i++) {
int minIndex = i;
for (int j = i + 1; j < nums.length; j++) {
if (nums[minIndex] > nums[j]) {
minIndex = j;
}
}
if (i != minIndex) {
int temp = nums[minIndex];
nums[minIndex] = nums[i];
nums[i] = temp;
}
}
for (int i = 0; i < nums.length; i++) {
System.out.printf("" + nums[i] + " ");
}
}
}
注意点
- 选择排序是一个不稳定的排序算法,有时候遇到比较规律的数,交换就会少很多。
- 特点是
记录下标最小值
- 第一层 for 循环也是次数,第二层 for 循环是跟
i + 1
个数进行比较