冒泡排序
冒泡排序是一个非常经典的排序方法，虽然其排序效率不是非常高，但是还是非常有必要了解一下其原理。
我认为了解一个算法之前，或是用java实现其之前，还是通过图示的方式来了解比较好，一张图印在脑海，写啥都不是事。
例如对于数组[10,1,35,61,89,36,55]，冒泡排序流程如下：
整个过程总结一下：
- 对于长度为n的数组来说，需要n-1趟排序。因为对于长度为n的数组来说，后n-1个元素确定了，第n个肯定是确定的，因此n-1趟排序即可完成所有元素的排序。
- 每一趟所做的事情就是从0元素开始，每两两比较，将小的那个放前面，也就是0跟1比，1跟2比。。。
- 对于第i趟排序来说，比较的次数为n-i。因为针对冒泡排序来说，每两个元素比较，大的元素会往后放，因此第一趟排序结束，最大的元素会放到数组末位，同理第二趟排序会选出第二大的元素放在第二位，如此下去
下面开始写代码：
package com.ty.sort; public class BubbleSort { public static void bubbleSort(int[] arr) { //数组一共N个元素，总排序趟数一共为N - 1 for(int i = 0; i < arr.length - 1; i++) { //第一趟排序需要做N - 1 = N - (i + 1)次比较。注：因为i是从0开始，趟是从1开始，所以趟=i + 1 for(int j = 0; j < arr.length - i - 1; j++) { //如果左边的>右边的，则交换位置 if(arr[j] > arr[j + 1]) { //引入一个暂时变量，可以想象两个萝卜交换坑，可以需要另一个空的坑 int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } } } }
以上冒泡排序也会存在一个问题，比如一共需要8趟排序，第6趟的时候数组已经有序，那么后面2趟的排序就多余了，增加一个标志优化：
package arithmetic.com.ty.binary; import java.util.Arrays; public class BubbleSort { public static void sort(int array[]) { for(int i = 0; i < array.length - 1; i++) { //有序标记，每一轮的初始值都是true boolean isSorted = true; for(int j = 0; j < array.length - i - 1; j++) { int tmp = 0; if(array[j] > array[j+1]) { tmp = array[j]; array[j] = array[j+1]; array[j+1] = tmp; //因为有元素进行交换，所以不是有序的，标记变为false isSorted = false; } } if(isSorted) { break; } } } public static void main(String[] args) { int[] array = new int[] { 5, 8, 6, 3, 9, 2, 1, 7 }; sort(array); System.out.println(Arrays.toString(array)); } }
鸡尾酒排序
假如对于数组{2,3,4,5,6,7,8,1}，使用冒泡排序的话非常浪费时间，因为前面7个元素都是有序的，鸡尾酒排序步骤如下：
2、此时开始不一样了，我们反过来从右往左比较并进行交换。
3、第3轮（虽然实际上已经有序，但是流程并没有结束）
package arithmetic.com.ty.binary; import java.util.Arrays; public class CocktailSort { public static void sort(int array[]) { int tmp = 0; for (int i = 0; i < array.length / 2; i++) { // 有序标记，每一轮的初始值都是true boolean isSorted = true; // 奇数轮，从左向右比较和交换 for (int j = i; j < array.length - i - 1; j++) { if (array[j] > array[j + 1]) { tmp = array[j]; array[j] = array[j + 1]; array[j + 1] = tmp; // 有元素交换，所以不是有序的，标记变为false isSorted = false; } } if (isSorted) { break; } // 在偶数轮之前，将isSorted重新标记为true isSorted = true; // 偶数轮，从右向左比较和交换 for (int j = array.length - i - 1; j > i; j--) { if (array[j] < array[j - 1]) { tmp = array[j]; array[j] = array[j - 1]; array[j - 1] = tmp; // 因为有元素进行交换，所以不是有序的，标记变为 false isSorted = false; } } if (isSorted) { break; } } } public static void main(String[] args) { int[] array = new int[] { 2, 3, 4, 5, 6, 7, 8, 1 }; sort(array); System.out.println(Arrays.toString(array)); } }
选择排序
原理
选择排序原理即是，遍历元素找到一个最小（或最大）的元素，把它放在第一个位置，然后再在剩余元素中找到最小（或最大）的元素，把它放在第二个位置，依次下去，完成排序。
过程
时间复杂度
选择排序的时间复杂度为 O(n2)。第一次需要检查n个元素，但随后检查的元素数依次为n - 1, n – 2, …, 2和1。平均每次检查的元素数为1/2 * n， 因此运行时间为 n * 1/2 * n，简单地写作 O(n^2)。
代码实现
原理：-----每次选择出最小的元素放在对应位置上。例如第一次选出最小的放在下标0上，第二次选出剩余最小的放在下标1上。
1、对于第一个循环，每次循环就是找到对应位置上最小的值，例如最小的放在0处，第二小的放在1处，如此循环。下标一共有array.length-1个，确定前array.length-2个位置的元素储存，最后一个肯定是确定的，因此循环array.length-1次即可；
2、对于确定每个i位置上的元素，需要与数组后所有元素比较，得到最小值，开始下标则为i；
3、默认将最小值下标设为i，然后挨个对比，用真实最小值覆盖；
4、这样经过array.length-1次循环后，所有位置上的元素即可排序正确。
Java 的选择排序示例如下：
public class SortDemo { public static void main(String[] args) { int[] arr = new int[] { 5, 3, 6, 2, 10, 2, 1 }; selectSort(arr); for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } } public static void selectSort(int[] arr) { for (int i = 0; i < arr.length - 1; i++) { int minIndex = i; // 用来记录最小值的索引位置，默认值为i for (int j = i + 1; j < arr.length; j++) { if (arr[j] < arr[minIndex]) { minIndex = j; // 遍历 i+1~length 的值，找到其中最小值的位置 } } // 交换当前索引 i 和最小值索引 minIndex 两处的值 if (i != minIndex) { int temp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = temp; } // 执行完一次循环，当前索引 i 处的值为最小值，直到循环结束即可完成排序 } } }
插入排序
原理
在要排序的一组数中，假定前n-1个数已经排好序，现在将第n个数插到前面的有序数列中，使得这n个数也是排好顺序的。如此反复循环，直到全部排好顺序。
过程
用一个动图看的更清楚：
图解：根据其原理，我们把该无序数列看成两个部分，我们不难看出图中，首先我们把第一位3看成是有序数列，剩下的作为无序数列，因为要把后面的无序数列中的数插入到前面有序数列，所以依次把后面的数抽出，在前面找到合适位置插入。如图，先抽出44，与前面比较，比3大放在3后面，再抽出38，与前面比较，比44小，比3大，所以插入到3后面。依次类推，直到最后的一个数也插入到前面的有序数列中。
时间复杂度
O(n2)
代码实现
原理：-----假定前n个元素是有序的
1、假设前i个数组元素是有序的，因为第一个元素肯定是有序的，因此从第二个元素开始，与其比较，如果比他小，则交换，这样前两个元素就是有序的了；
2、接着到第三个元素，分别与第一、二个元素进行比较，插入到合适的位置。
public static void insert_sort(int array[],int lenth){ int temp; for(int i=0;i<lenth-1;i++){ for(int j=i+1;j>0;j--){ if(array[j] < array[j-1]){ temp = array[j-1]; array[j-1] = array[j]; array[j] = temp; }else{ //不需要交换 break; } } } }
快速排序
原理-----分治
- 先从数列中取出一个数作为key值；
- 将比这个数小的数全部放在它的左边，大于或等于它的数全部放在它的右边；
- 对左右两个小数列重复第二步，直至各区间只有1个数。
过程
方法其实很简单：分别从初始序列“6 1 2 7 9 3 4 5 10 8”两端开始“探测”。先从右往左找一个小于6的数，再从左往右找一个大于6的数，然后交换他们。这里可以用两个变量i和j，分别指向序列最左边和最右边。我们为这两个变量起个好听的名字“哨兵i”和“哨兵j”。刚开始的时候让哨兵i指向序列的最左边（即i=1），指向数字6。让哨兵j指向序列的最右边（即=10），指向数字。
首先哨兵j开始出动。因为此处设置的基准数是最左边的数，所以需要让哨兵j先出动，这一点非常重要（请自己想一想为什么）。哨兵j一步一步地向左挪动（即j–），直到找到一个小于6的数停下来。接下来哨兵i再一步一步向右挪动（即i++），直到找到一个数大于6的数停下来。最后哨兵j停在了数字5面前，哨兵i停在了数字7面前。
现在交换哨兵i和哨兵j所指向的元素的值。交换之后的序列如下：
6 1 2 5 9 3 4 7 10 8
到此，第一次交换结束。接下来开始哨兵j继续向左挪动（再友情提醒，每次必须是哨兵j先出发）。他发现了4（比基准数6要小，满足要求）之后停了下来。哨兵i也继续向右挪动的，他发现了9（比基准数6要大，满足要求）之后停了下来。此时再次进行交换，交换之后的序列如下：
6 1 2 5 4 3 9 7 10 8
第二次交换结束，“探测”继续。哨兵j继续向左挪动，他发现了3（比基准数6要小，满足要求）之后又停了下来。哨兵i继续向右移动，糟啦！此时哨兵i和哨兵j相遇了，哨兵i和哨兵j都走到3面前。说明此时“探测”结束。我们将基准数6和3进行交换。交换之后的序列如下：
3 1 2 5 4 6 9 7 10 8
到此第一轮“探测”真正结束。此时以基准数6为分界点，6左边的数都小于等于6，6右边的数都大于等于6。回顾一下刚才的过程，其实哨兵j的使命就是要找小于基准数的数，而哨兵i的使命就是要找大于基准数的数，直到i和j碰头为止。
OK，解释完毕。现在基准数6已经归位，它正好处在序列的第6位。此时我们已经将原来的序列，以6为分界点拆分成了两个序列，左边的序列是“3 1 2 5 4”，右边的序列是“9 7 10 8”。接下来还需要分别处理这两个序列。因为6左边和右边的序列目前都还是很混乱的。不过不要紧，我们已经掌握了方法，接下来只要模拟刚才的方法分别处理6左边和右边的序列即可。现在先来处理6左边的序列现吧。
左边的序列是“3 1 2 5 4”。请将这个序列以3为基准数进行调整，使得3左边的数都小于等于3，3右边的数都大于等于3。好了开始动笔吧
如果你模拟的没有错，调整完毕之后的序列的顺序应该是：
2 1 3 5 4
OK，现在3已经归位。接下来需要处理3左边的序列“2 1”和右边的序列“5 4”。对序列“2 1”以2为基准数进行调整，处理完毕之后的序列为“1 2”，到此2已经归位。序列“1”只有一个数，也不需要进行任何处理。至此我们对序列“2 1”已全部处理完毕，得到序列是“1 2”。序列“5 4”的处理也仿照此方法，最后得到的序列如下：
1 2 3 4 5 6 9 7 10 8
对于序列“9 7 10 8”也模拟刚才的过程，直到不可拆分出新的子序列为止。最终将会得到这样的序列，如下
1 2 3 4 5 6 7 8 9 10
到此，排序完全结束。细心的同学可能已经发现，快速排序的每一轮处理其实就是将这一轮的基准数归位，直到所有的数都归位为止，排序就结束了。下面上个霸气的图来描述下整个算法的处理过程。
这是为什么呢？
快速排序之所比较快，因为相比冒泡排序，每次交换是跳跃式的。每次排序的时候设置一个基准点，将小于等于基准点的数全部放到基准点的左边，将大于等于基准点的数全部放到基准点的右边。这样在每次交换的时候就不会像冒泡排序一样每次只能在相邻的数之间进行交换，交换的距离就大的多了。因此总的比较和交换次数就少了，速度自然就提高了。当然在最坏的情况下，仍可能是相邻的两个数进行了交换。因此快速排序的最差时间复杂度和冒泡排序是一样的都是O(N2)，它的平均时间复杂度为O(NlogN)。其实快速排序是基于一种叫做“二分”的思想。我们后面还会遇到“二分”思想，到时候再聊。先上代码，如下
时间复杂度
O(nlogn)
代码实现
package arithmetic.com.ty.binary; import java.util.Arrays; public class QuickSort { public static void quickSort(int[] arr, int low, int high) { //当数组中只有一个元素时，为终止条件。low == high，说明只有一个元素，low > high只是为了健壮性，不允许low > high if (low >= high) { return; } int base = arr[low]; //low、high在一个循环里不会更改，因此引入i、j两个变量，初始值为low、high int i = low; int j = high; // 使用双指针，i指针需要小于j指针。i指针从左往右，j指针从右往左。 while (i < j) { // 从右向左，找到第一个小于base的下标，如果大于base，继续往左找 while (base <= arr[j] && i < j) { j--; } // 从左到右，找到第一个大于base的下标，如果小于base，继续往右找 while (base >= arr[i] && i < j) { i++; } // 如果此时i<j，则交换两个位置的值 if (i < j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } // 由于i每次都是+1，j每次都是-1，因此到这说明i == j。这时候需要把base数跟当前的数交换，这样在base左边的数全部小于base，在base右边的全部大于base arr[low] = arr[i]; arr[i] = base; // 以base值下标为分界，左右分别递归，继续拆分，直到数组中只有一个元素即可。 quickSort(arr, low, i - 1); quickSort(arr, i + 1, high); } public static void main(String[] args) { int[] arr = { 9, 7, 2, 4, 7, 62, 3, 4, 2, 1, 8, 9, 19 }; quickSort(arr, 0, arr.length - 1); System.out.println(Arrays.toString(arr)); } }