七大排序算法 |
您所在的位置:网站首页 › 九字讲解 › 七大排序算法 |
文章目录
一、排序的概念排序的概念排序的稳定性七大排序算法
二、归并排序核心思想代码实现
三、性能分析四、七大排序算法性能对比
一、排序的概念
排序的概念
排序:所谓排序,就是使一串记录,按照其中的某个或某些关键字的大小,递增或递减的排列起来的操作。 排序的稳定性上述待排序的数中,有两个5。 将前面的5标记一个a, 将后面的5标记一个b。 通过算法进行排序后,这一组数就有序了, 但是要看两个相同的5的位置是否有改变。 5a仍在5b前面,那么这个排序算法就是稳定的 , 5a跑到了5b后面,那么这个排序算法就是不稳定的 。 一个稳定的排序算法可以做到不稳定, 不稳定的排序算法一定做不到稳定。 至于为什么要讨论这个稳定性, 是为了以后应用到实际场景上。 比如,一场数学考试, 假设a用了30分钟做完了,并得了满分。 假设b用了一个小时做完了,并得了满分。 此时a与b都是得了满分,但是用的时间不一样,所以两个人的排名又会有所不同。 七大排序算法 二、归并排序 核心思想基本思想:归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide andConquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。 图解 有一组待排序数列,我们进行升序排序。 拆分过程:将一个数组逐层拆分成多个子序列,直到每个子序列只剩一个数据,那么就认为这个子序列是有序的。 合并过程:再逐一将这些子序列进行有序合并,最后得到的序列就是有序的。 代码实现代码实现 public class MergeSort { /** * 归并排序 * 时间复杂度:O(n*logn) * 空间复杂度:O(n) * 稳定性:稳定 * @param array */ //递归实现的归并排序 public static void mergeSort(int[] array) { mergeSortFunc(array,0, array.length-1); } private static void mergeSortFunc(int[] array,int left,int right) { if(left >= right) { return; } int mid = (left+right)/2; mergeSortFunc(array,left,mid); mergeSortFunc(array,mid+1,right); merge(array,left,right,mid); } // 合并方法 private static void merge(int[] array,int start,int end,int mid) { // 创建一个新数组 int[] ary = new int[end-start+1]; // 左边有序数组的起始下标 int left = start; // 右边有序数组的起始下标 int right = mid+1; for (int i = 0; i mid) { ary[i] = array[right++]; // 如果右边有序数组已经全部有序的存入了新数组, // 那就证明剩下左边有序数组的数已经有序了,不用比较直接存入 }else if (right > end) { ary[i] = array[left++]; // 哪个小哪个先存进新数组 } else if(array[left] > array[right]) { ary[i] = array[right++]; }else { ary[i] = array[left++]; } } // 将新数组按位置存入需要排序的数组 for (int i = start; i |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |