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²+n+6，则(去掉常数项和最高次项的系数等)只保留最大次幂也就是O(n²)；
如下图所示，若在循环中第三个表达式（循环变量修正表达式）为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)");}
【快速排序】
快速排序（Quicksort）又称分区交换排序，最早由东尼·霍尔提出的一种不稳定排序算法。快速排序通常明显比其他算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地达成。
快速排序使用分治法策略根据基准值把序列分为较小和较大的2个子序列，然后递归地排序两个子序列，选取基准值的方法对排序的时间性能有决定性影响。
原理：
从数列中挑出一个元素，称为“基准”（pivot）
所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面，与基准值相等的数可随意放。
递归地将小于基准值元素的子序列和大于基准值元素的子序列排序。
4. 判断需要递归的数列大小是0或1时，排序完成。
1）main方法
//快速排序int score[] = { 5,100,520,88,8 };System.out.println("原始数组："+ Arrays.toString(score));//参数：序列,leftIndex,rightIndexquickSort(score, 0, score.length - 1);System.out.println("排序后：" + Arrays.toString(score));
2）quickSort()方法：大方向上分成两段排序
public static void quickSort(int[] score, int left, int right) {if (left < right) {//获取基准值int middle = getMiddle(score, left, right);// 对大左侧进行递归排序quickSort(score, left, middle - 1);// 对大右侧进行递归排序quickSort(score, middle + 1, right);}}
3）getMiddle()方法获取基准值
public static int getMiddle(int[] score, int left, int right) {// 数组的左侧第一个数作为中轴int temp = score[left];//遍历数组：循环移动中轴角标到右侧while (left < right) {while (left < right && score[right] >= temp) {//右侧角标左移一位，以便比较下一个角标位置System.out.println("1.比较基准"+temp+"和"+score[right]+"没发生交换");right--;}score[left] = score[right];while (left < right && score[left] <= temp) {System.out.println("2.比较基准"+temp+"和"+score[left]+"没发生交换");left++;}score[right] = score[left];}System.out.println("新基准"+temp+"赋值给最左侧"+"，角标："+left+"\n");score[left] = temp;return left; //返回新基准的角标}
输出结果：
原始数组：[5, 100, 520, 88, 8]1】比较基准5和8没发生交换1】比较基准5和88没发生交换1】比较基准5和520没发生交换1】比较基准5和100没发生交换新基准5赋值给最左侧，角标：02】比较基准100和8没发生交换1】比较基准100和520没发生交换2】比较基准100和88没发生交换新基准100赋值给最左侧，角标：31】比较基准8和88没发生交换新基准8赋值给最左侧，角标：1排序后：[5, 8, 88, 100, 520]
不稳定因素是在基准元素和score[index]交换的时候，很有可能把前面的元素的稳定性打乱。比如序列为 5 4 2 0 1 2 ，现在基准元素5和最右侧的2交换就会把第三个元素“2”的稳定性打乱，所以快速排序是一个不稳定的排序算法。
【直接排序】
直接排序（也叫选择排序）是一种不稳定的排序算法，并且使用直接排序无论什么数据进去都是O(n²)的时间复杂度，所以数据规模越小效果越好。
原理：首先在未排序序列中找到最小（最大）元素，存放在排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，再放到已排序序列的末尾，以此类推，直到所有元素均排序完毕。
【代码说明】
//直接排序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]
学习算法不光是为了提高我们的技术水平更是一种提高思维能力的过程。一起加油吧！