1、选择排序
package com.example.demo.algorithm;
import java.util.Arrays;
/**
* @Description :
* 选择排序
*
* 数据规模：N
* 0 ~ N-1 （看 + 比） + 交换
* 1 ~ N-1 （看 + 比） + 交换
* 2 ~ N-1 （看 + 比） + 交换
* 3 ~ N-1 （看 + 比） + 交换
* i ~ N-1 （看 + 比） + 交换
* ...
* N-1 ~ N-1（看 + 比） + 交换
*
* 0 ~ N-1 （2） + 1
* 1 ~ N-1 （2） + 1
* 2 ~ N-1 （2） + 1
* 3 ~ N-1 （2） + 1
* i ~ N-1 （2） + 1
* ...
* N-1 ~ N-1（2） + 1
*
* 2 *（N-1 + N-2 + N-3 + ...） + N
* = 2 * （aN^2 + bN + c） + N
* = 2 * N^2 + 2bN + 2c + N
* = O(N^2)
* 舍弃低阶项和常数项
*
* @Author : Darren
* @Date : 2020 年 12 月 28 日 19:39:08
* @since : 1.0
*/
public class J001_SelectSort {
public static void main(String[] args) {
int count = 500000;
int maxSize = 100;
int maxValue = 100;
boolean success = true;
for (int i = 0; i < count; i++) {
int[] var1 = generateRandomArray(maxSize, maxValue);
int[] var2 = copyArray(var1);
selectSort(var1);
comparator(var2);
if (!isEqual(var1, var2)){
success = false;
printArray(var1);
printArray(var2);
break;
}
}
System.out.println(success ? "success" : "failure");
}
public static void selectSort(int[] arrays){
if (arrays == null || arrays.length < 2){
return;
}
// 0 ~ N-1 找到最小值，在哪，放到0位置上
// 1 ~ n-1 找到最小值，在哪，放到1 位置上
// 2 ~ n-1 找到最小值，在哪，放到2 位置上
for (int i = 0; i < arrays.length - 1; i++){
int minIndex = i;
// i ~ N-1 上找最小值的下标，与当前的最小值minIndex替换
for (int j = i + 1; j < arrays.length; j++){
minIndex = arrays[j] < arrays[minIndex] ? j : minIndex;
}
swap(arrays, i, minIndex);
}
}
public static void swap(int[] arrays, int i, int j) {
int tmp = arrays[i];
arrays[i] = arrays[j];
arrays[j] = tmp;
}
/**
* 生成一个随机数组
* @param maxSize
* @param maxValue
* @return
*/
public static int[] generateRandomArray(int maxSize, int maxValue){
//Math.random() [0,1)
//Math.random() * N [0,N)
//(int)(Math.random() * N) [0,N-1]
int[] arrays = new int[(int) ((maxSize+1) * Math.random())];
for (int i = 0; i < arrays.length; i++) {
arrays[i] = (int) ((maxValue+1) * Math.random()) - (int)(maxValue * Math.random());
}
return arrays;
}
/**
* 生成一个随机数
* @param maxValue
* @return
*/
public static int generateRandom(int maxValue){
return (int) ((maxValue+1) * Math.random()) - (int)(maxValue * Math.random());
}
/**
* java自带排序
* @param arrays
*/
public static void comparator(int[] arrays){
Arrays.sort(arrays);
}
/**
* java自带复制数组
* @param arrays
* @return
*/
public static int[] copyArray(int[] arrays){
return Arrays.copyOf(arrays, arrays.length);
}
/**
* 判断两个数组是否相等
* @param var1
* @param var2
* @return
*/
public static boolean isEqual(int[] var1, int[] var2){
if ((var1 == null && var2 != null) || (var1 != null && var2 == null)){
return false;
}
if(var1 == null && var2 == null){
return true;
}
if (var1.length != var2.length){
return false;
}
for (int i = 0; i < var1.length; i++) {
if (var1[i] != var2[i]){
return false;
}
}
return true;
}
/**
* 打印数组
* @param arrays
*/
public static void printArray(int[] arrays){
if (arrays == null){
return;
}
for (int i = 0; i < arrays.length; i++) {
System.out.print(arrays[i] + " ");
}
System.out.println();
}
}
2、冒泡排序
package com.example.demo.algorithm;
/**
* @Description :
* 冒泡排序
*
* 0 ~ N-1 0位置的数和后面的每个数比较，将较大值不断的往后移 N-1位置放最大值
* 0 ~ N-2 0位置的数和后面的每个数比较，将较大值不断的往后移 N-2位置放最大值
* 0 ~ N-3 0位置的数和后面的每个数比较，将较大值不断的往后移 N-3位置放最大值
* 0 ~ N-i 0位置的数和后面的每个数比较，将较大值不断的往后移 N-i位置放最大值
* ……
* 0 ~ 0 终止
*
* @Author : Darren
* @Date : 2020 年 12 月 28 日 19:39:08
* @since : 1.0
*/
public class J002_BubbleSort {
public static void main(String[] args) {
int count = 500000;
int maxSize = 100;
int maxValue = 100;
boolean success = true;
for (int i = 0; i < count; i++) {
int[] var1 = J001_SelectSort.generateRandomArray(maxSize, maxValue);
int[] var2 = J001_SelectSort.copyArray(var1);
bubbleSort(var1);
J001_SelectSort.comparator(var2);
if (!J001_SelectSort.isEqual(var1, var2)){
success = false;
J001_SelectSort.printArray(var1);
J001_SelectSort.printArray(var2);
break;
}
}
System.out.println(success ? "success" : "failure");
}
public static void bubbleSort(int[] arrays){
if (arrays == null || arrays.length < 2){
return;
}
//0 ~ N-1
//0 ~ N-2
//0 ~ N-3
for (int i = arrays.length - 1; i >= 0; i--) {
//内循环一次 i位置的数就排好序了
for (int j = 0; j < i; j++) {
if (arrays[j] > arrays[j+1]){
J001_SelectSort.swap(arrays, j, j+1);
}
}
}
}
}
3、插入排序
package com.example.demo.algorithm;
/**
* @Description :
* 插入排序
*
* 0 ~ 0 想做到有序 默认有序
* 0 ~ 1 想做到有序 1位置往前看 小则交换
* 0 ~ 2 想做到有序 2位置往前看 小则交换
* 0 ~ i 想做到有序 i位置往前看 小则交换
* ……
* 0 ~ N-1 想做到有序 N-1位置往前看 小则交换
*
* @Author : Darren
* @Date : 2021 年 02 月 07 日 19:29:30
* @since : 1.0
*/
public class J003_InsertionSort {
public static void main(String[] args) {
int count = 500000;
int maxSize = 100;
int maxValue = 100;
boolean success = true;
for (int i = 0; i < count; i++) {
int[] var1 = J001_SelectSort.generateRandomArray(maxSize, maxValue);
int[] var2 = J001_SelectSort.copyArray(var1);
insertionSort(var1);
J001_SelectSort.comparator(var2);
if (!J001_SelectSort.isEqual(var1, var2)){
success = false;
J001_SelectSort.printArray(var1);
J001_SelectSort.printArray(var2);
break;
}
}
System.out.println(success ? "success" : "failure");
}
public static void insertionSort(int[] arrays){
if (arrays == null || arrays.length < 2){
return;
}
// 0 ~ 0 想做到有序 默认有序
// 0 ~ 1 想做到有序 1位置往前看 小则交换
// 0 ~ 2 想做到有序 2位置往前看 小则交换
// 0 ~ i 想做到有序 i位置往前看 小则交换
for (int i = 1; i < arrays.length; i++) {
//i=1 j=0 -> 0位置和1位置比较 0~1位置有序
//i=2 j=1 -> 1位置和2位置比较 0位置和1位置比较 0~2位置有序
//i=3 j=2 -> 2位置和3位置比较 1位置和2位置比较 0位置和1位置比较 0~3位置有序
//将j+1插入到合适的位置
for (int j = i - 1; j >= 0; j--) {
if (arrays[j] > arrays[j+1]){
J001_SelectSort.swap(arrays, j, j+1);
}
}
}
}
}
