目录
冒泡排序、选择排序、直接插入排序
冒泡排序
import java.util.Arrays;
/**
* @author dengqixing
* @date 2021/4/17
*/
public class BubbleSort {
public static void main(String[] args) {
// 1、定义无序数组
int[] arr = {89, 59, 44, 12, 58, 26, 94, 98, 21, 23};
// int[] arr = {12, 21, 23, 26, 44, 58, 59, 89, 94, 98};
// 2、输出无序数组
System.out.println(Arrays.toString(arr));
// 3、排序
// 外循环，至少比较数组长度减一，因为最后一个元素无需再进行比较
for (int i = 0; i < arr.length - 1; i++) {
// 默认序列是有序的
boolean flag = true;
// 内循环，由于每次比较都会有一个最大或最小的数被放在最边缘的位置，所以每次循环时都需要对应的减少比较的次数
for (int j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
arr[j] = arr[j] ^ arr[j + 1];
arr[j + 1] = arr[j] ^ arr[j + 1];
arr[j] = arr[j] ^ arr[j + 1];
// 如果第一次小循环进行过交换，说明序列不是有序的,否则说明是有序的
flag = false;
}
}
// 这么做如果数组已经是有序了，则无需继续进行比较，减少循环次数，增加效率
if (flag) {
break;
}
}
// 4、输出排序后的数组
System.out.println(Arrays.toString(arr));
}
}
选择排序
class SelectSort {
public static void main(String[] args) {
// 1、定义无序数组
int[] arr = {89, 59, 44, 12, 58, 26, 94, 98, 21, 23};
// 2、输出无序数组
System.out.println(Arrays.toString(arr));
// 3、排序
// 外循环，需要 n - 1的循环次数
for (int i = 0; i < arr.length - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[minIndex] > arr[j]) {
minIndex = j;
}
}
// 进行交换
if (minIndex != i) {
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
}
// 4、输出排序后的数组
System.out.println(Arrays.toString(arr));
}
}
选择排序与冒泡排序的注意事项
- 冒泡排序至多需要n-1趟循环，最少一趟循环；其中n为长度
- 选择排序一定需要n-1躺循环，一趟也不能少
- 冒泡排序中最多的操作就是比较和交换，一趟循环中可能发生多次交换；
- 选择排序中最多的操作就是比较，一趟比较结束后发现更小(或更大)的值才进行交换
- 所以更推荐使用冒泡。
小案例，使用选择排序完成对对象的排序
class SelectSort2 {
public static void main(String[] args) {
// 1、定义无序数组
Comparable[] arr = {new Person(14,"李四"),new Person(18,"李四"),new Person(16,"李四")};
// 2、输出无序数组
System.out.println(Arrays.toString(arr));
// 3、排序
selectSort(arr);
// 4、输出排序后的数组
System.out.println(Arrays.toString(arr));
}
private static void selectSort(Comparable[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[minIndex].compareTo(arr[j]) > 0) {
minIndex = j;
}
}
// 进行交换
if (minIndex != i) {
Comparable temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
}
}
}
class Person implements Comparable<Person> {
int age;
String name;
public Person(int age, String name) {
this.age = age;
this.name = name;
}
public int getAge() {
return age;
}
public void setAge(int age) {
this.age = age;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
@Override
public int compareTo(Person p) {
return Integer.compare(this.getAge(), p.getAge());
}
@Override
public String toString() {
return "Person{" +
"age=" + age +
", name='" + name + '\'' +
'}';
}
}
直接插入排序(插入排序)
public static void insertSort(int[] arr) {
// 默认第一个元素是有序序列，所以从1开始
for (int i = 1; i < arr.length; i++) {
// 临时变量存储当前需要插入的数据
int temp = arr[i];
// 存储有序序列的元素下标位置
int j = i - 1;
// 如果当前的元素小于需要比较的元素
while (j >= 0 && temp < arr[j]) {
// 将当前正在比较的元素放入其后面的位置
arr[j + 1] = arr[j];
// 继续往左进行数据比较
j--;
}
// 循环结束后，将其比较的元素放在最后比较的一个元素的后面
arr[j + 1] = temp;
}
}
快速排序（比较排序中效率最高的一种排序）
原理：
- 首先得到一个无序序列
- 随机选取其中一个数为基准数(一般默认为最左侧的第一个元素)
- 然后会有两个指针分别在当前需要比较的序列的最左侧和最右侧
- 先从最右侧开始往左移动比较，一旦碰到了大于或者相等于基准数的元素，则继续向左移动，直到指针所指向的元素小于基准数，就停下(还有一个条件，左边的索引必须小于右边的索引)
- 然后从最左侧开始向右移动比较，一旦碰到了小于或者相等于基准数的元素，则继续向右移动，直到指针所指向的元素大于基准数，就停下（左边的索引必须小于右边的索引）
- 如果左指针与右指针相等（也就是相遇了），则将其相遇位置的元素与基准数进行交换
- 最后再将基准数左边的序列再次进行快速排序
- 将基准数右边的序列再次进行快速排序
public static void main(String[] args) {
int[] arr = new int[100000000];
for (int i = 0; i < arr.length; i++) {
// 随机存入1到10万之间的数字
arr[i] = (int)(Math.random() * 100000)+1;
}
// 排序
long start = System.currentTimeMillis();
quickSort(arr, 0 , arr.length -1);
long end = System.currentTimeMillis();
//19357毫秒，排序1亿个数字的序列竟只用了19秒，
冒泡排序在10万数据时就已耗时15秒左右，快速排序在10万数据时耗时只有20-30毫秒
System.out.println("运行时间为 :" + (end - start));
}
public static void quickSort(int[] arr, int left, int right) {
// 如果左边索引比右边索引还要大，是不合法的，直接return结束方法
if (left > right) {
return;
}
// 获得基准数(默认选择最左边的数)与左右2个下标索引数
int base = arr[left];
int i = left;
int j = right;
// 当i和j不相遇的时候，才进行循环检索
while (i != j) {
// 从右边开始检索，如果找到了小于基准数的数，就停下
// 如果检索到比基准数大的或者相等的，就继续检索
while (arr[j] >= base && i < j) {
j--;
}
// 从左开始检索，如果找到了大于基准数的数，就停下
// 如果检索到比基准数小的或者相等的，就继续检索
while (arr[i] <= base && i < j) {
i++;
}
// 到这说明i和j都停下了，交换它们两的元素
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// 到这说明 i 和 j相遇了，就将相遇位置的值与基准数交换
arr[left] = arr[i];
arr[i] = base;
// 然后将排序后左边的序列再次进行排序
quickSort(arr, left , i -1);
// 将右边的序列再次进行排序
quickSort(arr, i + 1, right);
}
}
折半查找(使用时有限制，只能是排序好了的数组)
// 非递归二分查找
public static int binarySearch(int[] arr, int key) {
int low = 0;
int high = arr.length - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (arr[mid] == key) {
return mid;
} else if (key < arr[mid]) {
high = mid - 1;
} else if (key > arr[mid]) {
low = mid + 1;
}
}
return -1;
}
// 递归二分查找
public static int binarySearch2(int[] arr, int key) {
int low = 0;
int high = arr.length - 1;
int index = binarySearch(arr, key, low, high);
return index;
}
private static int binarySearch(int[] arr, int key, int low, int high) {
if (low > high) {
return -1;
}
// 计算中间索引
int mid = (low + high) / 2;
if (arr[mid] == key) {
return mid;
} else if (key < arr[mid]) {
return binarySearch(arr, key, low, mid - 1);
} else {
return binarySearch(arr, key, mid + 1, high);
}
}
补充一下递归的优点与缺点
- 优点：编码简单，适合处理相同业务逻辑的问题
- 缺点：占用内存空间多，每递归一次都会在栈空间中开辟新空间执行方法