初级排序算法

微信公众号：Vegout 如有问题或建议，请公众号留言

今天分享给您的是三种初级排序算法，但绝对也是经典排序算法。平时，当我们遇到需要排序的问题时，也许第一反应就是xxx.Sort()。太多的库函数为我们实现了排序的过程，其中的算法可能也会比今天谈到的排序算法高效的多，简单的调用，这种高效便为我们提供了服务，但今天我们为什么还要提及这些算法呢？ 知其然也需知其所以然，打开黑箱子的过程就是我们进步的过程。这些算法虽然很初级，但却是很多复杂排序算法的基石，他们会作为中间过程出现在复杂排序算法中。于是学习这些初级排序算法绝对是一个明智的选择。

提示：排序顺序默认从小到大，从A到Z

冒泡排序算法

冒泡排序，就是将相邻的元素进行比较，如果位置不对，则进行交换。这样，每一趟都会将最大或最小的元素浮到顶端，最终完成排序。

public class Bubble {
    public static void sort(int[] array){
        int N = array.length;
        for (int i = N-1;i>=0;i--){
            for (int j = 0;j<i;j++){
                if (array[j]>array[j+1]){
                    int temp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = temp;
                }
            }
        }
    }
}

外层for循环控制了进行比较的元素界限i，array[i]及其左侧的元素会进行冒泡，当然其右侧的元素必定就是每一趟冒泡浮到顶端的元素，位置已经确定。内层for循环就是将相邻的元素进行比对，交换。

选择排序算法

选择排序，就是不停的在没有排序的元素中选择最小的元素排到有序元素后边，或者作为所有元素中最小的元素排到数组首位。

public class Selection {
    public static void sort(int[] array){
        int N =array.length;              //数组长度
        for (int i = 0;i<N;i++){
                                          //将array[i]和array[i+1..N]中的最小元素交换
            int min = i;                  //记录下最小元素的索引
            for (int j = i+1;j<N;j++){
                if (array[min]>array[j])min = j;//寻找真正最小元素的索引
            }
            int temp = array[min];
            array[min] = array[i];
            array[i] = temp;
        }
    }
}

最外的for循环，确定了一个界限i。array[i]之前的元素一定是排好顺序的，并且在之后的排序过程中，之前的元素不会再次被访问。里层的for循环只有一个任务，寻找array[i]以及其之后的最小元素的索引。之后再将最小元素排到array[i]的位置。选择排序在所有的排序算法中数据移动次数是最少的，元素会被一次性排到它应该在的位置。但为之付出的代价也是巨大的，选择的过程会花费很长时间（与其他排序算法相比）。为了找到最小的元素，i之后的元素会一个一个进行比较，从而选出最小的元素。每一次扫描也不会给下一次扫描提供任何有用的信息。于是，对于选择排序来说，对一个大小为N的有序序列和一个大小为N的无序序列进行排序所花费的时间是一样的，运行时间和输入无关。我们在以后的文章中将会看到，其他算法更善于利用输入的初始状态。

插入排序算法

插入排序，就是将a[i]插入到a[i-1],a[i-2],a[i-3]….中比它大的元素之前。

public class Insertion {
    public static void sort(int[] array){
        int N =array.length;
        for (int i = 0;i<N;i++){
            for (int j = i;j>0&&array[j]<array[j-1];j--){
                int temp = array[j];
                array[j] = array[j-1];
                array[j-1] = temp;
            }
        }
    }
}

外层的for循环，将i从0移动到N-1，并且保证array[i]左侧的元素都已经有序，但每个元素可能并不是在最终的位置（可能还会被array[i]之后的元素插来插去）。内层的for循环便负责了“插入”这一重要的动作，j一直向前推移，一旦发现比array[j]大的元素，就插入到这个大的元素之前，一旦发现比array[j]小的元素,内层for循环就会停止。

结语

这三种排序算法的时间复杂度都是平方级别的，但在不同情况下的表现却是不同的。如果有相对有序元素数组A和相对无序元素数组B，对与选择排序算法来说，处理A和处理B的时间是一样的；对与冒泡排序来说，处理A比处理B，比较的次数不变，交换的次数会减少；对与插入排序来说，处理A比处理B就要快特别多了，因为它比较的次数和插入（交换）的次数都会减少。插入排序与另外两种算法作比较，插入排序对与部分有序的数组十分高效。