七大经典算算法总结（非原创，有很多借鉴）

冒泡算法是一个很简单的 排序 算法，通过每次相邻的两个元素进行比较，如果前面的比后面的大就交换两个元素（也可以比较是否是小，取决于是升序排序还是降序排序），可以理解的是，通过n-1次比较就排序排好了，同时也可以发现不管初始序列的状态如何，冒泡排序的时间复杂都是O(n^2).

1.1 算法过程描述

1.从第一个开始，比较相邻的两个元素，如果第一个比第二大，则交换

2.对每一相邻元素做相同的工作，从开始第一对到结尾的最后一对，这样第一次就将最大的数放到了数组结尾了

3.针对所有的元素重复以上步骤

4.重复步骤1~3，直到排序完成

1.2 动图演示

1.3 代码实现

public static void bubbleSort(int[] nums) {
    /**
     * 养成良好的习惯，一定要对程序的鲁棒性进行判断，处理异常输入的能力
     **/
    if (nums == null || nums.length <= 0) {
        return;
    }
    int length = nums.length;
    // 排序n - 1次就完成了排序了
    for (int i = 0; i < length - 1; i++) {
        for (int j = 0; j < length - 1 - i; j++) {
            //如果前面比后面大，就开始交换
            if (nums[j] > nums[j + 1]) {
                int temp = nums[j];
                nums[j] = nums[j + 1];
                nums[j + 1] = temp;
            }
        }
    }
}
复制代码

2 选择排序

选择排序是一种简单的排序算法，每次在未排序的序列中选出最小（大）的一个元素，存放到序列的起始位置，然后再从剩余未排序的元素中继续寻找最小（大）元素，放到已排序序列的末尾，以此类推，直到所有元素均排序完成。

2.1 算法描述过程

1.初始状态：无序区为R[1...n],有序区为空

2.第i趟排序（i=1,2,3...n-1）开始时，当前有序区和无序区分别为R[1...i-1]和R(i..n)。该趟排序从当前无序区中选出关键字最小的记录R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R[i+1..n]分别变为记录个数，增加1个的新有序区和记录个数减少1个的新无序区；

3.n-1趟结束，数组有序化了

2.2 动图演示

2.3 代码实现

public static void selectSort(int[] nums) {
    if (nums == null || nums.length <= 0) {
        return;
    }
    int minIndex, temp, length = nums.length;
    for (int i = 0; i < length - 1; i++) {
        // 从第i个开始，先标记最开始这个为最小的数
        minIndex = i;
        for (int j = i + 1; j < length; j++) {
            if (nums[j] < nums[minIndex]) {
                // 如果后面出现了更小的数，则记下该数的下标，因为后面需要将最小的数放到最前面
                minIndex = j;
            }
        }
        temp = nums[i];
        nums[i] = nums[minIndex];
        nums[minIndex] = temp;
    }
}
复制代码

3 插入排序

插入排序是一种相对也比较简单直观的排序算法，工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

3.1 算法描述

1.从第一个元素，该元素可以认为已经被排序；

2.取出下一个元素，在已经排序的元素中从后向前扫描；

3.如果该元素（已排序的元素）大于新元素，将该元素移到下一位置；

4.重复步骤3，直到找到已排序的元素小于或等于新元素的位置；

5.将新元素插入到该位置;

6.重复步骤2~5.

3.2 动图演示

3.3 代码实现

public static void inserSort(int[] nums) {
    if (nums == null || nums.length <= 0) {
        return;
    }
    int length = nums.length;
    for (int i = 1; i < length; i++) {
        // 用来记录比当前元素小或者等于当前元素的那个位置，则当前元素就应该插入到该元素后面一个
        preIndex = i - 1;
        // 记录当前需要插入的元素
        current = nums[i];
        while (preIndex >= 0 && nus[preIndex] > current) {
            // 只要preIndex指向的元素值大于当前元素，则就应该将该元素一直往后移
            nums[preIndex + 1] = nus[preIndex];
            preIndex--;
        }
        // 将需要插入的元素插入到属于它的位置
        nums[preIndex + 1] = current;
    }
}
复制代码

4 希尔排序

希尔排序是第一个突破O(n^2)的排序算法，是简单插入排序的改进版，它与插入排序不同之处在于，它会优先比较距离较远的元素。希尔排序又叫作缩小增量排序。

4.1 算法描述

先将整个待排序的序列分割为若干子序列分别进行直接插入排序，具体算法描述：

1.选择一个增量序列t1,t2,....,tk,其中ti>tj，tk=1；

2.按增量序列个数k，对序列进行k趟排序；

3.每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m的子序列，分别对各子表进行直接插入排序。仅增量因子为1时，整个序列作为一个表来处理，表长度即为整个序列的长度。

4.2 动图演示

4.3 代码实现

public static void shellSort(int[] nums) {
    if (nums == null || nums.length <= 0) {
        return;
    }
    int length = nums.length;
    for (int gap = length / 2; gap > 0; gap = gap / 2) {
        for (int i = gap; i < length; i++) {
            int j = i;
            int temp = nums[j];
            if (nums[j] < nums[j - gap]) {
                while (j - gap >= 0 && temp < nums[j - gap]) {
                    nums[j] = nums[j - gap];
                    j -= gap;
                }
                nums[j] = temp;
            }
        }
    }
}
复制代码