冒泡，选择，插入，希尔，归并，快速排序大合集，面试收藏必备( 二 ) _快速排序

文章插图

代码实现：

/*** 希尔排序* @author 溪云阁* @param arrays void* 希尔排序是插入排序的改进版，* 它将数组按照约定的数量分成N列，对每一列执行插入排序，接着缩小步长* 不断重复这过程，最后整个表就只有一列了*/public static void shellSort(int[] arrays) {if (arrays == null || arrays.length <= 1) {return;} else {// 增量int incrementNum = arrays.length / 2;while (incrementNum >= 1) {for (int i = 0; i < arrays.length; i++) {// 进行插入排序for (int j = i; j < arrays.length - incrementNum; j = j + incrementNum) {if (arrays[j] > arrays[j + incrementNum]) {final int temple = arrays[j];arrays[j] = arrays[j + incrementNum];arrays[j + incrementNum] = temple;}}}// 设置新的增量incrementNum = incrementNum / 2;}}}

归并排序原理：归并其实就是分而治之的思想，对于每一个数组，每个递归过程涉及三个步骤
1、分解:：把待排序的 n 个元素的序列分解成两个子序列, 每个子序列包括 n/2 个元素.
2、治理:：对每个子序列分别调用归并排序MergeSort, 进行递归操作
3、合并：合并两个排好序的子序列,生成排序结果.

文章插图

代码实现：

/*** 两路归并算法，两个排好序的子序列合并为一个子序列* @author 溪云阁* @param a* @param left* @param mid* @param right void*/public static void merge(int[] a, int left, int mid, int right) {// 辅助数组final int[] tmp = new int[a.length];// p1、p2是检测指针，k是存放指针int p1 = left, p2 = mid + 1, k = left;while (p1 <= mid && p2 <= right) {if (a[p1] <= a[p2])tmp[k++] = a[p1++];elsetmp[k++] = a[p2++];}while (p1 <= mid) {// 如果第一个序列未检测完，直接将后面所有元素加到合并的序列中tmp[k++] = a[p1++];}while (p2 <= right) {// 同上tmp[k++] = a[p2++];}// 复制回原素组for (int i = left; i <= right; i++) {a[i] = tmp[i];}}/*** 归并排序* @author 溪云阁* @param a* @param start* @param end void*/public static void mergeSort(int[] a, int start, int end) {// 当子序列中只有一个元素时结束递归if (start < end) {// 划分子序列final int mid = (start + end) / 2;// 对左侧子序列进行递归排序mergeSort(a, start, mid);// 对右侧子序列进行递归排序mergeSort(a, mid + 1, end);// 合并merge(a, start, mid, end);}}

快速排序原理：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

文章插图

代码实现：

/*** 快速排序* @author 溪云阁* @param arr待排序列* @param leftIndex待排序列起始位置* @param rightIndex 待排序列结束位置*/public static void quickSort(int[] arr, int leftIndex, int rightIndex) {if (leftIndex >= rightIndex) {return;} else {int left = leftIndex;int right = rightIndex;// 待排序的第一个元素作为基准值final int key = arr[left];// 从左右两边交替扫描，直到left = rightwhile (left < right) {while (right > left && arr[right] >= key) {// 从右往左扫描，找到第一个比基准值小的元素right--;}// 找到这种元素将arr[right]放入arr[left]中arr[left] = arr[right];while (left < right && arr[left] <= key) {// 从左往右扫描，找到第一个比基准值大的元素left++;}// 找到这种元素将arr[left]放入arr[right]中arr[right] = arr[left];}// 基准值归位arr[left] = key;// 对基准值左边的元素进行递归排序quickSort(arr, leftIndex, left - 1);// 对基准值右边的元素进行递归排序 。quickSort(arr, right + 1, rightIndex);}}

--END--
作者：@溪云阁
如需要源码，转发，关注后私信我。
部分图片来源网络，如侵权请联系删除，谢谢！