java 排序算法(6)归并排序:排序就是将一组对象按照某种逻辑顺序重新排列的过程。
归并排序是建立在归并操作上的一种有效的排序算法, 该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。
归并排序基本思想:(1)将待排序数组分为分为两部分,i 和 j 分别指向待排序子序列的第一个元素,比较 a[i] 和 a[j] 的大小,若 a[i]≤a[j],则将第一个有序表中的元素 a[i] 复制到 r[k](申请的临时数组,大小为子序列之和)中,并令 i 和 k 分别加上 1;否则将第二个有序表中的元素 a[j] 复制到 r[k] 中,并令 j 和 k 分别加上 1,如此循环下去,直到其中一个有序表取完,然后再将另一个有序表中剩余的元素复制到 r 中从下标 k 到下标 t 的单元。
(2)归并排序的算法我们通常用递归实现,先把待排序区间 [s,t] 以中点二分,接着把左边子区间排序,再把右边子区间排序,最后把左区间和右区间用一次归并操作合并成有序的区间[s,t]。
2、代码实现
- package com.chunsoft.sort;
- public class MergeSort {
- public static void main(String[] args) {
- int data[] = {
- 9,
- 8,
- 7,
- 6,
- 5,
- 8,
- 4,
- 3,
- 2,
- 1,
- 11,
- 0,
- 90
- };
- int length = data.length;
- F_MergeSort(data, 0, length - 1);
- for (int num: data) {
- System.out.println(num);
- }
- }
- private static void F_MergeSort(int[] data, int low, int high) {
- int mid = (low + high) / 2;
- if (low < high) { //左边切分 F_MergeSort(data,low,mid); //右边切分 F_MergeSort(data,mid+1,high); //归并 Sort(data,low,mid,high); } } private static void Sort(int[] data,int low,int mid,int high) { int[] temp = new int[high - low + 1]; int i = low;// 左指针 int j = mid + 1;// 右指针 int k = 0; while(i <= mid && j <= high) { if(data[i] <= data[j]) { temp[k++] = data[i++]; }else{ temp[k++] = data[j++]; } } //将左边剩余元素全部移入新数组 while(i <= mid) { temp[k++] = data[i++]; } //将右边剩余元素全部移入新数组 while(j <= high) { temp[k++] = data[j++]; } //把新数组中的数覆盖data数组 int length = temp.length; for (int k2 = 0; k2 < length; k2++) data[low + k2] = temp[k2]; }}
3、复杂度和稳定性
(1)复杂度
时间复杂度为 O(nlogn) 这是该算法中最好、最坏和平均的时间性能。
空间复杂度为 O(n)
比较操作的次数介于 (nlogn) / 2 和 nlogn - n + 1。
赋值操作的次数是 (2nlogn)。归并算法的空间复杂度为:0 (n)
归并排序比较占用内存,但却是一种效率高且稳定的算法。
时间复杂度:O(nlogn)
空间复杂度:O(n)
(2)稳定性
假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中,ri=rj,且 ri 在 rj 之前,而在排序后的序列中,ri 仍在 rj 之前,则称这种排序算法是稳定的;否则称为不稳定的。
稳定的:
归并排序是稳定的排序. 即相等的元素的顺序不会改变. 如输入记录 1(1) 3(2) 2(3) 2(4) 5(5) (括号中是记录的关键字) 时输出的 1(1) 2(3) 2(4) 3(2) 5(5) 中的 2 和 2 是按输入的顺序. 这对要排序数据包含多个信息而要按其中的某一个信息排序, 要求其它信息尽量按输入的顺序排列时很重要. 这也是它比快速排序优势的地方.
(3)特点
速度仅次于快速排序,为稳定排序算法,一般用于对总体无序,但是各子项相对有序的数列。
就爱阅读 www.92to.com 网友整理上传, 为您提供最全的知识大全, 期待您的分享,转载请注明出处。
来源: http://www.92to.com/bangong/2017/03-13/18653861.html