基础

算法（algorithm；算法），在数学（算学）和计算机科学之中，指一个被定义好的、计算机可施行其指示的有限步骤或次序，常用于计算、数据处理和自动推理。算法是有效方法，包含一系列定义清晰的指令，并可于有限的时间及空间内清楚的表述出来。

冒泡排序

原理

比较两个相邻的元素，将值大的元素交换到右边

实现

public class BubbleSort {

    public static void main(String[] args) {
        int[] arr = {3, 5, 2, 1, 8, 9};
        print(arr);
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr.length - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    swap(arr, j, j + 1);
                }
            }
        }
        print(arr);
    }

    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[j];
        arr[j] = arr[i];
        arr[i] = tmp;
    }

    public static void print(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]);
        }
        System.out.println();
    }
}

选择排序

原理

每一趟从待排序的记录中选出最小的元素，顺序放在已排好序的序列最后，直到全部记录排序完毕。

实现

public class SelectionSort {

    public static void main(String[] args) {
        int[] arr = {4, 6, 2, 9, 1, 7, 3, 8};
        print(arr);
        for (int i = 0; i < arr.length; i++) {
            int min = i;
            for (int j = i; j < arr.length; j++) {
                if (arr[min] > arr[j]) {
                    min = j;
                }
            }
            swap(arr, i, min);
        }
        print(arr);
    }

}

插入排序

原理

将一个记录插入到已经排好序的有序表中，从而一个新的、记录数增 1 的有序表

实现

public class InsertionSort {

    public static void main(String[] args) {
        int[] arr = {5, 3, 8, 2, 9, 7, 4, 1};
        print(arr);
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = i; j >= 0; j--) {
                if (arr[j] > arr[j + 1]) {
                    swap(arr, j, j + 1);
                }
            }
        }
        print(arr);
    }

}

希尔排序

原理

希尔排序(Shell Sort)是插入排序的一种，它是针对直接插入排序算法的改进。

实现

归并排序

思想

归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案”修补”在一起，即分而治之)。

原理

实现

public class MergeSort {
    
    public static void main(String[] args) {
        int[] data = {2, 4, 5, 7, 9, 1, 3, 6, 8, 9};
        int left = 4;
        int right = 9;
        sort(data, left, right);
        print(data);
    }

    private static void sort(int[] data, int left, int right) {
        int[] tmp = new int[data.length];
        int i = 0;
        int j = left + 1;
        int k = 0;

        while (k < data.length && i < data.length / 2 && j < data.length) {
            if (data[i] < data[j]) {
                tmp[k] = data[i];
                i++;
            } else {
                tmp[k] = data[j];
                j++;
            }

            k++;
        }

        // 处理左边剩余部分
        while (i <= left) {
            tmp[k] = data[i];
            i++;
            k++;
        }

        // 处理右边剩余部分
        while (j <= right) {
            tmp[k] = data[j];
            j++;
            k++;
        }

        // 将数据复制给原数组
        for (int n = 0; n < tmp.length; n++) {
            data[n] = tmp[n];
        }

        print(tmp);
    }


    public static void print(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]);
        }
        System.out.println();
    }
}