合并排序与快速排序是排序算法中常用的两种排序算法，合并排序把数据分为两段，从两段中逐个选最小的元素移入新数据的末尾；快速排序是在序列中挑选一个元素（本文中为首位元素），将小于该元素的放在该元素之前，大于的放于该元素之后，再分别对元素前后两段序列进行排序。
实现思路： 将数组通过折中不断细分成若干子序列，对最短两元素的子序列进行两两比较后得到若干有序序列，不断两两合并这些子序列，并通过比较两个序列首部元素大小进行排列，最终合并得到有序的序列。
时间复杂度： O(nlogn)
空间复杂度： O(n)
代码如下：
public static void mergeSort(int[] arr, int left, int right) {
if (left < right) {
int i = (left + right) / 2;
//递归调用，对左侧进行排序
mergeSort(arr, left, i);
//递归调用，对右侧进行排序
mergeSort(arr, i + 1, right);
merge(arr, left, i, right);
}
}
//arr[1:m] arr[m+1:r]
public static void merge(int[] arr, int l, int m, int r) {
int len1 = m - l + 1;
int len2 = r - m;
//构造数组left，right分别存储左右侧元素
int[] left = new int[len1];
int[] right = new int[len2];
for (int n1 = 0; n1 < len1; n1++) {
left[n1] = arr[l + n1];
}
for (int n1 = 0; n1 < len2; n1++) {
right[n1] = arr[m + 1 + n1];
}
int i = 0, j = 0;
int k = l;
//将数组元素值两两比较，并合并到arr数组相应位置
while (i < len1 && j < len2)
{
if (left[i] <= right[j])
arr[k++] = left[i++];
else
arr[k++] = right[j++];
}
//判断超出部分并进行拼接
if (i >= len1) {
for (int n1 = j; n1 < len2; n1++) {
arr[k++] = right[n1];
}
}
if (j >= len2) {
for (int n1 = i; n1 < len1; n1++) {
arr[k++] = left[n1];
}
}
}
实现思路： 将数组头部元素与后续元素进行比较，通过首尾双指针（首指针找大于头部元素的元素，尾指针找小于头部元素的元素，找到则进行交换，直到首指针等于尾指针，最后将头部元素与首指针元素进行交换）使得头部元素（已换位）前的元素均小于自身，后的元素均大于自身，然后对头部元素（已换位）前的元素子序列、后的元素子序列不断重复以上过程，直到子序列长度等于1。
时间复杂度： O(nlogn)
空间复杂度： O(logn)
代码如下：
public static void quickSort(int[] arr, int begin, int end) {
//长度小于1结束递归
if (begin > end) {
return;
}
int tmp = arr[begin];
int i = begin, j = end;
//首指针i等于尾指针j结束循环
while (i != j) {
//j在前面，因为尾指针j先出发
//从后往前找，直到找到比tmp小的元素
while (arr[j] >= tmp && i < j) {
j--;
}
//从前往后找，直到找到比tmp大的元素
while (arr[i] <= tmp && i < j) {
i++;
}
//将两元素进行调换
int t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
//将头元素与中间元素进行调换
arr[begin] = arr[i];
arr[i] = tmp;
//对左边进行快速排序
quickSort(arr, begin, i - 1);
//对右边进行快速排序
quickSort(arr, i + 1, end);
}
实践出真知，只有自己动手写才能充分感受到算法的巧妙与设计难度，在一步一步代码实现的过程中充分理解算法的思想，不断巩固，不断进步！最后补充常用排序算法及其复杂度分析，具体如下图：
参考《算法程序设计 》