Android 程序员经常遇到的算法问题，七大常用的算法，小白看完都会了

return arr;}

// 分水岭,基位,左边的都比这个位置小,右边的都大 private int partition(int[] arr, int low, int heigh) {int base = arr[low]; //用子表的第一个记录做枢轴(分水岭)记录 while (low < heigh) { //从表的两端交替向中间扫描 while (low < heigh && arr[heigh] >= base) {heigh--;}// base 赋值给 当前 heigh 位,base 挪到(互换)到了这里,heigh 位右边的都比 base 大 swap(arr, heigh, low);while (low < heigh && arr[low] <= base) {low++;}// 遇到左边比 base 值大的了,换位置 swap(arr, heigh, low);}// now low = heigh;return low;}

private void swap(int[] arr, int a, int b) {int temp;temp = arr[a];arr[a] = arr[b];arr[b] = temp;}

5.合并排序算法

归并排序采用的是递归来实现，属于“分而治之”，将目标数组从中间一分为二，之后分别对这两个数组进行排序，排序完毕之后再将排好序的两个数组“归并”到一起，归并排序最重要的也就是这个“归并”的过程，归并的过程中需要额外的跟需要归并的两个数组长度一致的空间

/**

• @param int[] 未排序数组

• @return int[] 排完序数组*/private int[] sort(int[] nums, int low, int high) {int mid = (low + high) / 2;if (low < high) {// 左边 sort(nums, low, mid);// 右边 sort(nums, mid + 1, high);// 左右归并 merge(nums, low, mid, high);}return nums;}private void merge(int[] nums, int low, in

《Android学习笔记总结+最新移动架构视频+大厂安卓面试真题+项目实战源码讲义》
浏览器打开：qq.cn.hn/FTe 免费领取

t mid, int high) {int[] temp = new int[high - low + 1];int i = low;// 左指针 int j = mid + 1;// 右指针 int k = 0;// 把较小的数先移到新数组中 while (i <= mid && j <= high) {if (nums[i] < nums[j]) {temp[k++] = nums[i++];} else {temp[k++] = nums[j++];}}// 把左边剩余的数移入数组 while (i <= mid) {temp[k++] = nums[i++];}// 把右边边剩余的数移入数组 while (j <= high) {temp[k++] = nums[j++];}// 把新数组中的数覆盖 nums 数组 for (int k2 = 0; k2 < temp.length; k2++) {nums[k2 + low] = temp[k2];}}

public int[] sortMerge(int[] array) {return sort(array, 0, array.length - 1);}

6.希尔排序算法

希尔排序的诞生是由于插入排序在处理大规模数组的时候会遇到需要移动太多元素的问题。希尔排序的思想是将一个大的数组“分而治之”，划分为若干个小的数组，以 gap 来划分，比如数组 [1, 2, 3, 4, 5, 6, 7, 8] ，如果以 gap = 2 来划分，可以分为 [1, 3, 5, 7] 和 [2, 4, 6, 8] 两个数组（对应的，如 gap = 3 ， 则划分的数组为： [1, 4, 7] 、 [2, 5, 8] 、 [3, 6] ）然后分别对划分出来的数组进行插入排序，待各个子数组排序完毕之后再减小 gap 值重复进行之前的步骤，直至 gap = 1 ，即对整个数组进行插入排序，此时的数组已经基本上快排好序了，所以需要移动的元素会很小很小，解决了插入排序在处理大规模数组时较多移动次数的问题，

希尔排序是插入排序的改进版，在数据量大的时候对效率的提升帮助很大，数据量小的时候建议直接使用插入排序就好了。

/**

• @param int[] 未排序数组

• @return int[] 排完序数组*/

public int[] sortShell(int[] array) {// 取增量 int step = array.length / 2;while (step >= 1) {for (int i = step; i < array.length; i++) {int temp = array[i];int j = 0;// 跟插入排序的区别就在这里 for (j = i - step; j >= 0 && temp < array[j]; j -= step) {array[j + step] = array[j];}array[j + step] = temp;}step /= 2;}return array;}

7.堆排序算法

本质就是先构造一个大顶堆,parent 比 children 大,root 节点就是最大的节点 把最大的节点(root)与尾节点(最后一个节点,比较小)位置互换，剩下最后的尾节点,现在最大,其余的,从第一个元素开始到尾节点前一位,构造大顶堆递归。

/**

• @param int[] 未排序数组

• @return int[] 排完序数组*/public int[] sortHeap(int[] array) {buildHeap(array);// 构建堆 int n = array.length;int i = 0;for (i = n - 1; i >= 1; i--) {swap(array, 0, i);heapify(array, 0, i);}

return array;}

private void buildHeap(int[] array) {int n = array.length;// 数组中元素的个数 for (int i = n / 2 - 1; i >= 0; i--)heapify(array, i, n);}

private void heapify(int[] A, int idx, int max) {int left = 2 * idx + 1;// 左孩子的下标（如果存在的话）int right = 2 * idx + 2;// 左孩子的下标（如果存在的话）int largest = 0;// 寻找 3 个节点中最大值节点的下标 if (left < max && A[left] > A[idx])largest = left;elselargest = idx;if (right < max && A[right] > A[largest])largest = right;if (largest != idx) {swap(A, largest, idx);heapify(A, largest, max);}}}// 建堆函数，认为【s，m】中只有 s// 对应的关键字未满足大顶堆定义，通过调整使【s，m】成为大顶堆=====================================================public static void heapAdjust(int[] array, int s, int m) {// 用 0 下标元素作为暂存单元 array[0] = array[s];// 沿孩子较大的结点向下筛选 for (int j = 2 * s; j <= m; j *= 2) {// 保证 j 为较大孩子结点的下标，j < m 保证 j+1 <= m ，不越界 if (j < m && array[j] < array[j + 1]) {j++;}