排序（sort）：就是将无序的数据按照特定的规则排成有序数据（升序、降序）。
这篇文章我们来了解一下Java中常见的三种排序方式，即冒泡排序、二分查找、插入排序。
既然要排序，那么就要考虑时间复杂度和空间复杂度这两个因素，我们可以在System.currentTimeMillis()里面查看。
一、冒泡排序
1.冒泡排序思路
冒泡排序就像烧开的水一样，里面大的泡泡往上浮。那么要进行冒泡排序就要从前往后遍历整个数组的元素，即从第一个元素开始遍历，将第一个元素和下一个元素进行比较，如果第一个元素大于下一个元素，则和下一个元素交换位置，继续和下一个元素进行比较，直至小于下一个元素，从而进行循环。总的来说，就是将一个乱序的数组排成一个升序的数组。
2.冒泡排序的图解（大数上浮法）
3.冒泡排序的具体分析
a = [2,98,-20,57,5,-7,88]
原顺序：2 , 98 , -20 , 57 , 5 , -7 , 88
第一次：2 , -20 , 57 , 5 , -7 , 88 , 98
第二次：-20 , 2 , 5 , -7 , 57 , 88 , 98
第三次：-20 , 2 , -7 , 5 , 57 , 88 , 98
第四次：-20 , -7 , 2 , 5 , 57 , 88 , 98
4.冒泡排序的代码示例
package com.simple.ex.day09;
public class Sort01 {
public static void main(String[] args) {
int[] a = {2,98,-20,57,5,-7,88};
System.out.println("排序前：");
for (int i : a) {
System.out.print(i + ", ");
}
bubbleSort(a);
System.out.println("\n排序后：") ;
for (int i : a) {
System.out.print(i + ",");
}
}
public static void bubbleSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
// 开始每一次两两比较
for (int j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr, j, j + 1);
}
}
}
}
private static void swap(int[] arr, int i, int j) {
arr[j] = arr[j] ^ arr[i];
arr[i] = arr[j] ^ arr[i];
arr[j] = arr[j] ^ arr[i];
}
}
程序运行结果如下：
/***
* 排序前：
* 2, 98, -20, 57, 5, -7, 88,
* 排序后：
* -20, -7, 2, 5, 57, 88, 98,
*/
二、选择排序
1.选择排序的思路
选择排序即在一个乱序数组中，假设第一个元素是最小值，将第一个元素和之后的元素进行比较，直至找到真正的最小值，交换这两个元素的位置即可。
2.选择排序的图解
3.选择排序的具体分析
a = [2,98,-20,57,5,-7,88]
原顺序：2 , 98 , -20 , 57 , 5 , -7 , 88
第一次：-20 , 98 , 2 , 57 , 5 , -7 , 88
第二次：-20 , -7 , 2 , 57 , 5 , 98 , 88
第三次：-20 , -7 , 2 , 57 , 5 , 98 , 88 //和第二次一样，排序了，但未找到真正的最小值
第四次：-20 , -7 , 2 , 5 , 57 , 98 , 88
第五次：-20 , -7 , 2 , 5 , 57 , 98 , 88 //和第四次一样，排序了，但未找到真正的最小值
第六次：-20 , -7 , 2 , 5 , 57 , 88 , 98
4.选择排序的代码示例
package com.simple.ex.day09;
public class Sort02 {
public static void main(String[] args) {
int[] a = {2, 98, -20, 57, 5, -7, 88};
System.out.println("排序前：");
for (int i : a) {
System.out.print(i + ", ");
}
selectSort(a);
System.out.println("\n排序后：");
for (int i : a) {
System.out.print(i + ", ");
}
}
public static void selectSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
int min = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[min]) {
// j对应的下标才是最小值
min = j;
}
}
// 假设失败，真正的最小值是min
if (min != i) {
swap(arr, min, i);
}
}
}
private static void swap(int[] arr, int i, int j) {
arr[j] = arr[j] ^ arr[i];
arr[i] = arr[j] ^ arr[i];
arr[j] = arr[j] ^ arr[i];
}
}
程序运行结果如下：
/***
* 排序前：
* 2, 98, -20, 57, 5, -7, 88,
* 排序后：
* -20, -7, 2, 5, 57, 88, 98,
*/
三、插入排序
1.插入排序的思路
插入排序即把第一个元素看作有序数组，从第二个元素开始依次插入到这个有序数组中，插入时这个数组必须保持有序。
2.插入排序的图解
3.插入排序的具体分析
a = [2,98,-20,57,5,-7,88]
原顺序：2 , 98 , -20 , 57 , 5 , -7 , 88
第一次：2 ， 98 ， -20 ， 57 ， 5 ， -7 ， 88
第二次：-20 ， 2 ， 98 ， 57 ， 5 ， -7 ， 88
第三次：-20 ， 2 ， 57 ， 98 ， 5 ， -7 ， 88
第四次：-20 ， 2 ， 5 ， 57 ， 98 ， -7 ， 88
第五次：-20 ， -7 ， 2 ， 5 ， 57 ， 98 ， 88
第六次：-20 ， -7 ， 2 ， 5 ， 57 ， 88 ， 98
4.插入排序的代码示例
package com.simple.ex.day09;
public class Sort03 {
public static void main(String[] args) {
int[] a = {2,98,-20,57,5,-7,88};
System.out.println("排序前：");
for (int i : a) {
System.out.print(i + ", ");
}
insertSort(a);
System.out.println("\n排序后：") ;
for (int i : a) {
System.out.print(i + ",");
}
}
public static void insertSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
// 取下一个元素，倒着插入，保证插入时数组一直有序
for (int j = i + 1; j > 0; j--) {
if (arr[j] < arr[j - 1]) {
swap(arr, j, j - 1);
}
}
}
}
private static void swap(int[] arr, int i, int j) {
arr[j] = arr[j] ^ arr[i];
arr[i] = arr[j] ^ arr[i];
arr[j] = arr[j] ^ arr[i];
}
}
程序运行结果如下：
/***
* 排序前：
* 2, 98, -20, 57, 5, -7, 88,
* 排序后：
* -20, -7, 2, 5, 57, 88, 98,
*/