用一首诗来总结下常见排序算法及其时间复杂度和稳定性：
选泡插
快归堆希统计基
恩方恩老恩一三
对恩加K恩乘K
不稳稳稳不稳稳
不稳不稳稳稳稳
常见排序算法 .png
如何写算法程序：
- 由简单到复杂
- 验证一步走一步
- 多打印中间结果
- 先局部后整体
- 没思路时先细分
- 先粗糙后精细
- 变量更名
- 语句合并
- 边界处理
- 选择排序
最简单但是最没用的算法：时间复杂度高O(n*n)，但是不稳定，基本不用。
public class SelectionSort {
public static void main(String[] args){
int[] arr = {4,7,1,3,8,2,9};
int minPos;
for (int i = 0; i < arr.length - 1; i++) {
minPos = i;
for (int j = i + 1; j < arr.length; j++) {
minPos = arr[j] < arr[minPos] ? j : minPos;
}
System.out.println("minPos:" + minPos);
swap(arr,i,minPos);
System.out.println("这是经过第:" + i + "次循环后数组的内容");
print(arr);
}
}
static void swap(int[] arr,int i,int j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
static void print(int[] arr){
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
}
- 验证算法的正确性：对数器
生成一个足够大的随机数组，copy一份相同的数据。用确定正确的算法对数组排序，再使用自己的算法对copy的数组排序。生成多次随机数进行操作，如果每次排序后两个数组的数据排序结果都完全一样，证明自己的算法是正确的。
public class DataCheck {
public static void main(String[] args){
check();
}
private static void check() {
int[] arr = generateRandomArray();
int[] arr2 = new int[arr.length];
System.arraycopy(arr,0,arr2,0,arr.length);
Arrays.sort(arr);
SelectionSort.sort(arr2);
boolean same = true;
for (int i = 0; i < arr.length; i++) {
if (arr[i] != arr2[i]){
same = false;
}
}
}
private static int[] generateRandomArray() {
Random random = new Random();
int[] arr = new int[10000];
for (int i = 0; i < arr.length; i++) {
arr[i] = random.nextInt(10000);
}
return arr;
}
}
- 冒泡排序
平均时间复杂度是O(n*n)，最好时间复杂度是O(n)，是稳定的。基本不用冒泡排序，因为要两两比较，太慢。
public class BubbleSort {
public static void main(String[] args){
int[] arr = {9,6,1,3,5};
sort(arr);
print(arr);
}
private static void print(int[] arr) {
for (int i = 0; i < arr.length; i++) {
System.out.print( arr[i] + " ");
}
}
private static void sort(int[] arr) {
for (int i = arr.length - 1;i > 0;i--){
for (int j = 0;j < i ;j++){
if (arr[j] > arr[j + 1]){
swap(arr,j,j +1);
}
}
}
}
private static void swap(int[] arr,int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
- 插入排序
对于基本有序的数组最好用，是稳定的
public class InsertionSort {
public static void main(String[] args){
int[] arr = {9,6,1,3,5};
sort(arr);
print(arr);
}
private static void print(int[] arr) {
for (int i = 1; i < arr.length; i++) {
System.out.print( arr[i] + " ");
}
}
private static void sort(int[] arr) {
for (int i = 1;i < arr.length;i++){
for (int j = i;j > 0;j--){
if (arr[j] < arr[j - 1]){
swap(arr,j,j - 1);
}
}
}
}
private static void swap(int[] arr,int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
