Java十大经典排序算法（一）
由于冒泡排序的简洁性，通常被用作对入门学生介绍算法概念的案例，也是企业面试的常见考察点。本系列从冒泡排序开始说起，建议此文阅读时跟着写一遍代码。
【冒泡排序】
冒泡排序（Bubble Sort）是一种稳定的排序算法。
原理：首先遍历要排序的数组，一次比较两个元素，如果顺序错误就交换位置，重复进行直到没有再需要交换的元素。这个算法因为越小或者越大的元素会经由交换慢慢“浮”到数列越顶端而得名。
【代码说明】升序：冒大元素到队尾
//冒泡排序：先冒大元素int score[] = { 100,5,25,88,8 };System.out.println("原始数组："+Arrays.toString(score));for (int i = 0; i < score.length -1; i++) {for (int j = 0; j < score.length - i - 1; j++) {//以内循环元素为基准冒大元素到队尾if (score[j] > score[j + 1]) {int temp = score[j];score[j] = score[j + 1];score[j + 1] = temp;}System.out.println("第" + (j + 1) + "次交换结果："+ Arrays.toString(score));}System.out.println("第" + (i + 1) + "次[排序]结果："+ Arrays.toString(score)+"\n");}
我们可以清晰地看到控制台输出结果体现了这种“冒”元素的方式:先把100给“冒出来”放置队尾，然后把88“冒出来”……以此类推。
原始数组：[100, 5, 25, 88, 8]// 比较100,5第1次交换结果：[5, 100, 25, 88, 8]//比较100,25第2次交换结果：[5, 25, 100, 88, 8]//比较100,88第3次交换结果：[5, 25, 88, 100, 8]//比较100，8第4次交换结果：[5, 25, 88, 8, 100]//100冒完，完成第一轮排序第1次[排序]结果：[5, 25, 88, 8, 100]第1次交换结果：[5, 25, 88, 8, 100]第2次交换结果：[5, 25, 88, 8, 100]第3次交换结果：[5, 25, 8, 88, 100]第2次[排序]结果：[5, 25, 8, 88, 100]第1次交换结果：[5, 25, 8, 88, 100]第2次交换结果：[5, 8, 25, 88, 100]第3次[排序]结果：[5, 8, 25, 88, 100]第1次交换结果：[5, 8, 25, 88, 100]第4次[排序]结果：[5, 8, 25, 88, 100]
既然我们可以通过把大元素先冒到队尾，如下图所示当然也可以先把小元素冒到队首完成排序效果，篇幅有限输出结果请大家自行测试：
//冒泡排序：先冒小元素int[] score = {100,5,25,88,8};System.out.println("原始数组："+Arrays.toString(score));int temp;for (int i = 0; i < score.length - 1; i++) {//外循环元素为基准冒小元素到前面for (int j = i; j < score.length - 1; j++) {if (score[i] > score[j + 1]) {temp = score[i];score[i] = score[j + 1];score[j + 1] = temp;}System.out.println("第" + (j + 1) + "次交换结果："+ Arrays.toString(score));}System.out.println("第" + (i + 1) + "次[排序]结果："+ Arrays.toString(score)+"\n");}System.out.println("最终结果为："+Arrays.toString(score));
时间复杂度分析：
冒泡排序算法时间复杂度为O(n²)，适用于排序小列表，最佳情况（序列原本就是正序） 时间复杂度为O(n)，此时需要对代码进行改进（以从小到大排列为例)，我么可以定义一个标识（didSwap）判断是否跳出外层循环：
int[] score = {5, 8, 25, 88, 100};System.out.println("原始数组："+ Arrays.toString(score));boolean didSwap;//双重循环遍历for (int i = 0; i < score.length - 1; i++) {// 是否发生交换,若没有交换，提前跳出外层循环didSwap = false;for (int j = i; j < score.length - 1; j++) {//……省略交换代码System.out.println("第" + (j + 1) + "次交换结果："+ Arrays.toString(score));}if(!didSwap){System.out.println("没有发生交换，跳出外循环。");break;}}System.out.println("最终结果为："+Arrays.toString(score));
此时输出结果为：
原始数组：[5, 8, 25, 88, 100]第1次交换结果：[5, 8, 25, 88, 100]第2次交换结果：[5, 8, 25, 88, 100]第3次交换结果：[5, 8, 25, 88, 100]第4次交换结果：[5, 8, 25, 88, 100]没有发生交换，跳出外循环。最终结果为：[5, 8, 25, 88, 100]
时间复杂度解析：
时间复杂度不能精确表示算法的执行次数，而只是以执行次数为计算基准下表达代码执行时间随数据规模增长的变化趋势。
如下图所示，横坐标为数据量，纵坐标为时间，可以发现时间复杂度对程序运行的不同影响，越陡峭的曲线说明程序对数据量增长的承受能力越弱。
如何计算时间复杂度？
简单来说就是统计当前函数被调用一次后计算出某段程序被调用的总次数T(n），然后去掉不重要的因素后得到的一个数字，加上O()为单位。
如下图所示，比如只是3条输出语句，则T(n)=3，像这样T(n)=常数的程序时间复杂度均为O(1)。
//时间复杂度O(1)System.out.println("da");System.out.println("ji");System.out.println("ya");
若计算结果为多项式，如T(n)=2n^2+n+6，则(去掉常数项和最高次项的系数等)只保留最大次幂也就是O(n^2)；
如下图所示，若在循环中第三个表达式（循环变量修正表达式）为i*=2，那么此时T(n)=3*log(2)n+2，只保留表达增长趋势的log n，去掉底数，为O(log n)。
//时间复杂度为O(log n)for (int i = 0; i < n; i *= 2) {System.out.println("调用此循环一次代码总执行次数大概为:" +" 1 + 1 + 3(log(2)n)" +"= 2 + 3(log(2)n)");}
底数问题：
去掉底数是因为算法中log级别的时间复杂度都是由于使用了分治思想（将大问题分而治之，各个子问题相互独立且与原问题性质相同），这个底数直接由分治的复杂度决定：如果采用二分法,那么就会以2为底，三分法就会以3为底数，其他类似。
假如n趋于无穷大的时候，任意底数的一个对数函数都只是相差常数倍而已。所以无论底数是什么，log级别的渐进意义是一样的。也就是说算法时间复杂度的增长与数据量增长之间的关系是一样的。所以Java使用O(logn)表达所有底数的对数的时间复杂度（变化趋势）。
【选择排序】
选择排序（Selection sort）也是一种稳定的排序算法，并且使用选择排序无论什么数据进去都是O(n2)的时间复杂度，所以数据规模越小效果越好。
原理：首先在未排序序列中找到最小（最大）元素，存放在排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，再放到已排序序列的末尾，以此类推，直到所有元素均排序完毕。
【代码说明】
//选择排序int score[] = { 100,5,25,88,8 };System.out.println("原始数组："+ Arrays.toString(score));for (int i = 0; i < score.length; i++) {int minIndex = i;for (int j = i+1; j < score.length; j++) {if (score[j] < score[minIndex]) //找到最小的数minIndex = j; //将最小数的索引保存System.out.print("第" + (j - i ) + "次找到的最小结果坐标为："+ minIndex+"\n");}//保存当前最小的元素到最前面的位置if(minIndex != i){int temp = score[minIndex];score[minIndex] = score[i];score[i] = temp;}System.out.println("此次找到最小值为："+temp);System.out.println("第" + (i + 1) + "次[排序]结果："+ Arrays.toString(score)+"\n");}System.out.println("排序后："+Arrays.toString(score));
输出结果分析：
原始数组：[100, 5, 25, 88, 8]第1次找到的最小结果坐标为：1第2次找到的最小结果坐标为：1第3次找到的最小结果坐标为：1第4次找到的最小结果坐标为：1此次找到最小值为：5第1次[排序]结果：[5, 100, 25, 88, 8]第1次找到的最小结果坐标为：2第2次找到的最小结果坐标为：2第3次找到的最小结果坐标为：4此次找到最小值为：8第2次[排序]结果：[5, 8, 25, 88, 100]第1次找到的最小结果坐标为：2第2次找到的最小结果坐标为：2此次找到最小值为：25第3次[排序]结果：[5, 8, 25, 88, 100]第1次找到的最小结果坐标为：3此次找到最小值为：88第4次[排序]结果：[5, 8, 25, 88, 100]此次找到最小值为：100第5次[排序]结果：[5, 8, 25, 88, 100]排序后：[5, 8, 25, 88, 100]
学习算法不光是为了提高我们的技术水平更是一种提高思维能力的过程。一起加油吧！