说明
为了自己学习方便,我这里总结了四大排序算法涵盖了七种排序算法
分类 | 算法名称 | 时间复杂度 空间复杂度 | 稳定性 |
插入排序 | 直接插入排序 希尔排序 | O(n^2) O(1) O(n^2/3) O(1) | 稳定 不稳定 |
选择排序 | 选择排序 堆排序 | O(n^2) O(1) O(nlogn) O(1) | 不稳定 不稳定 |
交换排序 | 冒泡排序 快速排序 | O(n^2) O(1) 全部有序最坏O(n^2) O(1) | 稳定 不稳定 |
归并排序 | 归并排序 | O(nlogn) O(n) | 稳定 |
归并排序
归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。
下面看代码
public static void mergeSort(int[] arr,int L,int R,int[] temp){
if(arr.length==0 || arr.length==1){
return;
}
if(L<R){
//分为两半
int mid=L+((R-L)>>1);
//排左边
mergeSort(arr,L,mid,temp);
//排右边
mergeSort(arr,mid+1,R,temp);
//合并
merge(arr,L,mid,R,temp);
}
}
// 合并两个有序数组
public static void merge(int[] arr,int L,int mid,int R,int[] temp){
int i=L,j=mid+1;
int m=mid,n=R;
int k=0;
while (i<=m && j<=n){
//将两个数组中较小的加入temp
if(arr[i]<arr[j]){
temp[k++]=arr[i++];
}else {
temp[k++]=arr[j++];
}
}
//一个数组已经遍历完了,另一个数组如果有元素直接加入temp
while (i<=m){
temp[k++]=arr[i++];
}
while (j<=n){
temp[k++]=arr[j++];
}
//将temp中的元素覆盖到arr中
for (int l = 0; l < k; l++) {
arr[L+l]=temp[l];
}
}
需要注意的是,归并排序需要创建一个临时数组,空间复杂度为O(n)