程序员经验分享-hwhale

八十六.快速排序与归并排序（查找与排序（二））——JAVA

2023-11-15

查找与排序（一）
查找与排序（三）
查找与排序（四）

一、分治法

  • 分治法：将原问题划分成若干个规模较小而结构与原问题一致的子问题；递归地解决这些子问题，然后再合并其结果，就得到原问题的解。
  • 容易确定运行时间，是分支算法的优点之一。
  • 分治模式在每一层递归上都有三个步骤：
    1、分解：将原问题分解成一系列子问题；
    2、解决：递归地解决各子问题。若子问题足够小，则直接有解；
    3、合并：将子问题的结果合并成原问题的解。

分治法的关键点：

  • 原问题可以一直分解为形式相同子问题，当子问题规模较小时，可自然求解，如一个元素本身有序
  • 子问题的解通过合并可以得到原问题的解
  • 子问题的分解以及解的合并一定是比较简单的，否则分解和合并所花的时间可能超出暴力解法，得不偿失

二、快速排序算法

  1. 分解：数组A [p……r] 被划分为两个子数组A [p……q-1] 和A [q+1,r] ，使得A [q] 为大小居中的数，左侧A [p……q-1] 中的每个元素都小于等于它，而右侧A [q+1，r] 中的每个元素都大于等于它。其中计算下标q也是划分过程的一部分。
  2. 解决：通过递归调用快速排序，对子数组A [p……q-1] 和A [q+1,r] 进行排序
  3. 合并：因为子数组都是原址排序的，所以不需要合并，数组A [p……r] 已经有序
QuickSort(A, p, r)
if p<r
   q = Partition(A, p, r)   //主要实现划分这一部分
   QuickSort(A, p, q-1)
   QuickSort(A, q+1, r)

三、快速排序的划分算法
1、一遍单向扫描法：

  • 一遍扫描法的思路是，用两个指针将数组划分为三个区间
  • 扫描指针左边是确认小于等于主元的
  • 扫描指针到某个指针中间为未知的，因此我们将第二个指针称为未知区间末指针，末指针的右边区间为确认大于主元的元素

在这里插入图片描述

import java.util.Scanner;

public class LianXi {
	/*QuickSort
	 * quickSort(A,p,r)
	 *    if(p<r)
	 *      q = partition(A, p, r)
	 *      quickSort(A, p, q-1)
	 *      quickSort(A, q+1, r)
	 *      
	 * partition(A, p, r):
	 *     pivot = A[p]
	 *     sp = p + 1     //扫描指针
	 *     bigger = r     //右侧指针
	 *     while(sp<=bigger):
	 *         if(A[sp]<=pivot)  //扫描元素小于主元，左指针向右移动
	 *            sp++
	 *         else
	 *           swap(A, sp, bigger) //扫描元素大于主元，二指针的元素交换，右指针左移
	 *           bigger--
	 *           
	 *      swap(A, p, bigger)    //结束循环后，主元与右侧指针需要交换
	 *      return bigger
	 * */
	
	public static void quickSort(int []A, int p, int r){
		if(p<r){
			int q = partition(A, p, r);
			quickSort(A, p, q-1);
			quickSort(A,q+1,r);
		}
	}
	
	public static int partition(int[]A, int p, int r){
		int pivot = A[p];    //选中位数最好，这里没有选
		int sp = p + 1;
		int bigger = r;
		while(sp<=bigger){
			if(A[sp]<=pivot){
				sp++;
			}
			else{
				swap(A,sp,bigger);
				bigger--;
			}
		}
		swap(A, p, bigger);   
		return bigger;
	}

	public static void swap(int[] A, int sp, int bigger) {
		int temp = A[sp];
		A[sp] = A[bigger];
		A[bigger] = temp;		
	}
	
	public static void main(String[] args){
		Scanner in = new Scanner(System.in);
		int N = in.nextInt();
		int []A = new int[N];
		for(int i = 0; i<N; i++){
			A[i] = in.nextInt();
		}
		System.out.println("初始数组为：");
		for(int i = 0; i<N; i++){
			System.out.print(A[i] + " ");
		}
		System.out.println("\n");
		quickSort(A,0,N-1);    //这里取了第一个元素为主元，应该取中位数
		System.out.println("排序后数组为：");
		for(int j = 0; j<N; j++){
			System.out.print(A[j] + " ");
		}
	}
}

