聊聊快速排序和归并排序
这两个排序算法很类似，都用到了递归和分治的思想。
快速排序的代码使用的是二叉树的前序遍历，而归并排序使用二叉树的后序遍历。
它们的代码模板分别为：
public sort(int[] a,int p,int r){
//快速排序
q = partition(a,p,r);
sort(a,p,q-1);
sort(a,q+1,r);
//归并排序
sort(a,p,q);
sort(a,q+1,r);
merge(a,p,q,r);
}
归并排序的思路是：
先将原有数据进行分开，直至分到数组的长度为2。然后对这个短的数组进行排序，然后再统一合并到一个数组中，最后归并到原有的数组。
在其中的merge函数，会在每一层对新建一个临时函数进行排序。
public class mergeOrder {
public static void mergeSort(int[] a, int n){
mergeSortRecu(a,0,n-1);
}
public static void mergeSortRecu(int[] a ,int p,int r){
//递归将数值进行分组
if (p>=r) return;
// 这里是为了p+r超过int类型的最大值
int q = p+(r-p)/2;
mergeSortRecu(a,p,q);
mergeSortRecu(a,q+1,r);
merge(a , p ,q ,r);
}
public static void merge(int[] a, int p,int q, int r) {
//对递归本层的两数组进行合并
//必须新建一个数组对合并的数组进行存储。
int i = p;
int k = q+1;
int j= 0;
int[] tmp = new int[r - p + 1];
//因为是一分为二，所以现在也是二合为一,且两组数据有长有段
while (i<=q && k<=r){
if (a[i] >= a[k]){
tmp[j++]= a[k++];
}else {
tmp[j++]= a[i++];
}
}
int start = i;
int end = q;
if (k <= r) {
start = k;
end =r;
}
//将剩余的添加到tmp中
while (start <= end){
tmp[j++] = a[start++];
}
// 将其放到原数组中的位置
for (int l = 0; l <= r-p; l++) {
a[p+l] = tmp[l];
}
}
public static void main(String[] args) {
int[] n = {2,1,32,44,35,22};
mergeSort(n,n.length);
for (int i : n) {
System.out.print(i+" ");
}
}
}
快速排序是前序遍历：
所以首先得得出中间值V，比V小的放在左边，比V大的放在右边。
因为是对数组操作，想要在原数组上进行数据的排序，少不了元素的移动，这会造成O(n)的时间复杂度。所以这里使用了交换数据来解决。先存储中间值V，然后一次和V对比，元素两两交换，遍历完所有元素，再与V交换即可。到这里就已经完成了一轮分值的对比，中间值的左边比它小，右边比它大。
然后进入下一层。依次递归，对a进行快速排序。
public class RapidSort {
public static void RapidS(int[] a, int p, int r){
// 快排相当于是前序排序，注意看下面当代码模板
if (p>=r) return;
int part = partition(a, p, r);
//part代表当是下一层当分区中心，而中心不用再进行对比
//所以要再-1和+1。
RapidS(a,p,part-1);
RapidS(a,part+1,r);
}
public static int partition(int[] a, int p, int r) {
int value = a[r];
int i = p;
//每次进入分区函数，要注意是在p,r的区间里比较
for (int j = p; j < r; j++) {
if (a[i] <= value){
int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
i++;
}
}
//当和分区值比较完之后，再将分区值与i下标对应当元素进行调换。
int t = a[r];
a[r]= a[i];
a[i] =t;
//返回分区下标
return i;
}
public static void main(String[] args) {
int[] n = {2,1,32,44,35,100};
RapidS(n,0,n.length-1);
for (int i : n) {
System.out.print(i+" ");
}
}
}