冒牌排序
介绍
冒泡排序（Bubble Sorting）的基本思想是：通过对待排序序列从前向后（从下标较小的元素开始）,依次比较相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从前移向后部，就象水底下的气泡一样逐渐向上冒。
?演示冒泡过程的例子(图解)
?
代码实现?
import java.time.Duration;
import java.time.LocalTime;
public class BubbleSort {
public static void main(String[] args) {
test1();
// test2();
}
public static void test1() {
int len=15;
int arr[]=new int [len];
for(int i=0;i<len;i++) {
arr[i]=(int) (Math.random()*len);
}
System.out.println("排序前数组：");
printArr(arr);
bubbleSort(arr);
System.out.println("排序后数组：");
printArr(arr);
}
//若干万数据，测试排序的时间
public static void test2() {
int len=50000;
int arr[]=new int [len];
for(int i=0;i<len;i++) {
arr[i]=(int) (Math.random()*len);
}
LocalTime before=LocalTime.now();
System.out.println("排序前的时间："+before);
bubbleSort(arr);
LocalTime after=LocalTime.now();
Duration duration=Duration.between(before, after);
System.out.println("排序后的时间："+after);
System.out.println("时间差(毫秒)："+duration.toMillis());
}
private static void bubbleSort(int[] arr) {
boolean flag=false; //标识变量，是否进行过交换
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]) {
//交换
flag=true; // 发生一次交换
int temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
}
if(!flag) { // 一趟排序中，依次交换都没有发生过
break;
}else {
flag=false; // 重置
}
}
}
//打印数组
private static void printArr(int[] arr) {
for(int i=0;i<arr.length;i++) {
System.out.print(arr[i]+" ");
}
System.out.println();
}
}
运行结果：
test1()运行结果：
?
?test2()排序5万数据运行结果：
选择排序?
介绍?
选择排序（select sorting）也是一种简单的排序方法。它的基本思想是：第一次从arr[0]~arr[n-1]中选取最小值，与arr[0]交换，第二次从arr[1]~arr[n-1]中选取最小值，与arr[1]交换，第三次从arr[2]~arr[n-1]中选取最小值，与arr[2]交换，…，第i次从arr[i-1]~arr[n-1]中选取最小值，与arr[i-1]交换，…, 第n-1次从arr[n-2]~arr[n-1]中选取最小值，与arr[n-2]交换，总共通过n-1次，得到一个按排序码从小到大排列的有序序列。
?
?代码实现
import java.time.Duration;
import java.time.LocalTime;
public class SelectionSort {
public static void main(String[] args) {
test1();
// test2();
}
public static void test1() {
int len=15;
int arr[]=new int [len];
for(int i=0;i<len;i++) {
arr[i]=(int) (Math.random()*100);
}
System.out.println("排序前数组：");
printArr(arr);
selectionSort(arr);
System.out.println("排序后数组：");
printArr(arr);
}
//若干万数据，测试排序的时间
public static void test2() {
int len=50000;
int arr[]=new int [len];
for(int i=0;i<len;i++) {
arr[i]=(int) (Math.random()*len);
}
LocalTime before=LocalTime.now();
System.out.println("排序前的时间："+before);
selectionSort(arr);
LocalTime after=LocalTime.now();
Duration duration=Duration.between(before, after);
System.out.println("排序后的时间："+after);
System.out.println("时间差(毫秒)："+duration.toMillis());
}
public static void selectionSort(int arr[]) {
for(int i=0;i<arr.length-1;i++) {
//假定 arr[i]是最小值，i是最小值的下标
int minIndex=i;
for(int j=i+1;j<arr.length;j++) {
if(arr[j]<arr[minIndex]) {
//更新最小值
minIndex=j;
}
}
//如果最小值的下标不是i则交换arr[i]和最小值
if(minIndex!=i) {
int temp=arr[i];
arr[i]=arr[minIndex];
arr[minIndex]=temp;
}
}
}
//打印数组
private static void printArr(int[] arr) {
for(int i=0;i<arr.length;i++) {
System.out.print(arr[i]+" ");
}
System.out.println();
}
}
运行结果：
test1()?
?test2() 排序5万数据的时间
?插入排序
介绍：
插入排序法思想:
插入排序（Insertion Sorting）的基本思想是：把n个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表。
代码实现?
import java.time.Duration;
import java.time.LocalTime;
public class InsertionSort {
public static void main(String[] args) {
test1();
// test2();
}
public static void test1() {
int len=15;
int arr[]=new int [len];
for(int i=0;i<len;i++) {
arr[i]=(int) (Math.random()*100);
}
System.out.println("排序前数组：");
printArr(arr);
insertionSort(arr);
System.out.println("排序后数组：");
printArr(arr);
}
//若干万数据，测试排序的时间
public static void test2() {
int len=50000;
int arr[]=new int [len];
for(int i=0;i<len;i++) {
arr[i]=(int) (Math.random()*len);
}
LocalTime before=LocalTime.now();
System.out.println("排序前的时间："+before);
insertionSort(arr);
LocalTime after=LocalTime.now();
Duration duration=Duration.between(before, after);
System.out.println("排序后的时间："+after);
System.out.println("时间差(毫秒)："+duration.toMillis());
}
public static void insertionSort(int []arr) {
int i;
for(int p=1;p<arr.length;p++) {
int temp=arr[p];
//当前数比上一个数小，就插到上一个数的前面
//i从p扫描，如果[i-1]比当前temp大，则[i-1]向后挪1个位置
//如果用希尔排序的方法理解，i>=gap, arr[i-gap] 这个插入排序的gap是1
//
for(i=p;i>=1 && temp<arr[i-1];--i)
arr[i]=arr[i-1];
arr[i]=temp;
}
}
//打印数组
private static void printArr(int[] arr) {
for(int i=0;i<arr.length;i++) {
System.out.print(arr[i]+" ");
}
System.out.println();
}
}
运行结果：
test1()?
?test2() 5万数据运行时间
