leetcode算法
冒泡排序 冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为相关的元素会经由交换慢慢“浮”到数列的顶端。
基本思路：
1、比较相邻的元素。如果第一个比第二个大(小)，就交换它们两个；
2、对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大(小)数；
3、针对所有的元素重复以上的步骤，除了最后一个；
重复步骤1~2，直到排序完成。
图示 第一轮循环：
后面继续从头开始循环，直到所有的元素都排好位置为止。
代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 public static void main(String[] args) { int nums[] = {3,5,6,7,1,4,2,9}; for(int i = 0; i < nums.length; i++){ for(int j = 0; j < nums.length - 1 - i; j++){ int temp1 = nums[j]; int temp2 = nums[j+1]; if(temp1 > temp2){ int temp0 = nums[j]; nums[j] = nums[j+1]; nums[j+1] = temp0; } } } System.out.println(Arrays.toString(nums)); }
选择排序 选择排序的思想其实和冒泡排序有点类似，都是在一次排序后把最小的元素放到最前面。但是过程不同，冒泡排序是通过相邻的比较和交换。而选择排序是通过对整体的选择
其实选择排序可以看成冒泡排序的优化，因为其目的相同，只是选择排序只有在确定了最大（小）的前提下才进行交换，大大减少了交换的次数。
具体步骤：
首先，找到数组中最大（小）的那个元素；
其次，将它和数组的第一个元素交换位置（如果第一个元素就是最大（小）元素那么它就和自己交换）；
再次，在剩下的元素中找到最大（小）的元素，将它与数组的第二个元素交换位置。如此往复，直到将整个数组排序。
图示 原始数组：
如此重复，最后形成数组：
代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 public static int[] choose(int nums[]){ for(int i = 0; i < nums.length; i++){ int index = i; for(int j = i ; j < nums.length ; j++){ if(nums[j] < nums[index]){ index = j; } } int temp0 = nums[i]; nums[i] = nums[index]; nums[index] = temp0; } return nums; }
插入排序 插入排序不是通过交换位置而是通过比较找到合适的位置插入元素来达到排序的目的的。相信大家都看过打麻将，在摸牌的时候，拿到一张牌，找到一个合适的位置插入。举个例子，我们手里有3万,4万,6万,8万这几张牌，我们收到5万这张牌，把6万,8万往后移，然后把5万放到原理6万的位置，这个原理其实和插入排序是一样的。
具体步骤：
对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
为了给要插入的元素腾出空间，我们需要将插入位置之后的已排序元素在都向右移动一位。
插入排序所需的时间取决于输入中元素的初始顺序。例如，对一个很大且其中的元素已经有序（或接近有序）的数组进行排序将会比对随机顺序的数组或是逆序数组进行排序要快得多。
总的来说，插入排序对于部分有序的数组十分高效，也很适合小规模数组。
图示 原始数组：
我们总是认为原始数组的第一个元素已经是有序的了，于是从第二个元素开始进行排序。
第二个元素是L，比T小，所以将T后移一位，L插入T原来的位置
第三个元素是M，在已经排序的序列L、T中，L比M小，L不动，继续比较，T比M大，所以将T后移一位，M插入T原来的位置
第四个元素是A，在已经排序的序列LMT中，A比它们都下，应该排在最前面，所以将LMT全部后移一位，A插入L原来的位置。
如此重复，最后形成结果数组：
代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 public static int[] insert(int nums[]){ for(int i = 1; i < nums.length; i++){ // 需插入的数据 int temp = nums[i]; int j = i; // 从j 开始往前遍历 while (j > 0 && temp < nums[j - 1]){ // 交换 nums[j ] = nums[j- 1]; j --; } nums[j ] = temp; } return nums; }
希尔排序 一种基于插入排序的快速的排序算法(请大家先学习插入排序，了解基本的插入排序的思想。对于大规模乱序数组插入排序很慢，因为元素只能一点一点地从数组的一端移动到另一端。例如，如果主键最小的元素正好在数组的尽头，要将它挪到正确的位置就需要N-1 次移动。
希尔排序为了加快速度简单地改进了插入排序，也称为缩小增量排序，同时该算法是冲破O(n^2）的第一批算法之一。
希尔排序是把待排序数组按一定增量的分组，对每组使用直接插入排序算法排序；然后缩小增量继续分组排序，随着增量逐渐减少，每组包含的元素越来越多，当增量减至 1 时，整个数组恰被分成一组，排序便完成了。这个不断缩小的增量，就构成了一个增量序列。
图示
代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 public static int[] sort(int nums[]){ int len = nums.length; int gap = len/ 2; while (gap > 0){ for(int i = gap; i < len; i++){ // 需插入的数据 int temp = nums[i]; int preIndex = i - gap; // 从j 开始往前遍历 while (preIndex >= 0 && temp < nums[preIndex]){ // 交换 nums[preIndex + gap ] = nums[preIndex]; preIndex -= gap; } nums[preIndex + gap] = temp; } gap = gap / 2; } return nums; }
快速排序 排序算法的思想非常简单，在待排序的数列中，我们首先要找一个数字作为基准数（这只是个专用名词）。为了方便，我们一般选择第 1 个数字作为基准数（其实选择第几个并没有关系）。接下来我们需要把这个待排序的数列中小于基准数的元素移动到待排序的数列的左边，把大于基准数的元素移动到待排序的数列的右边。这时，左右两个分区的元素就相对有序了；接着把两个分区的元素分别按照上面两种方法继续对每个分区找出基准数，然后移动，直到各个分区只有一个数时为止。
这是典型的分治思想，即分治法。下面我们对一个实际例子进行算法描述，讲解快速排序的排序步骤。
以 47、29、71、99、78、19、24、47 的待排序的数列为例进行排序，为了方便区分两个 47，我们对后面的 47 增加一个下画线，即待排序的数列为 47、29、71、99、78、19、24、47。
首先我们需要在数列中选择一个基准数，我们一般会选择中间的一个数或者头尾的数，这里直接选择第 1 个数 47 作为基准数，接着把比 47 小的数字移动到左边，把比 47 大的数字移动到右边，对于相等的数字不做移动。所以实际上我们需要找到中间的某个位置 k，这样 k 左边的值全部比 k 上的值小，k 右边的值全部比 k 上的值大。
接下来开始移动元素。怎么移动呢？其实冒泡排序也涉及对元素的移动，但是那样移动起来很累，比如把最后一个元素移动到第 1 个，就需要比较 n-1 次，同时交换 n-1 次，效率很低。其实，只需把第 1 个元素和最后一个元素交换就好了，这种思想是不是在排序时可以借鉴呢？之前说快速排序就是对冒泡排序的一个改进，就是这个原因。
快速排序的操作是这样的：首先从数列的右边开始往左边找，我们设这个下标为 i，也就是进行减减操作（i–），找到第 1 个比基准数小的值，让它与基准值交换；接着从左边开始往右边找，设这个下标为 j，然后执行加加操作（j++），找到第 1 个比基准数大的值，让它与基准值交换；然后继续寻找，直到 i 与 j 相遇时结束，最后基准值所在的位置即 k 的位置，也就是说 k 左边的值均比 k 上的值小，而 k 右边的值都比 k 上的值大。
所以对于上面的数列 47、29、71、99、78、19、24、47，进行第 1 趟第 1 个交换的排序情况如下，第 1 次的操作情况如图 1 所示。
图示
图 1 第 1 次发现可以交换的数
交换之后，j 移动到了下标为 6 的位置，对 i 继续扫描，如图 2 所示。
此时交换后的数列变为 24、29、47、99、78、19、71、47。接下来我们继续对 i、j 进行操作，如图 3 所示，继续进行 i– 及 j++ 的比较操作。
进行了这两次 i、j 的移动、比较、交换之后，我们最终得到的数列是 24、29、19、47、78、99、71、47。接下来我们继续进行 i– 的操作，发现在 i 为 4 时比 47 大不用交换，在 i 为 3 时与 j 相遇，这时就不需要继续移动、比较了，已经找到 k 了，并且 k 的值为 3。我们可以确认一下当前的数列是不是 k 左边的值都比 47 小，而 k 右边的值都比 47 大（由于要保持相对位置不变，所以 47 同样在基准值 47 的右边）。
47 这个值已经落到了它该在的位置，第 1 趟排序完成了。
代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 public static int[] quick(int nums[], int start, int end){ // 基准数 if(start < end){ int temp = nums[start]; int i = start; int j = end; while (i < j){ while (i < j && nums[j] > temp){ j--; } if(i < j ){ nums[i] = nums[j]; i++; } while (i < j && nums[i] < temp){ i++; } if(i < j ){ nums[j] = nums[i]; j--; } } nums[i] = temp; quick( nums, start, i - 1); quick( nums, i + 1, end); } return nums; }
归并排序 归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。
若将两个有序表合并成一个有序表，称为2-路归并，与之对应的还有多路归并。
对于给定的一组数据，利用递归与分治技术将数据序列划分成为越来越小的半子表，在对半子表排序后，再用递归方法将排好序的半子表合并成为越来越大的有序序列。
为了提升性能，有时我们在半子表的个数小于某个数（比如15）的情况下，对半子表的排序采用其他排序算法，比如插入排序。
图示
代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 // 归并 public static int[] mergeSor(int nums[]){ if(nums.length < 2) return nums; // 切分数组 int mid = nums.length / 2; int [] left = Arrays.copyOfRange(nums, 0, mid); int [] right = Arrays.copyOfRange(nums, mid, nums.length); return merge(mergeSor(left), mergeSor(right)); } // 归并排序 public static int[] merge(int left[], int []right){ int result[] = new int[left.length + right.length]; for(int index = 0, i = 0, j = 0; index < result.length; index++){ if(i >= left.length){ // 左边已经取完 result[index] = right[j++]; }else if(j >= right.length){ // 右边已经取完 result[index] = left[i++]; }else if(left[i] > right[j]){ result[index] = left[i++]; }else { result[index] = right[j++]; } } return result; }
堆排序 许多应用程序都需要处理有序的元素，但不一定要求他们全部有序，或者不一定要一次就将他们排序，很多时候，我们每次只需要操作数据中的最大元素（最小元素），那么有一种基于二叉堆的数据结构可以提供支持。
所谓二叉堆，是一个完全二叉树的结构，同时满足堆的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。在一个二叉堆中，根节点总是最大（或者最小）节点。
这就是一个典型的二叉堆。
堆排序算法就是抓住了这一特点，每次都取堆顶的元素，然后将剩余的元素重新调整为最大（最小）堆，依次类推，最终得到排序的序列。
图示
将该数组视为一个完全二叉树 ，则是：
堆的初始化 很明显，这个二叉树不符合最大堆的定义，需要初始化为最大堆，从最后一个非叶节点 开始，从下到上，从右到左调整
最后一个非叶节点在8/2-1=3的位置，也就是值为9的元素，将它和自己的叶节点进行比较并交换
48和63调整到位后，进而调整根节点35，
将35和它的子结点86交换，此时86变成根结点，35则变成子结点。很明显35和11、63组成的树不符合二叉堆的定义，此时需要再次调整35的位置：
此时就完成了堆的初始化，最大的数已经成为了根节点 。
正式开始堆排序的过程
此时将堆顶的86和尾元素9交换
86现在处于数组下标为7的位置，不再将86视为二叉树的一部分。9处于根结点，很明显，此时需要调整元素的位置 使之重新变成二叉堆
继续将堆顶63和尾元素48交换，63现在处于数组下标为6的位置，不再将63视为二叉树的一部分。48处于根结点，很明显，此时需要调整元素的位置 使之重新变成二叉堆
代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 private static int len; public static void main(String[] args) { int nums[] = {3,5,6,7,1,4,2,9}; // 选择 System.out.println(Arrays.toString(heapArray( nums))); } // 堆排序 public static void swap(int array[], int i, int j){ int temp = array[i]; array[i] = array[j]; array[j] = temp; } public static int[] heapArray(int[] nums){ len = nums.length; if(len < 1) return nums; // 构建最大堆 buildMaxheap(nums); // 循环将堆首位(最大值）与末排序数组末位交换，然后重新调整为最大堆 while (len > 0) { swap(nums, 0, len - 1); len--; adjustHeap(nums, 0); } return nums; } public static void buildMaxheap(int [] array){ // 从最后一个非叶子节点开始向上构造最大堆 for(int i = len / 2 - 1; i >= 0; i--){ adjustHeap(array, i); } } // 调整成最大堆 public static void adjustHeap(int [] array, int i){ int maxIndex = i; int left = 2 * i + 1; int right = 2 * (i + 1); // 如果有左子树， 且左子树大于父节点， 则将最大指针指向左子树 if(left < len && array[left] > array[maxIndex]){ maxIndex = left; } // 如果有右子树， 且右子树大于父节点且大于左子树， 则将最大指针指向右子树 if(right < len && array[right] > array[maxIndex] && array[right] > array[left]){ maxIndex = right; } // 如果父节点不是最大值， 则将父节点与最大值交换， 并且递归调整与父节点交换的位置 if(maxIndex != i){ swap(array, maxIndex,i); adjustHeap(array, maxIndex); } }
桶排序 桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，利用某种函数的映射关系将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序）。
基本步骤是：
根据输入建立适当个数的桶，每个桶可以存放某个范围内的元素；
将落在特定范围内的所有元素放入对应的桶中；
对每个非空的桶中元素进行排序，可以选择通用的排序方法，比如插入、快排
按照划分的范围顺序，将桶中的元素依次取出。排序完成。
桶排序利用函数的映射关系，减少了几乎所有的比较工作。实际上，桶排序的f(k)值的计算，其作用就相当于快排中划分，已经把大量数据分割成了基本有序的数据块(桶)。然后只需要对桶中的少量数据做先进的比较排序即可。
图示
我们可以建立5个桶，每个桶按范围顺序依次是[0, 10)、[10, 20)……[40, 50)，注意是左闭右开区间，对于待排序数组，5,9会被放到[0, 10)这个桶中，…….，48会被放到[40, 50)这个桶中
对这5个桶中的元素分别排序。 依次取出5个桶中元素，得到排序后的序列。
在桶排序中保证元素均匀分布到各个桶尤为关键。举个反例，有数组[0, 9, 4, 5, 8, 7, 6, 3, 2, 1]要排序，它们都是10以下的数，如果还按照上面的范围[0, 10)建立桶，全部的元素将进入同一个桶中，此时桶排序就失去了意义。实际情况我们很可能事先就不知道输入数据是什么，为了保证元素均匀分不到各个桶中，需要建立多少个桶，每个桶的范围是多少呢？
其实我们可以这样：简单点，首先限定桶的容量，再根据元素的个数来决定桶的个数。当然使用更复杂的方法也是可以的。
桶排序利用函数的映射关系，减少了几乎所有的比较工作。实际上，桶排序的f(k)值的计算，其作用就相当于快排中划分，已经把大量数据分割成了基本有序的数据块(桶)。然后只需要对桶中的少量数据做先进的比较排序即可。
代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 public class Bucket { public static void main(String[] args) { ArrayList<Integer> array = new ArrayList<>(); array.add(86); array.add(11); array.add(77); array.add(23); array.add(32); array.add(45); array.add(58); array.add(63); array.add(93); array.add(4); array.add(37); array.add(22); System.out.println("=============="); ArrayList<Integer> dest = Bucket.sort(array, 2); dest.stream().forEach(item -> System.out.println(item)); } public static ArrayList<Integer> sort(ArrayList<Integer> array, int bucketCap){ if(array == null || array.size() < 2 ){ return array; } int max = array.get(0), min = array.get(0); // 找到最大值和最小值 for(int i = 0; i < array.size(); i++){ if(array.get(i) > max){ max = array.get(i); } if(array.get(i) < min){ min = array.get(i); } } // 获取桶的数量 int bucketCount = (max - min ) / bucketCap + 1; // 构建桶 ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketCount); ArrayList<Integer> resultArr = new ArrayList<>(); for(int i = 0; i< bucketCount; i++){ bucketArr.add(new ArrayList<>()); } // 将原数组中的数据分配到桶中 for(int i = 0; i < array.size(); i++){ bucketArr.get((array.get(i) - min) / bucketCap).add(array.get(i)); } // 看看桶中数据分布 for(int i = 0; i < bucketArr.size(); i++){ System.out.println("第" +i+ "个桶包含数据： "); bucketArr.get(i).stream().forEach(item -> System.out.println(item)); } for(int i = 0; i < bucketCount; i++){ // bucketArr.get(i).sort(null); for (int value : bucketArr.get(i)) { resultArr.add(value); } } return resultArr; } }
基数排序 常见的数据元素一般是由若干位组成的，比如字符串由若干字符组成，整数由若干位0~9数字组成。基数排序按照从右往左的顺序，依次将每一位都当做一次关键字，然后按照该关键字对数组的元素入桶，每一轮入桶都基于上轮入桶的结果；完成所有位的入桶后，整个数组就达到有序状态。比如对于数字2985，从右往左就是先以个位为关键字进行入桶，然后是十位、百位、千位，总共需要四轮。基数排序也是一种无需比较的排序算法。
基数是什么意思？对于十进制整数，每一位都只可能是0~9中的某一个，总共10种可能。那10就是它的基，同理二进制数字的基为2；对于字符串，如果它使用的是8位的扩展ASCII字符集，那么它的基就是256。
图示
首先按个位排序
然后再按十位进行排序
代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 public class Base { public static void main(String[] args) { ArrayList<Integer> array = new ArrayList<>(); array.add(86); array.add(11); array.add(77); array.add(23); array.add(32); array.add(45); array.add(58); array.add(63); array.add(93); array.add(4); array.add(37); array.add(22); System.out.println("=============="); baseSort(array); array.stream().forEach(item -> System.out.println(item)); } public static void baseSort(ArrayList<Integer> array){ // 计算桶的数量 int max = 0; for(int value : array){ if(value > max) max = value; } //桶的数量 int bucketCount = 0; while (max != 0){ max /= 10; bucketCount++; } int mod = 10, div = 1; // 构建桶 ArrayList<ArrayList<Integer>> bucketList = new ArrayList<>(10); for(int i = 0; i < 10; i++){ bucketList.add(new ArrayList<>()); } for(int i = 0; i < bucketCount; i++, mod *= 10, div *= 10){ // 遍历入桶 for(int j = 0; j < array.size(); j++){ int num = (array.get(j) % mod ) / div; bucketList.get(num).add(array.get(j)); } // 桶中的数据写回原始数组，清除桶，准备下一轮的排序 array.clear(); for(int j = 0; j < bucketList.size(); j++){ for(int k =0; k < bucketList.get(j).size(); k++){ array.add(bucketList.get(j).get(k)) ; bucketList.get(j).clear(); } } } } }
排序算法总结
