归并排序和快速排序
归并排序
定义：归并排序是建立在归并操作上的一种有效，稳定的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。
思路： 1）首先将给定的数组{51, 46, 20, 18, 95, 67, 82, 30}一分为二，直到每个数组的长度等于1 {51, 46, 20, 18} {95, 67, 82, 30} {51, 46} {20, 18} {95, 67} {82, 30} {51} {46} {20} {18} {95} {67} {82} {30} 2）两两比较进行交换{46, 51} {18, 20} {67, 95} {30, 82} 3）最后进行合并得到排序后的数组{18, 20, 30, 46, 51, 67, 82, 95} 整体的递归思路就是：
代码执行：
import java.util.Arrays;
public class MergeSort {
public static int sum = 0;
public static void main(String[] args) {
int[] a = {51, 46, 20, 18, 95, 67, 82, 30};
mergeSort(a, 0, a.length - 1);
System.out.println(Arrays.toString(a));
}
public static void mergeSort(int[] a, int left, int right) {
//二分
int mid = (left + right) / 2;
//拆分过程就是递归，需要不断进行递归，减小子数组的规模，最终减小到每个数组的规模为1或者为0
if (left < right) {
mergeSort(a, left, mid);
mergeSort(a, mid + 1, right);
merge(a, left, mid, right);
}
}
public static void merge(int[] a, int left, int mid, int right) {
int[] temp = new int[right - left + 1];//临时数组，用来进行归并
int i = left, j = mid + 1, k = 0;//左半段用i指向，右半段用j指向，temp中用k指向
while (i <= mid && j <= right) {
if (a[i] < a[j]) {
//如果左边的a[i]小于右边的a[j]，就放到数组的第k个，k和i自增
temp[k++] = a[i++];
} else {
//否则，就把右边的第j个放到数组的第k个，k和j自增
temp[k++] = a[j++];
}
}
while (i <= mid) temp[k++] = a[i++];//如果左边在循环比较后还有剩余，就放到k中、
while (j <= right) temp[k++] = a[j++];//如果剩余直接放到k中
for (int l = 0; l < temp.length; l++) {
//让temp数组放到左半段和右半段有序的数据
a[left + l] = temp[l];
}
}
}快速排序
运行流程： 1）首先设定一个分界值，通过该分界值将数组分成左右两部分。 2）将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于分界值，而右边部分中各元素都大于或等于分界值。 3）左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。 4）重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。
运行流程图：
代码思路：
1）首先确定left、rigeht和基准点temp
2）当i(left) 和 j(right)相等的时候就结束循环
3）在循环中再次循环找出a[j]小于temp的时候把a[j]赋给a[i++]，以及找出a[i]大于temp的时候把a[i]赋给a[j--]
4）不断递归进行排序
代码执行：
import java.util.Arrays;
public class quickSortDemo {
public static void main(String[] args) {
int[] a = {49, 38, 65, 97, 76, 13, 27, 49};
quickSort(a, 0, a.length - 1);
System.out.println(Arrays.toString(a));
}
public static void quickSort(int[] a, int left, int right) {
if (left > right) return;//区间无效不需要递归
int i = left, j = right, temp = a[left];//temp为基准点
while (i != j) {
while (a[j] >= temp && j > i) j--;//一直循环找a[j]小于temp的时候
if (j > i) a[i++] = a[j];//将a[j]赋给a[i++]
while (a[i] <= temp && i < j) i++;//循环找a[i]大于temp的时候
if (i < j) a[j--] = a[i];//将a[i]赋给a[j--]
}
a[i] = temp;//将基准点的元素放到a[i]处
quickSort(a, left, i - 1);//已经确定i为基准点所以right就位i - 1
quickSort(a, i + 1, right);//已经确定i为基准点所以left就位i + 1
}
}腾讯云开发者