在这里插入图片描述
2、双向扫描法
双向扫描法的思路是，头尾指针往中间扫描，从左找到大于主元的元素，从右找到小于等于主元的元素二者交换，继续扫描，直到左侧无大元素，右侧无小元素。

import java.util.Scanner;

public class LianXi {
	/*QuickSort
	 * quickSort(A,p,r)
	 *    if(p<r)
	 *      q = partition2(A, p, r)
	 *      quickSort(A, p, q-1)
	 *      quickSort(A, q+1, r)
	 *      
	 * partition2(A, p, r):
	 *   pivot = A[p]
	 *   left = p + 1
	 *   right = r
	 *   while(left<=right):
	 *   //left不停往右走，直到遇到大于主元的元素
	 *        while(left<=right && A[left]<=pivot) left++ //循环退出时，left一定是指向第一个大于大于主元的位置
	 *        while(left<=right && A[right]>pivot) right-- //循环退出时，right一定是指向最后一个小于等于主元的位置
	 *        if(left<right)
	 *           swap(A,left,right)
	 *           
	 *   //while退出时，两者交错，且right指向的是最后一个小于等于主元的位置，也就是主元应该呆的位置
	 *   swap(A, p, right)
	 *   return right
	 *   
	 * */
	
	public static void quickSort(int []A, int p, int r){
		if(p<r){
			int q = partition2(A, p, r);
			quickSort(A, p, q-1);
			quickSort(A, q+1, r);
		}
	}
	
	public static int partition2(int[]A, int p, int r){
		int pivot = A[p];
		int left = p + 1;
		int right = r;
		while(left <= right){
			while(left <= right && A[left] <= pivot){
				left++;
			}
			while(left <= right && A[right] > pivot){
				right--;
			}
			if(left < right)
				swap(A, left, right);
		}
		swap(A, p, right);
		return right;
	}
		
	public static void swap(int[] A, int left, int right) {
		int temp = A[left];
		A[left] = A[right];
		A[right] = temp;		
	}
	
	public static void main(String[] args){
		Scanner in = new Scanner(System.in);
		int N = in.nextInt();
		int []A = new int[N];
		for(int i = 0; i<N; i++){
			A[i] = in.nextInt();
		}
		System.out.println("初始数组为：");
		for(int i = 0; i<N; i++){
			System.out.print(A[i] + " ");
		}
		System.out.println("\n");
		quickSort(A,0,N-1);        //这里取了第一个元素为主元，应该取中位数
		System.out.println("排序后数组为：");
		for(int j = 0; j<N; j++){
			System.out.print(A[j] + " ");
		}
	}
}

在这里插入图片描述
3、三指针分区法
① 如果数组中存在很多与主元等值的元素,那么在对主元左、右侧进行快速排序时,可以不用对那些与主元等值的元素进行排序
② 增设一个等值指针,来标记第一个与主元相等的元素,最终将区域划分为三部分：
1.左侧为所有小于主元的元素
2.中间为所有等于主元的元素
3.右侧为所有大于主元的元素
在这里插入图片描述

import java.util.Scanner;

public class LianXi {
	/*QuickSort
	 * quickSort(A,p,r)
	 *    if(p<r)
	 *      q = partition3(A, p, r)
	 *      quickSort(A, p, q-1)
	 *      quickSort(A, q+1, r)
	 *      
	 * partition3(A, p, r):
	 *   pivot = A[p]
	 *   sp = p + 1
	 *   equal = sp
	 *   bigger = r
	 *   //当sp扫描到的数字小于主元，则下标为sp和equal的需要交换数据，这样就又将小于主元的放在一起了，然后sp和equal都要自增
		 //当sp扫描到的数字等于主元，直接将sp自增
		 //当sp扫描到的数字大于主元，就将小标为sp和bigger上的数据交换，bigger再自减(和单向扫描分区法处理一样)
	 *   while(sp<=bigger):
	 *       if(A[sp] < pivot) 
	 *			swap(array, equal, sp);
	 *			equal++;
	 *			sp++;
	 *		
	 *		else if(A[sp] == num) 
	 *			sp++;
	 *		
	 *		else if(A[sp] > num) 
	 *			swap(A, sp, bigger);
	 *			bigger--;
	 *  
	 *   swap(A, p, bigger)
	 *   return bigger
	 *   
	 * */
	
