比较
两种算法都是分治(Divide and Conquer)算法。。 但是快速排序是先整体(<= pivot pivot >= pivot)后局部….. 原地操作。。。具有稳定性。。平均O(nlogn) 而归并排序是先局部(小数组排好序)后整体(排好序的小数组Merge) 空间复杂为O(n)…..稳定。。。都是O(nlogn)
Code:
快速排序：
public class QuickSort {
public static void sortIntegers(
int[] nums){
if (nums ==
null || nums.length ==
0){
return;
}
quickSort(nums,
0 ,nums.length -
1);
}
private static void quickSort(
int[] nums,
int start,
int end){
if (start >= end){
return;
}
int left = start, right = end;
int pivot = nums[(start + end) /
2];
while (left <= right){
while (left <= right && nums[left] < pivot){
left++;
}
while (left <= right && nums[right] > pivot){
right--;
}
if (left <= right){
int tmp = nums[left];
nums[left] = nums[right];
nums[right] = tmp;
left++;
right--;
}
}
quickSort(nums, start, right);
quickSort(nums, left, end);
}
细节：
这里要注意pivot取得是元素，而不是下标。。另外left <= right 可以避免子数组相交。为了切分均匀，nums[xx] 与pivot之间没有等号。。
归并排序：
public class MergeSort {
public static void sortIntegers(
int[] nums){
int[] tmp =
new int[nums.length];
mergeSort(nums,
0, nums.length -
1, tmp);
}
private static void mergeSort(
int[] nums,
int start,
int end,
int[] tmp){
if (start >=
end){
return;
}
int mid = (start +
end) /
2;
mergeSort(nums, start,
mid, tmp);
mergeSort(nums,
mid +
1,
end, tmp);
merge(nums, start,
end, tmp);
}
private static void merge(
int[] nums,
int start,
int end,
int[] tmp){
int mid = (
end + start) /
2;
int left = start,
right =
mid +
1;
int index = start;
while (
left <=
mid &&
right <=
end){
if (nums[
left] < nums[
right]){
tmp[index++] = nums[
left++];
}
else{
tmp[index++] = nums[
right++];
}
}
while(
left <=
mid){
tmp[index++] = nums[
left++];
}
while(
right <=
end){
tmp[index++] = nums[
right++];
}
for(
int i = start; i <=
end; i++){
nums[i] = tmp[i];
}
}
细节：
为了节约辅助数组的操作时间，这里是当做参数传进来的。。。 无脑归并操作，一定要记住。。。
转载请注明原文地址: https://ju.6miu.com/read-16593.html
