java实现归并排序(Mergesort)
引言
3.29
简介
归并排序(MERGESORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。
归并排序的时间复杂度是O(nlogn), 空间复杂度是O(n)。是稳定的排序。
归并排序的思路流程是:
第一步、将待排序数列中的数字分为若干组,每个数字分成一组,即如果数列中8个数字,就分成8组。
第二步、将这些组两两合并,保证合并之后的数列是有序的。
第三步、重复第二步操作,直到只剩下一组,即排序完成。
看文字理解可能有点云里雾里,接下来我们用图来解释下这个过程。
3.29
图解流程
3.29
代码实现
Java:
import java.util.Arrays;
public class MergeSort {
public static void main(String[] args) {
int[] arr = {2,3,4,1,5,7,8,6};
System.out.println(Arrays.toString(arr));
mergeSort(arr,0, arr.length-1);
System.out.println(Arrays.toString(arr));
}
/**
*
* @param arr //待排序数组
* @param low //左边标识
* @param high //右边标识
*/
public static void mergeSort(int[] arr,int low,int high){
if(low >= high){
return;
}
int mid = (low +high) >>> 1;
mergeSort(arr,low,mid);
mergeSort(arr,mid+1,high);
//合并
merge(arr, low, mid, high);
}
private static void merge(int[] arr, int low, int mid, int high) {
int s1 = low; //第一个归并段开始
int s2 = mid+1 ;//第二个归并段开始
//临时数组
int[] ret = new int[high-low +1];
int i = 0; //ret数组的下标
//归并段有数据
while (s1 <= mid && s2 <=high )
{
//s1和s2数据比较
if(arr[s1] <= arr[s2]){
ret[i++] = arr[s1++];
}else {
ret[i++] = arr[s2++];
}
}
//跳出循环
while (s1 <= mid){
ret[i++] = arr[s1++];
}
while (s2 <= high){
ret[i++] = arr[s2++];
}
for (int j = 0; j < ret.length ; j++) {
arr[j+low]= ret[j];
}
}
}
C++:
template<typename T> // 整數或浮點數皆可使用,若要使用物件(class)時必須設定"小於"(<)的運算子功能
void merge_sort(T arr[], int len) {
T *a = arr;
T *b = new T[len];
for (int seg = 1; seg < len; seg += seg) {
for (int start = 0; start < len; start += seg + seg) {
int low = start, mid = min(start + seg, len), high = min(start + seg + seg, len);
int k = low;
int start1 = low, end1 = mid;
int start2 = mid, end2 = high;
while (start1 < end1 && start2 < end2)
b[k++] = a[start1] < a[start2] ? a[start1++] : a[start2++];
while (start1 < end1)
b[k++] = a[start1++];
while (start2 < end2)
b[k++] = a[start2++];
}
T *temp = a;
a = b;
b = temp;
}
if (a != arr) {
for (int i = 0; i < len; i++)
b[i] = a[i];
b = a;
}
delete[] b;
}
如果该文章对你有帮助,"再看"和"点赞"是对我最大的鼓励!
扫二维码|关注我们
谢谢观看
把城市夜晚的喧嚣,点出来
▼