归并排序
订阅
归并排序(Merge Sort)是建立在归并操作上的一种有效,稳定的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。
展开全文

归并排序(Merge Sort)是建立在归并操作上的一种有效,稳定的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。
信息
- 外文名
- Merge Sort
- 空间复杂度
- T(n)
- 发明者
- 约翰·冯·诺伊曼
- 中文名
- 归并排序
- 稳定性
- 稳定
- 时间复杂度
- O(n log n)
归并排序归并操作
归并操作,也叫归并算法,指的是将两个顺序序列合并成一个顺序序列的方法。如 设有数列{6,202,100,301,38,8,1}初始状态:6,202,100,301,38,8,1第一次归并后:{6,202},{100,301},{8,38},{1},比较次数:3;第二次归并后:{6,100,202,301},{1,8,38},比较次数:4;第三次归并后:{1,6,8,38,100,202,301},比较次数:4;总的比较次数为:3+4+4=11;逆序数为14;
-
归并排序
2019-03-01 11:31:48归并排序0.时间复杂度
lgn * n
1.Java实现
private static void println(int[] array) { for (int item : array) { System.out.print(item + " "); } System.out.println(); } private static void mergeSortByIndex(int[] array, int startIndex, int endIndex) { // 最小处理块1 然后依次往上层归并 if (startIndex < endIndex) { int centerIndex = (startIndex + endIndex) / 2; mergeSortByIndex(array, startIndex, centerIndex); mergeSortByIndex(array, centerIndex + 1, endIndex); mergeArray(array, startIndex, centerIndex, endIndex); } } private static void mergeArray(int[] array, int startIndex, int centerIndex, int endIndex) { int[] tempArray = new int[endIndex - startIndex + 1]; int leftIndex = startIndex; int rightIndex = centerIndex + 1; boolean leftFlag = true; boolean rightFlag = true; int temp = 0; while (temp <= endIndex - startIndex) { if (leftIndex > centerIndex) { leftFlag = false; } if (rightIndex > endIndex) { rightFlag = false; } if (leftFlag && rightFlag) { // 左右2边都有 // if (array[leftIndex] <= array[rightIndex]) { if (array[leftIndex] >= array[rightIndex]) { tempArray[temp] = array[leftIndex]; leftIndex ++; } else { tempArray[temp] = array[rightIndex]; rightIndex ++; } } else if (!leftFlag && !rightFlag) { // 左右2边都没有 break; } else if (!leftFlag && rightFlag) { // 只有右边有 tempArray[temp] = array[rightIndex]; rightIndex ++; } else { // 只有左边有 tempArray[temp] = array[leftIndex]; leftIndex ++; } temp ++; } // 复制到原数组中 for (int copyIndex = 0; copyIndex < tempArray.length; copyIndex ++) { array[startIndex + copyIndex] = tempArray[copyIndex]; } } private static void mergeSort(int[] array) { mergeSortByIndex(array, 0, array.length - 1); } public static void main(String[] args) throws Exception { // int[] array = {10, 9, 8}; int[] array = {8, 9, 10}; println(array); mergeSort(array); println(array); }
收藏数
46,186
精华内容
18,474