Created
April 24, 2018 07:30
-
-
Save liweiwei1419/9231657e0b8506f8e6d3f2702dc9e8ec to your computer and use it in GitHub Desktop.
插入排序的 Java 代码实现。
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package test; | |
import java.util.Arrays; | |
import java.util.Random; | |
public class InsertSort { | |
private static Random random = new Random(System.currentTimeMillis()); | |
/** | |
* 判断给定的数组是不是已经排好序的数组 | |
* | |
* @param arr | |
*/ | |
private static void checkSorted(int[] arr) { | |
int len = arr.length; | |
for (int i = 0; i < len - 1; i++) { | |
if (arr[i] > arr[i + 1]) { | |
throw new RuntimeException("数组不是排好序的"); | |
} | |
} | |
} | |
/** | |
* @param count 数组中元素的个数 | |
* @param mix 最小值能取到 | |
* @param max 最大值取不到 | |
* @return | |
*/ | |
private static int[] generateRamdonArray(int count, int mix, int max) { | |
int[] arr = new int[count]; | |
int bound = max - mix; | |
for (int i = 0; i < count; i++) { | |
int randomInt = random.nextInt(bound) + mix; | |
arr[i] = randomInt; | |
} | |
return arr; | |
} | |
private static void swap(int[] arr, int index1, int index2) { | |
if (index1 == index2) return; | |
int temp = arr[index1]; | |
arr[index1] = arr[index2]; | |
arr[index2] = temp; | |
} | |
public static void main(String[] args) { | |
// 插入排序(内层循环可以提前终止) | |
int[] arr = generateRamdonArray(15, 10, 100); | |
System.out.println("原始数组" + Arrays.toString(arr)); | |
int len = arr.length; | |
for (int i = 0; i < len - 1; i++) { // 第 1 轮的时候,第 1 个数可以认为是排好序的 | |
for (int j = i + 1; j > 0; j--) { | |
if (arr[j] < arr[j - 1]) { | |
swap(arr, j, j - 1); | |
} else { | |
break; | |
} | |
} | |
} | |
checkSorted(arr); | |
System.out.println("排好序的数组" + Arrays.toString(arr)); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment