精华内容
下载资源
问答
  • Java快速排序和归并排序区别和实现

    千次阅读 2018-06-05 14:11:52
    快速排序归并排序的概念: 快速排序(Quicksort)是对冒泡排序的一种改进。 快速排序由C. A. R. Hoare在1962年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比...

    快速排序与归并排序的概念:

             快速排序(Quicksort)是对冒泡排序的一种改进。
              快速排序由C. A. R. Hoare在1962年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列
                   归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并

    快速排序与归并排序的区别:

                  快速排序的时间复杂度是(nlogn),但是快速排序是一种不稳定的排序方法,也就是说当有多个相同的值的时候在排序结束的时候它们的相对位置会发生改变。

                   归并排序的时间复杂度是(nlogn),但是归并排序是一种稳定的排序方法,即相等的元素顺序不会改变,但是相比于快速排序来说归并要申请的空间更大,消耗空间更多。

    快速排序实现方式:

                        快速排序原理基于冒泡排序改进的。设要排序的数组是A[0]....A[N-1],首先任意选取一个数据(通常选取用数组的第一个数)作为关键数据key,然后比key小的数据都放到key的前面,比key大的数据都放在key的后面,这个过程称为一趟快速排序。

                        算法思路:

                                            1>设置两个变量i,j,排序开始的时候,i=low;j = high;(第一趟low=0,high为数组长度N)

                                            2>以第一个数组元素为关键元素,赋值给key,即key = A[0];

                                            3>从j开始像前搜索,找到第一个比key小的数a[j],将a[j]和a[i]交换。

                                            4>从i开始向后搜素,找到第一个比key大的数a[i],将a[i]和a[j]交换。

                                            5>重复3,4步直到i==j

                                            6>对key左边和右边分别递归调用以上步骤。

                        代码如下:

    package sort;
    
    import java.util.Arrays;
    import java.util.Scanner;
    
    public class QuickSort {
    
    	public static void main(String[] args) {
    		int [] a = {1,11,2,3,5,68,0,1};
    		System.out.println("未排序的数组:"+Arrays.toString(a));
    		if(a.length > 0){
    			quickSort(a,0,a.length-1);
    		}else{
    			System.out.println("空数组不能排序");
    		}
    		System.out.println("排序后的数组:"+Arrays.toString(a));
    	}
    	public static void quickSort(int[] a,int low,int high){
    		if(low > high){
    			return;
    		}//递归的出口
    		int i = low;
    		int j = high;
    		int key = a[low];
    		while(i < j){
    			while(a[j] > key && i < j){
    					j--;
    			}//找到第一个比key小的数
    			while(a[i] <= key && i < j){
    					i++;
    			}//找到第一个比key大的数
    			if(i < j){//如果i小于j,交换a[i],a[j]
    				int temp = a[i];
    				a[i] = a[j];
    				a[j] = temp;
    			}
    		}
    		int  p = a[i];
    		a[i] = a[low];
    		a[low] = p;//调整key的位置
    		quickSort(a,low,i-1);
    		quickSort(a,i+1,high);
    	}
    }
    

         归并排序的实现方式:
             归并排序就是利用归并的思想实现的排序方法。而且充分利用了完全二叉树的深度是log2n+1的特性,因此效率比较高。
            基本原理如下:对于给定的一组记录,利用递归与分治技术将数据序列划分成为越来越小的半子表,在对半子表排序,最后再用递归方法将排好序的半子表合并成为越来越大的有序序列。 
    经过第一轮比较后得到最小的记录,然后将该记录的位置与第一个记录的位置交换;接着对不包括第一个记录以外的其他记录进行第二次比较,得到最小记录并与第二个位置记录交换;重复该过程,知道进行比较的记录只剩下一个为止。
           实现方式:
    第一步:申请空间,使其大小为两个已经 排序序列之和,该空间用来存放合并后的序列
    第二步:设定两个 指针,最初位置分别为两个已经排序序列的起始位置
    第三步:比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置
    第四步:重复步骤3直到某一指针超出序列尾 将另一序列剩下的所有元素直接复制到合并序列尾。
    package sort;
    import java.util.Arrays;
    public class MergeSort {
    	public static void main(String[] args){
    		int [] a = {1,11,2,3,5,68,0,1};
    		System.out.println("未排序的数组:"+Arrays.toString(a));
    		if(a.length > 0){
    			mergeSort(a,0,a.length-1);
    		}else{
    			System.out.println("空数组不能排序");
    		}
    		System.out.println("排序后的数组:"+Arrays.toString(a));
    	}
    	public static void merge(int[]a,int low,int mid,int high){
    		int [] mergeArr = new int[high-low+1];//申请一个新空间来保存排序后数组
    		int i = low;
    		int j = mid + 1;
    		int k = 0;
    		while(i <= mid && j <= high){
    			if(a[i] < a[j]){
    				mergeArr[k] = a[i];
    				k++;
    				i++;
    			}else{
    				mergeArr[k] = a[j];
    				k++;
    				j++;
    			}
    		}
    		while(i <= mid){
    			mergeArr[k] = a[i];
    			k++;
    			i++;
    		}//把左边剩余的元素导入
    		while(j <= high){
    			mergeArr[k] = a[j];
    			j++;
    			k++;
    		}//把右边剩余的元素导入
    		for(int m = 0;m < mergeArr.length;m++){
    			a[m+low] = mergeArr[m];
    		}//将新排好序的数组放入元素相应的位置中
    	}
    	public static void mergeSort(int []a,int low,int high){
    		int mid = (low + high) / 2;
    		if(low < high){
    			mergeSort(a,low,mid);//左
    			mergeSort(a,mid+1,high);//右
    			merge(a,low,mid,high);//左右合并
    		}
    	}
    }
    
    以上就是我对快速排序算法和归并算法学习的心得,如有不足还多多请各位指教。



                        

                
    展开全文
  • 快速排序和归并排序区别

    千次阅读 2012-07-29 18:42:09
    快速排序: 1 是直接在待排序序列中排序的,不需要备用数组装排好的数据 2 是分部分进行排序,但,部分是随机的,没有一半一半的关系。只要符合条件就可以。 3 分部分的过程中同时排序的。不等到部分都分完。...

     

    快速排序:

    1  是直接在待排序序列中排序的,不需要备用数组装排好的数据

    2  是分部分进行排序,但,部分是随机的,没有一半一半的关系。只要符合条件就可以。

    3  分部分的过程中同时排序的。不等到部分都分完。。

    4  交换排序,跳跃性,不稳定排序

    归并排序:

    1  需要备用数组,在最后的时候装排好序的数组,并再copy给原来的数组。

    2  分部分,但是是分一半一半的,刚好二分之一。

    3  是先分完部分,再进行的排序,分和排是先后的。

    4  两两比较,稳定排序

     

    展开全文
  • 快速排序和归并排序

    2021-02-15 22:40:58
    快速排序和归并排序 比较 时间复杂度 空间复杂度 稳定性 快速排序(quick sort) 平均o(nlogn) 最坏o(n^2) o(1) in-place 不稳定 归并排序(merge sort) 都是o(nlogn) o(n) 稳定 都是分治思想,和双...

    快速排序和归并排序

    比较时间复杂度空间复杂度稳定性
    快速排序(quick sort)平均o(nlogn) 最坏o(n^2)o(1) in-place不稳定
    归并排序(merge sort)都是o(nlogn)o(n)稳定
    1. 都是分治思想,和双指针实现手法
    2. 不同的是快排是从宏观到微观,归并是微观到宏观
    3. 稳定性是指对于相同的key,排序后的次序还保持原来排序前的次序。

    python代码实现

    • 快速排序

      def quickSort(list,start,end):
          if (start >= end):
              return
          left,right = start,end
          pivot = list[(start + end) // 2]
          while (left <= right):
              while (left <= right and list[left] < pivot):
                  left += 1
              while (left <= right and list[right] > pivot):
                  right -= 1
              if (left <= right):
                  list[left],list[right] = list[right],list[left]
                  left += 1
                  right -= 1
          quickSort(list,start,right)
          quickSort(list,left,end)
                  
      

      注意:

    1. left <= right not left < right
    2. 每次partitionj的结果都是list[start:right+1] <= pivot, list[left:end+1] >= pivot。 目的是使partition后左右两个区间长度尽可能相同,从而避免最坏情况
    • 归并排序

      def mergeSort(list,start,end):
          if(start >= end):
              return
          mid = (start + end) // 2
          mergeSort(list,start,mid)
          mergeSort(list,mid + 1,end)
          merge(list,start,mid,end)
      
      def merge(list,start,mid,end):
          temp = []
          left,right = start,mid + 1
          while (left <= mid and right <= end):
              if (list[left] < list[right]):
                  temp.append(list[left])
                  left += 1
              else:
                  temp.append(list[right])
                  right += 1
          temp += list[left:mid+1]
          temp += list[right:end+1]
          list[start:end+1] = temp
      

      注意:merge函数的书写

    展开全文
  • 用matlab实现的快速排序以及归并排序
  • 虽然归并排序和快速排序的时间复杂度都为O(nlogn),但实际上快速排序的速度会比归并排序快2-3倍,原因如下: 1.归并排序在执行时,需要一个额外的temp数组去拷贝原数组的数据,会大量占用程序的空间。 2.快速排序...

    虽然归并排序和快速排序的时间复杂度都为O(nlogn),但实际上快速排序的速度会比归并排序快2-3倍,原因如下:

    1.归并排序在执行时,需要一个额外的temp数组去拷贝原数组的数据,会大量占用程序的空间。

    2.快速排序再运行时,实际上是直接再原数组进行递归操作,并不会占用额外的空间。

    展开全文
  • 快速排序和归并排序(C语言)

    千次阅读 2017-12-23 21:44:41
    快速排序和归并排序; 快速排序归并排序; 阅读之前注意:本文阅读建议用时:20min
  • 本文主要讨论性质相对比较好且作者喜欢的快速排序算法和归并排序算法,并对此这做了一定比较。 正文: 常见的排序算法大致分为四类: 1.插入排序:直接插入排序,Shell排序 2.选择排序:直接选择排序,堆排序 3....
  • 排序之归并排序和快速排序

    千次阅读 2017-04-02 16:34:08
    1. 归并排序归 快速排序 归并排序和快速排序区别
  • 排序算法:快速排序和归并排序 快速排序和归并排序是排序算法里十分常用的两个排序,二者的代码复杂度差不多,并且都应用了分治法的思想。 复杂度 排序算法 平均时间复杂度 最坏时间复杂度 最好时间复杂度 ...
  • 快速排序思路:随便选择一个数字作为中间点,小于放在左边,大于放在右边。递归对左右两个部分排序。就是先整体有序,后局部有序。归并排序优缺点优点:容易掌握,用处广泛。分治思想很重要缺点:花费O(n)的额外空间...
  • 选择排序、插入排序、冒泡排序以及快速排序和归并排序的C语言实现,绝对可用
  • 分治思想是常见的算法思想之一,在排序算法中用到分治思想的有:快速排序和归并排序。 分治法介绍如下图: 分治思想的关键点: 1、有问题可以一直分解为形式相同的子问题,当子问题规模较小时,可自然求解,例如一...
  • 本篇文章讲解三个高级排序算法,分别为希尔排序、归并排序、快速排序。虽然它们的思想很复杂,但真的运用得非常得巧妙,我会用丰富的例子以及动图来让大家轻松地理解并掌握。
  • Java实现快速排序归并排序快速排序归并排序 快速排序 import java.util.Arrays; public class QuickSort01 { public static void main(String[] args) { int[] arr = {2, 9, 3, 1, 8, 4}; quick...
  • 快速排序&归并排序

    2017-05-21 21:41:27
    快速排序&归并排序快速排序和归并排序是非常常用的两种排序方式; 例如C# Array.Sort()就是快速排序的实现 java集合里Collections.sort()是归并排序及优化的归并排序(TimSort) 感兴趣的童鞋可以参考 C# Array....
  • 快速排序和归并排序对比 快速排序 排序流程 (1)首先设定一个分界值(一般为第一个元素),通过该分界值将数组分成左右两部分。 (2)将大于或等于分界值的数据集中到数组右边,小于分界值的数据集中到数组的左边。此时...
  • 主要为大家详细介绍了JavaScript希尔排序、快速排序归并排序算法,感兴趣的朋友可以参考一下
  • 算法设计实验报告,包括:快速排序和归并排序两种算法各自的基本思想、时间复杂度分析,C++实现代码,两种算法运行时间的比较,运行截图,实验心得。
  • 快速排序由于排序效率在同为O(N*logN)的几种排序方法中效率较高,因此经常被采用,再加上快速排序思想----分治法(敲黑板,这个很重要)也确实实用,因此很多软件公司的笔试面试都喜欢考这个,还有大大小的程序方面...
  • 在对数组排序的算法中,复杂度为O(nlgn)的算法有:快速排序归并排序堆排序。由于堆排序需要将数据组织成一个最大堆,这对于链表来说需要将其重新构造为一个二叉树,这样做太过复杂并且浪费额外的空间。所以只能...
  • 快速排序和归并排序及其区别 首先在预期情况下的快速排序和归并排序时间复杂度都是O(NlogN), 在空间复杂度上,没使用临时栈的快速排序在空间上优于归并排序。 其次,在稳定性上来说,快速排序是不稳定的排序,...
  • 掌握选择排序、冒泡排序、合并排序快速排序归并排序的算法原理 分析不同排序算法的时间效率时间复杂度,以及理论值与实测数据的对比分析。 一、冒泡排序 算法伪代码: for i=1 to n for j=0 to n-i ...
  • 今天对一些排序简单的总结了一下,主要有冒泡排序,选择排序,快速排序和归并排序。 int a[10] = {8,5,2,3,6,9,7,4,1,0}; 冒泡排序 冒泡排序应该是我们在学习过程中学习到的第一个排序算法, for (int i=0;i&...
  • 快速排序归并排序

    2013-12-26 20:06:32
    归并排序与快速排序的比较次数,交换次数 运行时间的比较
  • 快速排序改变链接 快速排序改变节点值 所有源码测试函数 对单向链表的排序有2种形式,只改变节点的值 只改变链接// 节点 struct ListNode { int val; ListNode* next; ListNode(int v, ListNode* n = NULL) ...
  • 主要介绍了Scala实现冒泡排序、归并排序和快速排序的示例代码,小编觉得挺不错的,现在分享给大家,也给大家做个参考。一起跟随小编过来看看吧
  • 五、快速排序 六、归并排序 七、内部排序方法小节 一、排序的基本概念 1、排序 假设含n个记录的序列为{ R1, R2, …, Rn }其相应的关键字序列为 { K1,K2, …,Kn }。经过排序确定一种排列{ Rp1≤Rp2≤…≤Rpn},...
  • 实现并验证合并排序算法; 实现并验证快速排序算法(参考习题5.2第7a题,P140); 用递归与分治的方法设计并实现寻找第k小元素算法

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 166,977
精华内容 66,790
关键字:

快速排序和归并排序区别