快速排序和归并排序哪个快？
| 阿里云国内75折 回扣 微信号：monov8 |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |
两个排序的基本思想都是分治分而治之,实现一般都使用递归实现。
1.快速排序
双边指针交换法记录分界值 创建左右指针记录下标。
以第一个元素为分界值先从右向左找出比分界值小的数据然后从左向右找出比分界值大的数据
左右指针下标未过界交换左右指针数据
循环查找交换直到左右指针下标重合这时右边都是比重合处大的数据左边除了分界值都是比重合处小的数据重合后交换分界值和重合下标数据重合下标变为新分界值再分别递归处理新分界值左右部分数据。
public void quickSort(int[] arr, int startIndex, int endIndex) {
if (startIndex >= endIndex) {
return;
}
// 找到分界值
int pivotIndex = doublePointerSwap(arr, startIndex, endIndex);
// 用分界值下标区分出左右区间进行递归调用
quickSort(arr, startIndex, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, endIndex);
}
private int doublePointerSwap(int[] arr, int startIndex, int endIndex) {
int pivot = arr[startIndex];
int leftPoint = startIndex;
int rightPoint = endIndex;
while (leftPoint < rightPoint) {
// 从右向左找出比pivot小的数据
while (leftPoint < rightPoint
&& arr[rightPoint] > pivot) {
rightPoint--;
}
// 从左向右找出比pivot大的数据
while (leftPoint < rightPoint
&& arr[leftPoint] <= pivot) {
leftPoint++;
}
// 没有过界则交换
if (leftPoint < rightPoint) {
int temp = arr[leftPoint];
arr[leftPoint] = arr[rightPoint];
arr[rightPoint] = temp;
}
}
// 最终将分界值与当前指针数据交换
arr[startIndex] = arr[rightPoint];
arr[rightPoint] = pivot;
// 返回分界值所在下标
return rightPoint;
}2.归并排序
将已有序的子序列合并得到完全有序的序列即先使每个子序列有序再使子序列段间有序。
public int[] mergeSort(int[] nums, int low, int high) {
if (low == high) return new int[] { nums[low] };
int mid = (low + high)/ 2;
int[] leftArr = mergeSort(nums, low, mid); //左有序数组
int[] rightArr = mergeSort(nums, mid + 1, high); //右有序数组
int[] newNum = new int[leftArr.length + rightArr.length]; //新有序数组
int m = 0, i = 0, j = 0;
while (i < leftArr.length && j < rightArr.length) {
newNum[m++] = leftArr[i] <= rightArr[j] ? leftArr[i++] : rightArr[j++];
}
while (i < leftArr.length)
newNum[m++] = leftArr[i++];
while (j < rightArr.length)
newNum[m++] = rightArr[j++];
return newNum;
}3.比较
归并排序的比较次数小于快速排序的比较次数移动赋值次数一般多于快速排序的移动次数。
归并排序的内存占用高于快速排序快速排序时原地排序空间复杂度为O(1)归并排序不是原地排序数组合并需要额外空间。
快速排序是边分解边排序每次分解都实现整体上有序即参照数左侧的数小于参照值右侧的大于参照值归并排序是先递归分解到最小区间然后从小区间开始合并排序是自下而上的排序。
快速排序是不稳定的时间复杂度在O(nlogn)~O(n^2)之间归并排序是稳定的时间复杂度是O(nlogn)。
哪个更快
C++毫无疑问是快速排序C++有很强的inline优化机制比较操作比赋值操作要快的多。
Java有点复杂基本数据类型如(int/double)快排更快复杂数据类型对象则不一定有可能归并排序快也有可能快排快取决于比较和赋值操作哪个更快。
下面代码就可以测试出部分情况赋值操作比较比较操作更快。
public static void main(String[] args) {
int assignmentFast = 0;
for(int k=0; k<100; k++){
int len = 1024 * 1024 ;
NumTest[] numArray = new NumTest[len];
for(int i=0; i<numArray.length; i++){
NumTest numTest = new NumTest();
numTest.setNum1(RandomUtil.getNum(1,9999));
numTest.setNum2(RandomUtil.getNum(1,9999));
numArray[i] = numTest;
}
long startTime = System.currentTimeMillis();
for(int i=0; i<numArray.length; i++){
if(numArray[0].compareTo(numArray[i]) > 0){}
}
long compareSpend = System.currentTimeMillis()-startTime;
startTime = System.currentTimeMillis();
for(int i=0; i<numArray.length; i++){
numArray[0] = numArray[i];
}
long moveSpend = System.currentTimeMillis()-startTime;
if(moveSpend < compareSpend){
assignmentFast++;
System.out.println("赋值比比较操作快赋值花费时间:"+moveSpend+",比较花费时间:"+compareSpend);
}
}
System.out.println("赋值比比较快的次数:"+ assignmentFast);
}
static class NumTest implements Comparable<NumTest>{
int num1;
int num2;
public int getNum1() {
return num1;
}
public void setNum1(int num1) {
this.num1 = num1;
}
public int getNum2() {
return num2;
}
public void setNum2(int num2) {
this.num2 = num2;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
NumTest numTest = (NumTest) o;
return num1 == numTest.num1 &&
num2 == numTest.num2;
}
@Override
public int hashCode() {
return Objects.hash(num1, num2);
}
@Override
public int compareTo(NumTest o) {
int otherSum = o.getNum1() + o.getNum2();
int localSum = num1 + num2;
if(localSum == otherSum){
return 0;
}
return localSum>otherSum?1:-1;
}
}
