归并排序和快速排序

归并排序和快速排序

一，归并排序

归并排序算法实现

算法思路： 如果要排序一个数组，我们先从数组中间把数组分成左数组和右数组两部分，分别对左右数组进行排序，然后将排序好的数组合并成结果数组，排序就完成了，最后只需将结果数组复制回原数组即可。

核心思想 ----- 分治思想

分治也即是分而治之，将一个大问题分解为小的子问题来解决。分治算法一般都是用递归来实现的。分治是一种解决问题的处理思想，递归是一种编程技巧。

归并排序分析

稳定排序算法归并排序的执行效率与原始数据的有序程度无关，其时间复杂度是非常稳定的，不管是最好情况、最坏情况，还是平均情况，时间复杂度都是O(NlogN)。归并排序有一个缺点，那就是它不是原地排序算法。在进行子数组合并的时候，我们需要临时申请一个数组来暂时存放排好序的数据。因为这个临时空间是可以重复利用的，因此归并排序的空间复杂度为O(n)，最多需要存放n个数据。

具体实现

public class MergeSort { /** * 归并排序 O(NlogN) * * 思想：分治 * @param oldArray * @param tmpArray * @param left * @param right */ private static void mergeSort(int[] oldArray,int[] tmpArray,int left,int right) { if(left < right) { //中间元素下标 int center = (left + right)/2; //分治左边数组[left , center] mergeSort(oldArray, tmpArray, left,center); //分治右边数组[center+1 , right] mergeSort(oldArray, tmpArray, center+1, right); //分开排序后合并成一个新数组在copy会原数组，此时原数组已经有序 merge(oldArray, tmpArray, left, center+1,right); } } /** * 排序，合并 * @param oldArray * @param tmpArray * @param leftStart * @param rightStart * @param rightEnd */ private static void merge(int[] oldArray, int[] tmpArray, int leftStart, int rightStart, int rightEnd) { //左数组开始下标 int leftEnd = rightStart - 1; //辅助数组起始下标 int tmpPos = leftStart; //数组元素数量 int numElements = rightEnd - tmpPos + 1; //左右数组进行比较,按序放入辅助数组 while(leftStart <= leftEnd && rightStart <= rightEnd) { if(oldArray[leftStart] <= oldArray[rightStart]) { tmpArray[tmpPos++] = oldArray[leftStart++]; }else { tmpArray[tmpPos++] = oldArray[rightStart++]; } } //判断子数组是否还有元素，有则拷贝到 tmp 后面 while(leftStart <= leftEnd) { tmpArray[tmpPos++] = oldArray[leftStart++]; } //判断子数组是否还有元素，有则拷贝到 tmp 后面 while(rightStart <= rightEnd) { tmpArray[tmpPos++] = oldArray[rightStart++]; } //复制辅助数组回原数组 for(int i = 0;i

结果：

二，快速排序

算法思路：

随便选取一项（一般是中间值），然后形成三个组，小于被选项组，大于被选项组合等于被选项组，递归的对小于被选项组，大于被选项组进行排序，然后合并这三个组。

核心思想：------- 分治思想

算法分析：

快速排序是一个原地排序算法，是一个不稳定的排序算法，因为其在数据交换过程中可能会改变相等元素的原始位置。平均时间复杂度O(NlogN) ,最坏时间复杂度O(N^2)如果快速排序每次都将数据分成相等的两部分，则快排的时间复杂度和归并排序相同，也是O(nlogn)，但这种情况是很难实现的。如果数据原来已经是有序的，则每次的分区都是不均等的，我们需要进行 n 次分区才能完成整个排序，此时快排的时间复杂度就退化成了O(n^2)

public class QuickSort { /** * 快速排序 O(NlogN) * @param list */ private static void quickSort(ArrayList list) { if(list.size()>1) { ArrayList smallerlist = new ArrayList<>(); ArrayList centerList = new ArrayList<>(); ArrayList largeList = new ArrayList<>(); //中间元素 Integer center = list.get(list.size()/2); //分类 for(Integer i : list) { if(i < center) { //比中间元素小 smallerlist.add(i); }else if (i > center) { //比中间元素大 largeList.add(i); }else { //与中间元素相等 centerList.add(i); } } //分组排序 quickSort(smallerlist); quickSort(largeList); //清空 list.clear(); //合并 list.addAll(smallerlist); list.addAll(centerList); list.addAll(largeList); } } public static void main(String[] args) { int[] a = {1,8,2,6,4,2,3,8,4,6,10,12,45,21,31}; ArrayList list = new ArrayList<>(); for(int i = 0;i

结果：

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。