排序：排序也称排序算法，是将一组数据，按指定的顺序进行排序的过程。
排序的分类：1）内部排序：指将需要处理的所有数据加载到内部存储器中进行排序； 2）外部排序：由于数据量过大，无法全部加载到内存中，需借助外部存储进行排序。
常见的排序算法有如下：
冒泡排序
基本思想：通过对待排序序列从前向后（从下标较小的元素开始），依次比较相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从前移向后部，就像水底的气泡一样逐渐上冒。
优化思想：因为在排序的过程中，各元素不断接近自己的位置，如果一趟比较下来没有进行交换，就说明序列有序。因此要在排序过程中设置一个 flag 判断元素是否进行过交换，从而减少不必要的比较。（可以在写好冒泡排序后再进行优化）
代码实现：
package sort;
public class BubbleSort {
public static void main(String[] args) {
int[] arr = { 3,9,-1,10,-2 };
print(arr);
//冒泡排序时间复杂度 O(n^2)
for (int i = 0; i < arr.length-1; i++) {
System.out.printf("第 %d 趟排序：n", i+1);
print(arr);
for (int j = 0; j < arr.length-1-i; j++) {
if (arr[j] > arr[j+1]){
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
print(arr);
}
}
}
}
public static void print(int[] nums){
for (int i = 0; i < nums.length; i++) {
System.out.print(nums[i] + " ");
}
System.out.println();
}
}
代码优化：
package sort;
public class BubbleSort {
public static void main(String[] args) {
int[] arr = { 3,9,11,15,20 };
print(arr);
//冒泡排序时间复杂度 O(n^2)
for (int i = 0; i < arr.length-1; i++) {
boolean flag = false;//标志数组内是否发生交换
System.out.printf("第 %d 趟排序：n", i+1);
print(arr);
for (int j = 0; j < arr.length-1-i; j++) {
if (arr[j] > arr[j+1]){
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
flag = true;//发生交换
print(arr);
}
}
if (!flag)
break;
}
}
public static void print(int[] nums){
for (int i = 0; i < nums.length; i++) {
System.out.print(nums[i] + " ");
}
System.out.println();
}
}
代码封装：
public static void bubbleSort(int[] arr){
for (int i = 0; i < arr.length-1; i++) {
boolean flag = false;//标志数组内是否发生交换
for (int j = 0; j < arr.length-1-i; j++) {
if (arr[j] > arr[j+1]){
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
flag = true;//发生交换
}
}
if (!flag)
break;
}
}
选择排序
基本思想：第一次从 arr[0]~arr[n-1] 中选取最小值，与 arr[0] 交换，第二次从 arr[1]~arr[n-1] 中选取最小值，与 arr[1] 交换...... 第 i 次从 arr[i-1]~arr[n-1] 中选取最小值，与 arr[i-1] 交换，......第 n-1 次从 arr[n-2]~arr[n-1] 中选取最小值，与 arr[n-2] 交换。总共通过 n-1 次，得到一个有序排列的数组。
示例：
代码实现：
package sort;
public class SelectSort {
public static void main(String[] args) {
int[] arr = { 101,34,119,1 };
System.out.print("选择排序之前：");
print(arr);
selectSort(arr);
System.out.print("选择排序之后：");
print(arr);
}
//选择排序时间复杂度 O(n^2)
public static void selectSort(int[] arr){
for (int i = 0; i < arr.length-1; i++) {
int min = arr[i];
int minIndex = i;
for (int j = i+1; j < arr.length; j++) {
if (min > arr[j]){
min = arr[j];//重置min
minIndex = j;//重置minIndex
}
}
if (i != minIndex){//优化，与 min交换
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
System.out.printf("第 %d 次选择排序：", i+1);
print(arr);
}
}
public static void print(int[] arr){
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
}
插入排序
基本思想：插入排序属于内部排序法，是对待排序的元素以插入的方式寻找该元素的适当位置，已达到排序的目的。把 n 个待排序的元素看成一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含 n-1 个元素排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表。
代码实现：
package sort;
import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;
public class InsertSort {
public static void main(String[] args) {
int[] arr = new int[80000];
for (int i = 0; i < 80000; i++) {
arr[i] = (int)(Math.random()*80000);//生成[0,80000)随机数
}
System.out.print("插入排序之前：");
Date date1 = new Date();
SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
String date1Str = simpleDateFormat.format(date1);
System.out.println(date1Str);
insertSort(arr);
System.out.print("插入排序之后：");
Date date2 = new Date();
String date2Str = simpleDateFormat.format(date2);
System.out.println(date2Str);
}
public static void insertSort(int[] arr){
for (int i = 1; i < arr.length; i++) {
int insertIndex = i-1;
int insertValue = arr[i];
while (insertIndex >= 0 && insertValue < arr[insertIndex]) {
arr[insertIndex + 1] = arr[insertIndex];
insertIndex--;
}
//判断是否需要赋值
if (insertIndex + 1 == i) {
arr[insertIndex + 1] = insertValue;
}
}
}
}