	public static void quickSort(int []A, int p, int r){
		if(p<r){
			int q = partition3(A, p, r);
			quickSort(A, p, q-1);
			quickSort(A, q+1, r);
		}
	}
	
	public static int partition3(int[]A, int p, int r){
		int pivot = A[p];
		int sp = p + 1;
		int equal = sp;
		int bigger = r;
		while(sp<=bigger){
			if(A[sp] < pivot){
				swap(A, equal, sp);
				sp++;
				equal++;
			}
			else if(A[sp] == pivot){
				sp++;
			}
			else if(A[sp] > pivot){
				swap(A, sp, bigger);
				bigger--;
			}
		}
		swap(A, p, bigger);
		return bigger;
	}
		
	public static void swap(int[] A, int left, int right) {
		int temp = A[left];
		A[left] = A[right];
		A[right] = temp;		
	}
	
	public static void main(String[] args){
		Scanner in = new Scanner(System.in);
		int N = in.nextInt();
		int []A = new int[N];
		for(int i = 0; i<N; i++){
			A[i] = in.nextInt();
		}
		System.out.println("初始数组为：");
		for(int i = 0; i<N; i++){
			System.out.print(A[i] + " ");
		}
		System.out.println("\n");
		quickSort(A,0,N-1);        //这里取了第一个元素为主元，应该取中位数
		System.out.println("排序后数组为：");
		for(int j = 0; j<N; j++){
			System.out.print(A[j] + " ");
		}
	}
}

在这里插入图片描述
四、快速排序优化
1、三点中值法


public class LianXi {
	
	public static void quickSort(int []A, int p, int r){
		if(p<r){
			int q = partition2(A, p, r);
			quickSort(A, p, q-1);
			quickSort(A, q+1, r);
		}
	}
	
	public static int partition2(int[]A, int p, int r){
		//优化，在p,r,mid之间，选一个中间值作为主元
		int midIndex = p + ((r - p) >> 1);  //中间下标
		int midValueIndex = -1;             //中值的下标
		if(A[p]<=midIndex && A[p]>=A[r]){
			midValueIndex = p;
		}
		else if(A[r]<=midIndex && A[r]>=A[p]){
			midValueIndex = r;
		}
		else{
			midValueIndex = midIndex;
		}
		swap(A, p, midValueIndex);
		int pivot = A[p];
		int left = p + 1;
		int right = r;
		while(left <= right){
			while(left <= right && A[left] <= pivot){
				left++;
			}
			while(left <= right && A[right] > pivot){
				right--;
			}
			if(left < right)
				swap(A, left, right);
		}
		swap(A, p, right);
		return right;
	}
	
	//交换函数	
	public static void swap(int[] A, int left, int right) {
		int temp = A[left];
		A[left] = A[right];
		A[right] = temp;		
	}
	
	//生成随机数函数
	public static int [] gennerateArray(int len ,int min, int max){
		int []arr = new int[len];
		for(int i = 0; i<len; i++){
			arr[i] = (int)(Math.random() * (max-min+1) + 1);
		}
		return arr;
	}
	
	public static void main(String[] args){
		int []A = gennerateArray(10,1,10);
		System.out.println("初始数组为：");
		for(int i = 0; i<A.length; i++){
			System.out.print(A[i] + " ");
		}
		System.out.println("\n");
		quickSort(A,0,A.length-1);
		System.out.println("排序后数组为：");
		for(int j = 0; j<A.length; j++){
			System.out.print(A[j] + " ");
		}
	}
}

在这里插入图片描述
2、待排序列表较短时(>=8)，用插入排序


public class LianXi {
	
	public static void quickSort(int []A, int p, int r){
		if(p<r){
			//待排序个数小于等于8的时候，插入排序
			if(p-r+1<=0){
				insertsort(A,p,r);
			}
			else{
				int q = partition2(A, p, r);
				quickSort(A, p, q-1);
				quickSort(A, q+1, r);
			}
		}
	}
	
	public static int partition2(int[]A, int p, int r){
		int pivot = A[p];
		int left = p + 1;
		int right = r;
		while(left <= right){
			while(left <= right && A[left] <= pivot){
				left++;
			}
			while(left <= right && A[right] > pivot){
				right--;
			}
			if(left < right)
				swap(A, left, right);
		}
		swap(A, p, right);
		return right;
	}
	
	//插入排序函数
	 static void Sort(int []arr){
		insertsort(arr, 0, arr.length-1);
	}
	public static void insertsort(int []arr, int low, int hight){
		for(int j = low + 1; j<=hight; j++){
			int x = arr[j];
			int index = j - 1;
			while(index>=low && x<arr[index]){
				arr[index+1] = arr[index];
				index--;
			}
			arr[index+1] = x;
		}
	}
	
	//交换函数	
	public static void swap(int[] A, int left, int right) {
		int temp = A[left];
		A[left] = A[right];
		A[right] = temp;		
	}
	
	//生成随机数函数
	public static int [] gennerateArray(int len ,int min, int max){
		int []arr = new int[len];
		for(int i = 0; i<len; i++){
			arr[i] = (int)(Math.random() * (max-min+1) + 1);
		}
		return arr;
	}
	
	public static void main(String[] args){
		int []A = gennerateArray(10,1,10);
		System.out.println("初始数组为：");
		for(int i = 0; i<A.length; i++){
			System.out.print(A[i] + " ");
		}
		System.out.println("\n");
		quickSort(A,0,A.length-1);
		System.out.println("排序后数组为：");
		for(int j = 0; j<A.length; j++){
			System.out.print(A[j] + " ");
		}
	}
}

在这里插入图片描述

五、归并排序

  • 归并排序算法完全依照了分治模式
    1、分解：将 n 个元素分成各含 n / 2 个元素的子序列；
    2、解决：对两个子序列递归地排序；
    3、合并：合并两个已排序的子序列以得到排序结果

  • 和快速排序不同的是
    1、归并的分解较为随意
    2、重点是合并

  • 算法描述
    归并操作的工作原理如下：
    1、申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
    2、设定两个指针，最初位置分别为两个已经排序序列的起始位置
    3、比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
    4、重复步骤3直到某一指针超出序列尾
    5、将另一序列剩下的所有元素直接复制到合并序列尾

import java.util.Scanner;

public class LianXi {
	/*
	 *    MergerSort
	 *       mergeSort(A, p ,r){
	 *           if(p<r){
	 *              mid = p + ((r - p) >> 1)
	 *              mergeSort(A, p, mid);   //对左侧排序
	 *              mergeSort(A, mid+1, r); //对右侧排序
	 *              merge(A, p, mid, r)     //合并
	 *           }
	 *       }
	 *       helper = [A.length]
	 *       merge(A, p, mid, r){
	 *          // 先把A的数据拷贝到help中
	 *          copy(A, p, helper, p, r-p+1);
	 *          left = p //左侧队伍的头部指针，指向待比较的元素
	 *          right = mid + 1  //右侧队伍的头部的头部指针，指向待比较的元素
	 *          current = p //原数组的指针，指向待填入数据的位置
	 *          
	 *          while(left<=mid && right<=r){
	 *               if(helper[left]<=helper[right]){
	 *                   A[current] = helper[left]
	 *                   current++
	 *                   left++
	 *               }
	 *               else{
	 *                   A[current] = helper[right]
	 *                   current++
	 *                   right++
	 *               }
	 *          }
	 *          
	 *          //左指针可能没到头;右边指针没到头也没关系
	 *          while(left<=mid){
	 *             A[current] = helper[left]
	 *             current++
	 *             left+++
	 *          }
	 *       }
	 * 
	 * */
	 public static int []helper;
	 
	 public static void mergeSort(int[] arr){
		 helper = new int[arr.length];
		 mergeSort(arr, 0 , arr.length - 1);
	 }
	 
	 public static void mergeSort(int []A, int p, int r){
		 if(p<r){
			 int mid = p + ((r - p) >> 1);
			 mergeSort(A, p, mid);   
			 mergeSort(A, mid+1, r); 
			 merge(A, p, mid, r);    
		 }
	 }
	 
	 public static void merge(int []A, int p, int mid, int r){
		 System.arraycopy(A, p, helper, p, r - p + 1);
		 int left = p;
		 int right = mid + 1;
		 int current = p;
		 
		 while(left<=mid && right<=r){
			 if(helper[left] <= helper[right]){
				 A[current] = helper[left];
				 current++;
				 left++;
			 }
			 else{
				 A[current] = helper[right];
				 current++;
				 right++;
			 }
		 }
		 
		 while(left <= mid){
			 A[current] = helper[left];
			 current++;
			 left++;
		 }
	 }
	 
	 public static void main(String[] args){
		 Scanner in = new Scanner(System.in);
		 int N = in.nextInt();
		 int [] A = new int[N];
		 for(int i = 0; i<N; i++){
			 A[i] = in.nextInt();
		 }
		 System.out.println("初始数组为：");
		 for(int i = 0; i<N; i++){
			 System.out.print(A[i] + " ");
		 }
		 System.out.println("\n");
		 mergeSort(A);
		 System.out.println("归并排序后，数组为： ");
		 for(int i = 0; i<N; i++){
			 System.out.print(A[i] + " ");
		 }
	 }
}

在这里插入图片描述

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

笔记

八十六.快速排序与归并排序（查找与排序（二））——JAVA 的相关文章

  • vue之路由的嵌套（父子路由）

    路由的嵌套 1 配置路由 main js文件中 import Users from components Users import UserAdd from components Users UserAdd import UserList

  • 第二章 Scala入门——让你的代码跑起来

    一 Scala的安装方法 要使用Scala 首先需要保证已经安装好了Java 8 对于Linux操作系统 Java 8已经默认安装了 而使用Windows操作系统的用户 则需要在Java官网下载安装包进行安装 请在CMD PowerShel

随机推荐

  • 小米解bl锁跳过168小时_红米K30S至尊纪念版秒解BL工具分享支持小米红米机型秒解BL跳过168小时...

    目前小米的新机 官方风控都默认绑定7天也就是168小时才能解锁BL 部分账号需要绑定15天才能满足条件 导致很多爱玩机的小伙伴被拒门外 并不是所有人都愿意等待官方解锁时候 而跳过168小时解锁 也成为了很多小伙伴希望的事情 本工具来自ROM

  • 操作系统CPU调度

    概述 多道程序操作系统的基础 通过在进程之间切换CPU 操作系统可以提高计算机的吞吐率 对于单处理器系统 每次只允许一个进程运行 任何其他进程必须等待 直到CPU空闲能被调度为止 CPU按一定的调度算法从就绪队列中选择一个进程 把CPU的使

  • TorchVision中使用FasterRCNN+ResNet50+FPN进行目标检测

    TorchVision中给出了使用ResNet 50 FPN主干 backbone 构建Faster R CNN的pretrained模型 模型存放位置为https download pytorch org models fasterrcn

  • PE文件资源解析（七）manifest资源的解析

    mainfest资源 在这里指的是资源类型为RT MANIFEST的资源信息 通过ResHacker看到的效果图如下 manifest资源存储编码格式是UTF 8 开始3个字节是EF BB BF 解析代码如下 UTF8 EF BB BF H

  • Java练习10：输入两个正整数m和n，求其最大公约数和最小公倍数

    辗转相除法 package com qiqi test import java util Scanner 输入两个正整数m和n 求其最大公约数和最小公倍数 辗转相除法 1 用大数m 小数n得第一个余数 2 余数为0则n为最大公约数 3 余数

  • 【数据库原理选择题1-4章】

    1 1 数据库系统概述 1 1 DB DBMS 和DBS 三者之间的关系是 A DBMS包括DB和DBS B DB 包括DBMS和DBS C 不能相互包括 D DBS包括DB和DBMS 正确答案 D 2 位于用户和操作系统之间的一层数据管理

  • VS2017 登录账户时，反复让输入密码，而一直无法登陆。

    问题描述 VS2017 登录账户时 反复让输入密码 而一直无法登陆成功 最后显示无法刷新此账户凭据 解决办法 在排除是自己账户或者网络有问题后 通过清理用户数据解决问题 具体步骤如下 使用管理员权限打开命令终端 转到VS安装目录下的 Com

  • torch中的model.eval()、model.train()详解

    个人简介 深度学习图像领域工作者 工作总结链接 https blog csdn net qq 28949847 article details 128552785 链接中主要是个人工作的总结 每个链接都是一些常用demo 代码直接复制运行即

  • 欧几里得距离（欧式距离）

    文章目录 一 定义 二 公式 一 定义 欧几里得度量 欧氏距离 Euclidean Metric Euclidean Distance 指在m维空间中两个点之间的真实距离 或者向量的自然长度 即该点到原点的距离 比如 在二维和三维空间中的欧

  • 液滴/液膜蒸发过程—in文件模拟-后处理分析-Ovito/Python绘图

    关注 M r m a t e r i a l color Violet rm Mr material Mr material

  • FDR计算

    FDR计算 FDR的计算很简单 我折腾了一上午主要是因为遇到了以下几个问题 问题 FDR是什么 有什么用 怎么计算 我把几个模型的P值都合并成一个表了 所以每次运算FDR时 我需挑选特定的对象 我有多个模型 所以我想着要如何构建循环 FDR

  • 机器学习-人为设置函数方法和神经网络方法解决智能五子棋问题

    2 智能决策 2 1 博弈树模型算法 2 1 1 全局估算函数 此次项目中评估函数有两种 1 人为设定函数方法 更具人的经验 对一些特定的棋形在棋盘上进行检索 并且计数 最后赋予相应权值求和得到对棋盘的评价值 典型的棋形有 活一 活二 活三

  • 集成学习-理论概述

    1 集成学习概述 集成学习 ensemble learning 本身不是一个单独的机器学习算法 而是通过构建并结合多个机器学习器来完成学习任务 集成学习的特点 集成方法是一种将几种机器学习技术组合成一个预测模型的元算法 以减小方差 bagg

  • IDEA中如何导入module并成功运行

    在写Java项目的时候我们通常需要导入module 需要注意的是导入过程需要以下两大步骤 否则会出现无法运行的情况 以下我以导入 service edu 模块为例 一 将module文件拷贝到工程目录下 直接将需要导入的module文件 s

  • 李宏毅深度学习——优化方法

    记录了关于梯度的历史 SGD SGD with Momentum 防止gradient为0 SGD停止不动了 sgd with momentum 前面的移动会累加到下一步 sgd with momentum 前面的移动会累加到下一步 所以小

  • 【07节】Python3+Selenium4自动化 unittest 测试框架详解

    文章目录 1 unittest 框架介绍 2 创建单元测试步骤 3 unittest 模块介绍 3 1 TestCase 类 3 1 1 TestCase 类常用方法 3 1 2 TestCase 类其他方法 3 2 setUp 与 tea

  • 【cpu or gpu】【tensorflow】怎么查看用的是CPU还是GPU

    方法1 from tensorflow python client import device lib print device lib list local devices 参考博客 可用设备为 name device CPU 0 dev

  • 设计模式之桥接模式

    文章目录 一 手机操作问题 1 传统方案解决手机操作问题 2 传统方案解决手机操作问题分析 二 桥接模式 1 基本介绍 2 原理类图 三 桥接模式解决手机操作的问题 1 类图 2 代码 2 抽象类 抽象类子类 行为类接口 接口实现类 客户端

  • 关于api-ms-win-crt-runtimel1-1-0.dll缺失问题的解决方法

    1 问题描述 在win7系统中安装一个截图软件Snipaste时 出现api ms win crt runtimel1 1 0 dll缺失问题 如下图 2 问题原因 在网上查找资料 发现说是在C window system 或者C wind

  • 八十六.快速排序与归并排序（查找与排序（二））——JAVA

    查找与排序 一 查找与排序 三 查找与排序 四 一 分治法 分治法 将原问题划分成若干个规模较小而结构与原问题一致的子问题 递归地解决这些子问题 然后再合并其结果 就得到原问题的解 容易确定运行时间 是分支算法的优点之一 分治模式在每一层递

热门标签