Java归并排序和快速排序怎么实现-创新互联
本篇内容介绍了“Java归并排序和快速排序怎么实现”的有关知识，在实际案例的操作过程中，不少人都会遇到这样的困境，接下来就让小编带领大家学习一下如何处理这些情况吧！希望大家仔细阅读，能够学有所成！
归并排序
// 归并排序
public static void mergeSort (int[] arr) {
// 建一个临时数据来存放数据
int[] temp = new int[arr.length];
mergeSort(arr, 0, arr.length - 1, temp);
}
private static void mergeSort(int[] arr, int left, int right, int[] temp) {
if (left < right) { // 如果起始下标跟结束下标差值小于1，则不进行操作
int mid = (left + right) / 2;
mergeSort(arr, left, mid, temp); // 分组，将左边分为一组，递归调用进行排序
mergeSort(arr, mid+1, right, temp); // 将右边分为一组
merge(arr, left, mid, right, temp); //将左右分组合并
}
}
private static void merge(int[] arr, int left, int mid, int right, int[] temp) {
int i = left; // 定义左指针
int j = mid + 1; // 定义右指针
int t = 0; // 给temp临时数组用的指针
while (i <= mid && j <= right) { // 设置左右指针的移动边界
if (arr[i] <= arr[j]) { // 此处是升序，故谁小谁先赋给临时数组
temp[t++] = arr[i++];
} else {
temp[t++] = arr[j++];
}
}
while (i <= mid) { // 如果左边有剩余，则放在temp中
temp[t++] = arr[i++];
}
while (j <= right) { // 如果右边有剩余，依次放入temp中
temp[t++] = arr[j++];
}
t = 0;
// 此时temp中已经是arr数组中下标从left到right之间排好序的数据了，因为temp每次都是从0开始赋值，所以需将排好序的数放回arr的对应位置
while (left <= right) {
// 将left到right之间排好序的数据放回arr中，此时left到right之间的数就是最终排好序的数
arr[left++] = temp[t++];
}
}快速排序
// 快速排序
public static void quickSort (int[] arr, int left, int right) {
// 先将异常情况处理掉
if (arr == null || arr.length < 2) {
return;
}
if (right <= left) {
return;
}
if (right - left == 1 && arr[left] <= arr[right]) {
return;
}
// 取第一个数为基准数(基数取哪个都行，此处是为了方便)
int index = arr[left];
int i = left + 1; // 左指针
int j = right; // 右指针
while (i < j && i < right && j > left) { // 设置指针的移动边界
while (arr[j] > index && j > left) {j--;} // 找到从右边数第一个比index小的数
while (arr[i] < index && i < right) {i++;} // 找到从左边数第一个比index大的数
if (i < j) { // 交换这两个数 如果i == j，说明二者定位到了同一个位置，则不用交换；如果i > j，说明二者已经相遇然后背向而行了，也不交换
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// 执行完上面循环后，arr已经是左边比index小，右边比index大的数组了，只是基准数仍在基准位置left处，需放到它应该在的位置
if (j != left && arr[j] != arr[left]) {
// j最后停留位置的数，肯定是一个小于等于index的值，所以如果不是同一个位置的话，直接将二者调换一下位置即可
int temp = arr[j];
arr[j] = arr[left];
arr[left] = temp;
}
quickSort(arr, left, j-1); // 将基准数左边排序
quickSort(arr, j+1, right); // 将基准数右边排序
}“Java归并排序和快速排序怎么实现”的内容就介绍到这里了，感谢大家的阅读。如果想了解更多行业相关的知识可以关注创新互联-成都网站建设公司网站，小编将为大家输出更多高质量的实用文章！
网页标题：Java归并排序和快速排序怎么实现-创新互联
URL标题：http://cdiso.cn/article/hosgh.html
