最近更新：2018-8-31 11:06

本篇文章介绍的是平时使用的比较多的并且必须掌握的各种算法

一、排序算法

排序就是将一组可比较大小的数据集合按从小到大（升序）或者从大到小（降序）的方式重新组织。
排序算法是用来对数据进行排序的工具，所以工欲善其事，必先利其器。今天，排序算法的种类是很多的，有简单的泡泡排序、选择排序、插入排序，还有复杂一些的归并排序、希尔排序、快速排序等。下面我们就来看看这些算法

冒泡排序
冒泡排序可以说是众多排序算法中最简单的一种排序算法。原理很简单，顾名思义，这种算法就像水中的泡泡一样，在排序的过程中，数组中的元素不断的网上冒，直到所有的泡泡都冒完了。
算法有如下几点：
1. 在冒泡的过程中，每次冒泡一个，即每次把当前未排序的元素的最大值（升序）放到当前待排序数组的最后
2. 元素个数为 n 的数组，总共需要冒泡 n-1 次，即要排序 n-1 趟
3. 已经排序过（冒泡）的元素不参与以后每趟的排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 冒泡排序
public class BubbleSort{
    public void sort(int...nums){
        // 排序n-1趟
        for(int i=1; i<nums.length; i++){
            // 进行第i趟排序
            for(int j=0; j<nums.length-i;j++){
                if(nums[j] > nums[j+1]){
                    int tmp = nums[j];
                    nums[j] = nums[j+1];
                    nums[j+1] = tmp;
                }
            }
        }
    }
}

选择排序
选择排序与冒泡排序有点类似，但是有不像冒泡排序一样，每次都要两两比较，然后再互相交换。
选择排序的原理是每次选择时都在待排序的数组中选择一个最小值（升序排序），或者一个最大值（降序排序），然后把该值与当前待排序数组的第一个元素交换。所以每次选择一个最值，在长度为n的数组中，共需要选择n-1次
选择排序有如下几步：
1. 长度为n的数组共需要选择n-1次
2. 每次选择一个最小值（升序排序）
3. 把选出来的值与当前待排序数组的第一个元素互换

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 选择排序
public class ChooseSort{
    public void sort(int... nums){
        // 选择排序 n-1 次
        for (int i=1; i<nums.length; i++){
            int current = i-1;
            int minIndex = current;
            // 进行第i次选择
            for (int j = i; j<nums.length; j++){
                if (nums[j]<nums[minIndex]){
                    minIndex = j;
                }
            }
            if(minIndex!=current){
                int tmp = nums[minIndex];
                nums[minIndex] = nums[current];
                nums[current] = tmp;
            }
        }
    }
}

插入排序

归并排序

希尔排序

快速排序