程序员经验分享-hwhale

java实现10种排序算法

2023-05-16

1.冒泡排序(Bubble Sort)

在这里插入图片描述

import java.util.Arrays;
//冒泡排序
public class BubbleSort_01 {
	public static void main(String[] args) {
		int a[]={3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};
		//记录比较次数
		int count=0;
		//i=0,第一轮比较
		for (int i = 0; i < a.length-1; i++) {
			//第一轮，两两比较
			for (int j = 0; j < a.length-1-i; j++) {
				if (a[j]>a[j+1]) {
					int temp=a[j];
					a[j]=a[j+1];
					a[j+1]=temp;
				}
				count++;
			}
		}
		System.out.println(Arrays.toString(a));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
		System.out.println("一共比较了："+count+"次");//一共比较了：105次
	}
}

冒泡排序的优化1:

import java.util.Arrays;
public class BubbleSort1_01 {
	public static void main(String[] args) {
		int a[]={3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};
		int count=0;
		for (int i = 0; i < a.length-1; i++) {
			boolean flag=true;
			for (int j = 0; j < a.length-1-i; j++) {
				if (a[j]>a[j+1]) {
					int temp=a[j];
					a[j]=a[j+1];
					a[j+1]=temp;
					flag=false;
				}
				count++;
			}
			if (flag) {
				break;
			}
		}
		System.out.println(Arrays.toString(a));// [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
		System.out.println("一共比较了："+count+"次");//一共比较了：95次
	}
}

2.选择排序(Select Sort)

在这里插入图片描述

import java.util.Arrays;
//选择排序:先定义一个记录最小元素的下标，然后循环一次后面的，找到最小的元素，最后将他放到前面排序好的序列。
public class SelectSort_02 {
	public static void main(String[] args) {
		int a[]={3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};
		for (int i = 0; i < a.length-1; i++) {
			int index=i;//标记第一个为待比较的数
			for (int j = i+1; j < a.length; j++) { //然后从后面遍历与第一个数比较
				if (a[j]<a[index]) {  //如果小,就交换最小值
					index=j;//保存最小元素的下标
				}
			}
			//找到最小值后，将最小的值放到第一的位置，进行下一遍循环
			int temp=a[index];
			a[index]=a[i];
			a[i]=temp;
		}
		System.out.println(Arrays.toString(a));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
	}
}

3.插入排序(Insert Sort)

在这里插入图片描述

import java.util.Arrays;
//插入排序:定义一个待插入的数，再定义一个待插入数的前一个数的下标，然后拿待插入数与前面的数组一一比较，最后交换。
public class InsertSort_03 {
	public static void main(String[] args) {
		int a[]={3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};
		for (int i = 0; i < a.length; i++) {  //长度不减1，是因为要留多一个位置方便插入数
			//定义待插入的数
			int insertValue=a[i];
			//找到待插入数的前一个数的下标
			int insertIndex=i-1;
			while (insertIndex>=0 && insertValue <a[insertIndex]) {//拿a[i]与a[i-1]的前面数组比较
				a[insertIndex+1]=a[insertIndex];
				insertIndex--;
			}
			a[insertIndex+1]=insertValue;
		}
		System.out.println(Arrays.toString(a));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
	}
}

4.希尔排序(Shell Sort)

在这里插入图片描述

import java.util.Arrays;
//希尔排序：插入排序的升级
public class ShellSort_04 {
	public static void main(String[] args) {
		int a[]={3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};
		int count=0;//比较次数
		for (int gap=a.length / 2; gap > 0; gap = gap / 2) {
			//将整个数组分为若干个子数组
			for (int i = gap; i < a.length; i++) {
				//遍历各组的元素
				for (int j = i - gap; j>=0; j=j-gap) {
					//交换元素
					if (a[j]>a[j+gap]) {
						int temp=a[j];
						a[j]=a[j+gap];
						a[j+gap]=temp;
						count++;
					}
				}
			}
		}
		System.out.println(count);//16
		System.out.println(Arrays.toString(a));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
	}
}

5.快速排序(Quick Sort)

参考这篇博客
在这里插入图片描述
在这里插入图片描述在这里插入图片描述在这里插入图片描述

import java.util.Arrays;
//快速排序：冒泡排序的升华版
public class QuickSort_05 {
	public static void main(String[] args) {
		//int a[]={50,1,12,2};
		int a[]={3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};
		quicksort(a,0,a.length-1);
		System.out.println(Arrays.toString(a));
	}
	private static void quicksort(int[] a, int low, int high) {
		int i,j;
		if (low>high) {
			return;
		}
		i=low;
		j=high;
		int temp=a[low];//基准位,low=length时，会报异常，java.lang.ArrayIndexOutOfBoundsException: 4 ，所以必须在if判断后面,就跳出方法。
		while(i<j){
			//先从右边开始往左递减，找到比temp小的值才停止
			while ( temp<=a[j] && i<j) {
				j--;
			}
			//再看左边开始往右递增，找到比temp大的值才停止
			while ( temp>=a[i] && i<j) {
				i++;
			}
			//满足 i<j 就交换,继续循环while(i<j)
			if (i<j) {
				int t=a[i];
				a[i]=a[j];
				a[j]=t;
			}
		}
		//最后将基准位跟  a[i]与a[j]相等的位置，进行交换,此时i=j
		a[low]=a[i];
		a[i]=temp;
		//左递归
		quicksort(a, low, j-1);
		//右递归
		quicksort(a, j+1, high);	
	}
}

6.归并排序(Merge Sort)

在这里插入图片描述

在这里插入图片描述

import java.util.Arrays;
//归并排序
public class MergeSort_06 {
	public static void main(String[] args) {
		int a[]={3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};
		//int a[]={5,2,4,7,1,3,2,2};
		int temp[]=new int[a.length];
		mergesort(a,0,a.length-1,temp);
		System.out.println(Arrays.toString(a));
	}
	private static void mergesort(int[] a, int left, int right, int[] temp) {
		//分解
		if (left<right) {
			int mid=(left+right)/2;
			//向左递归进行分解
			mergesort(a, left, mid, temp);
			//向右递归进行分解
			mergesort(a, mid+1, right, temp);
			//每分解一次便合并一次
			merge(a,left,right,mid,temp);
		}
	}
	/**
	 *
	 * @param a  待排序的数组
	 * @param left  左边有序序列的初始索引
	 * @param right 右边有序序列的初始索引
	 * @param mid	中间索引
	 * @param temp	做中转的数组
	 */
	private static void merge(int[] a, int left, int right, int mid, int[] temp) {
		int i=left; //初始i，左边有序序列的初始索引
		int j=mid+1;//初始化j，右边有序序列的初始索引（右边有序序列的初始位置即中间位置的后一位置）
		int t=0;//指向temp数组的当前索引，初始为0
		
		//先把左右两边的数据（已经有序）按规则填充到temp数组
		//直到左右两边的有序序列，有一边处理完成为止
		while (i<=mid && j<=right) {
			//如果左边有序序列的当前元素小于或等于右边的有序序列的当前元素，就将左边的元素填充到temp数组中
			if (a[i]<=a[j]) {
				temp[t]=a[i];
				t++;//索引向后移
				i++;//i后移
			}else {
				//反之，将右边有序序列的当前元素填充到temp数组中
				temp[t]=a[j];
				t++;//索引向后移
				j++;//j后移
			}
		}
		//把剩余数据的一边的元素填充到temp中
		while (i<=mid) {
			//此时说明左边序列还有剩余元素
			//全部填充到temp数组
			temp[t]=a[i];
			t++;
			i++;
		}
		while (j<=right) {
			//此时说明左边序列还有剩余元素
			//全部填充到temp数组
			temp[t]=a[j];
			t++;
			j++;
		}
		//将temp数组的元素复制到原数组
		t=0;
		int tempLeft=left;
		while (tempLeft<=right) {
			a[tempLeft]=temp[t];
			t++;
			tempLeft++;
		}
	}
	
}

7.堆排序(Heap Sort)

堆排序
第一步：构建初始堆buildHeap， 使用sink(arr,i, length)调整堆顶的值;
第二步：将堆顶元素下沉 目的是将最大的元素浮到堆顶来，然后使用sink(arr, 0,length)调整;
堆排序图解：链接
在这里插入图片描述

public class Heap_Sort_07 {
	public static void main(String[] args) {
		int a[]={3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};	
		sort(a);
		System.out.println(Arrays.toString(a));
	}
    public static void sort(int[] arr) {
        int length = arr.length;
        //构建堆
        buildHeap(arr,length);
        for ( int i = length - 1; i > 0; i-- ) {
            //将堆顶元素与末位元素调换
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            //数组长度-1 隐藏堆尾元素
            length--;
            //将堆顶元素下沉 目的是将最大的元素浮到堆顶来
            sink(arr, 0,length);
        }
    }
    private static void buildHeap(int[] arr, int length) {
        for (int i = length / 2; i >= 0; i--) {
            sink(arr,i, length);
        }
    }
    
    private static void sink(int[] arr, int index, int length) {
        int leftChild = 2 * index + 1;//左子节点下标
        int rightChild = 2 * index + 2;//右子节点下标
        int present = index;//要调整的节点下标

        //下沉左边
        if (leftChild < length && arr[leftChild] > arr[present]) {
            present = leftChild;
        }

        //下沉右边
        if (rightChild < length && arr[rightChild] > arr[present]) {
            present = rightChild;
        }

        //如果下标不相等 证明调换过了
        if (present != index) {
            //交换值
            int temp = arr[index];
            arr[index] = arr[present];
            arr[present] = temp;

            //继续下沉
            sink(arr, present, length);
        }
    }
}

8.计数排序 (Count Sort)

参考链接
算法的步骤如下：

  • 找出待排序的数组array中最大的元素max
  • 统计数组中每个值为 i 的元素出现的次数，存入数组 count 的第 i 项
  • 对所有的计数累加（从 count中的第一个元素开始，每一项和前一项相加）
  • 反向填充目标数组：将每个元素 i 放在新数组的第 count [i] 项，每放一个元素就将 count [i] 减去

在这里插入图片描述

import java.util.Arrays;
public class CountSort_08 {
	public static void main(String[] args) {
		int[] array = { 4, 2, 2, 8, 3, 3, 1 };
		// 找到数组中最大的值 ---> max:8
		int max = findMaxElement(array);
		int[] sortedArr = countingSort(array, max + 1);
		System.out.println("计数排序后的数组： " + Arrays.toString(sortedArr));
	}
	private static int findMaxElement(int[] array) {
		int max = array[0];
		for (int val : array) {
			if (val > max)
				max = val;
		}
		return max;
	}
	private static int[] countingSort(int[] array, int range) { //range:8+1
		int[] output = new int[array.length]; 
		int[] count = new int[range];
		//初始化： count1数组
		for (int i = 0; i < array.length; i++) {
			count[array[i]]++;
		}
		//计数： count2数组，累加次数后的，这里用count2区分
		for (int i = 1; i < range; i++) {
			count[i] = count[i] + count[i - 1];
		}
		//排序：最后数组
		for (int i = 0; i < array.length; i++) {
			output[count[array[i]] - 1] = array[i];
			count[array[i]]--;
		}
		return output;
	}
}

9.桶排序(Bucket Sort)

参考链接

桶排序可以看成是计数排序的升级版，它将要排的数据分到多个有序的桶里，每个桶里的数据再单独排序，再把每个桶的数据依次取出，即可完成排序。
桶排序：将值为i的元素放入i号桶，最后依次把桶里的元素倒出来。
在这里插入图片描述桶排序序思路：

  • 设置一个定量的数组当作空桶子。
  • 寻访序列，并且把项目一个一个放到对应的桶子去。
  • 对每个不是空的桶子进行排序。
  • 从不是空的桶子里把项目再放回原来的序列中。
public class BucketSort_09 {
    public static void sort(int[] arr){
        //最大最小值
        int max = arr[0];
        int min = arr[0];
        int length = arr.length;

        for(int i=1; i<length; i++) {
            if(arr[i] > max) {
                max = arr[i];
            } else if(arr[i] < min) {
                min = arr[i];
            }
        }

        //最大值和最小值的差
        int diff = max - min;

        //桶列表
        ArrayList<ArrayList<Integer>> bucketList = new ArrayList<>();
        for(int i = 0; i < length; i++){
            bucketList.add(new ArrayList<>());
        }

        //每个桶的存数区间
        float section = (float) diff / (float) (length - 1);

        //数据入桶
        for(int i = 0; i < length; i++){
            //当前数除以区间得出存放桶的位置 减1后得出桶的下标
            int num = (int) (arr[i] / section) - 1;
            if(num < 0){
                num = 0;
            }
            bucketList.get(num).add(arr[i]);
        }

        //桶内排序
        for(int i = 0; i < bucketList.size(); i++){
            //jdk的排序速度当然信得过
            Collections.sort(bucketList.get(i));
        }

        //写入原数组
        int index = 0;
        for(ArrayList<Integer> arrayList : bucketList){
            for(int value : arrayList){
                arr[index] = value;
                index++;
            }
        }
    }
}

10.基数排序(Raix Sort)

我们假设有一个待排序数组[53，3，542，748，14，214]，那么如何使用基数排序对其进行排序呢？
首先我们有这样的十个一维数组，在基数排序中也叫桶。用桶排序实现。
在这里插入图片描述第一轮，以元素的个位数进行区分：[542，53，3，14，214,748]
在这里插入图片描述第二轮，以元素的十位数进行区分：[3，14，214，542，748，53]在这里插入图片描述第三轮，以元素的百位数进行区分：[3，14，53，214，542，748]
在这里插入图片描述

import java.util.Arrays;
public class RaixSort_10 {
	public static void main(String[] args) {
		int[] arr = { 53, 3, 542, 748, 14, 214 };

		// 得到数组中最大的数
		int max = arr[0];// 假设第一个数就是数组中的最大数
		for (int i = 1; i < arr.length; i++) {
			if (arr[i] > max) {
				max = arr[i];
			}
		}
		// 得到最大数是几位数
		// 通过拼接一个空串将其变为字符串进而求得字符串的长度，即为位数
		int maxLength = (max + "").length();

		// 定义一个二维数组，模拟桶，每个桶就是一个一维数组
		// 为了防止放入数据的时候桶溢出，我们应该尽量将桶的容量设置得大一些
		int[][] bucket = new int[10][arr.length];
		// 记录每个桶中实际存放的元素个数
		// 定义一个一维数组来记录每个桶中每次放入的元素个数
		int[] bucketElementCounts = new int[10];

		// 通过变量n帮助取出元素位数上的数
		for (int i = 0, n = 1; i < maxLength; i++, n *= 10) {
			for (int j = 0; j < arr.length; j++) {
				// 针对每个元素的位数进行处理
				int digitOfElement = arr[j] / n % 10;
				// 将元素放入对应的桶中
				// bucketElementCounts[digitOfElement]就是桶中的元素个数，初始为0，放在第一位
				bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
				// 将桶中的元素个数++
				// 这样接下来的元素就可以排在前面的元素后面
				bucketElementCounts[digitOfElement]++;
			}
			// 按照桶的顺序取出数据并放回原数组
			int index = 0;
			for (int k = 0; k < bucket.length; k++) {
				// 如果桶中有数据，才取出放回原数组
				if (bucketElementCounts[k] != 0) {
					// 说明桶中有数据，对该桶进行遍历
					for (int l = 0; l < bucketElementCounts[k]; l++) {
						// 取出元素放回原数组
						arr[index++] = bucket[k][l];
					}
				}
				// 每轮处理后，需要将每个bucketElementCounts[k]置0
				bucketElementCounts[k] = 0;
			}
		}
		System.out.println(Arrays.toString(arr));//[3, 14, 53, 214, 542, 748]
	}
}

基数排序是用空间换时间的经典算法,当数据足够多时，达到几千万级别时内存空间可能不够用了，发生堆内存溢出

在这里插入图片描述

————————————————
版权声明：本文为CSDN博主「~wangweijun」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_42453117/article/details/100036347

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

java实现10种排序算法 的相关文章

  • opengles共享纹理

    OpenGL ES 3 0中引入的 外部纹理 xff08 External Textures xff09 扩展 xff0c 允许将OpenGL纹理对象绑定到由外部API创建的纹理对象 xff0c 例如相机采集到的图像 视频流或其他图像数据

  • https 证书工具 Letsencrypt 简单教程

    https取代http是大势所趋 xff0c https的好处本文不在赘述 xff0c 很多公司和机构都在推进这一进程 xff0c Apple公司甚至规定 xff0c iOS上的App应用必须使用https 因此 xff0c 正是受到App

  • Linux简单命令使用笔记

    之前一直用虚拟机 xff0c 其实购买一台阿里云服务器学习linxu更加的方便快捷 阿里云服务器购买 1 electerm连接登录linux SecureCRT和SFTP 最近linux连接工具electerm 上面是两款不同的连接linu

  • 软件工程的十大模型

    1 软件生命周期模型 软件生命周期由软件定义 软件开发与运维 xff08 也称软件维护 xff09 3个时期组成 xff0c 每个时期又进一步划分成若干个阶段 问题定义 xff1a 要解决的问题是什么 xff1f 通过对客户的访问调查 xf

  • WEEK6 限时测试A - 掌握魔法の东东 II

    A 掌握魔法 东东 II 题目描述 从瑞神家打牌回来后 xff0c 东东痛定思痛 xff0c 决定苦练牌技 xff0c 终成赌神 xff01 东东有 A B 张扑克牌 每张扑克牌有一个大小 整数 xff0c 记为a xff0c 范围区间是

  • WEEK13 作业 A - TT 的神秘任务1（必做）

    A TT 的神秘任务1 xff08 必做 xff09 题目描述 这一天 xff0c TT 遇到了一个神秘人 神秘人给了两个数字 xff0c 分别表示 n 和 k xff0c 并要求 TT 给出 k 个奇偶性相同的正整数 xff0c 使得其和

  • WEEK14 作业 C - Q老师的考验（必做）

    C Q老师的考验 xff08 必做 xff09 题目描述 Q老师 对数列有一种非同一般的热爱 xff0c 尤其是优美的斐波那契数列 这一天 xff0c Q老师 为了增强大家对于斐波那契数列的理解 xff0c 决定在斐波那契的基础上创建一个新

  • 程序设计与实践 模拟题四 201809-3 元素选择器

    201809 3 元素选择器 题目描述 题解 本题是一道思维难度不大的模拟题 实现过程和思想都比较简单 xff0c 具体实现比较难 xff0c 认真仔细即可 xff08 但是自己一开始写的代码只得了80分 xff0c 又比较了其他人的代码才

  • idea中添加maven远程仓库

    idea无法自动下载依赖的解决方法 xff1a 1 xff1a 选择自己的maven目录 配置文件setting xml和仓库repository xff0c 并勾选2个Override 2 点击Runner 在VM Options那一行添

  • 详解C++中的指针结构体数组以及指向结构体变量的指针

    这篇文章主要介绍了C 43 43 中的指针结构体数组以及指向结构体变量的指针的用法 是C 43 43 入门学习中的基础知识 需要的朋友可以参考下 C 43 43 结构体数组 一个结构体变量中可以存放一组数据 xff08 如一个学生的学号 姓

  • bad substitution

    初接触shell脚本 xff0c 在vim中写代码 xff0c 出现了好几次 Bad substitution 我的错误有两种 xff1a 开始的的指定脚本环境 应该是 bin bash 在编译运行时 也应该用 bash 的使用错误 xff

  • Re.从零开始--基于UbuntuServer 20.04-OpenStack平台搭建_

    基于UbuntuServer 20 04 OpenStack平台搭建 前言 xff1a 本文档基于ubuntu server20 04版本和OpenStack Victoria搭建openstack环境 部署最小化Ubuntu openst

  • win10系统vvv连接不上，提示:“在连接完成前，连接被远程计算机终止”的解决办法

    进入 控制面板 网络和共享中心 更改适配器设置 右键点 vvv连接 属性 安全 选择 允许使用这些协议 xff0c 以下选项全部打勾即可 未加密的密码 质询握手身份验证协议 Microsoft CHAP Version2

  • CSP 2021 S组游记

    这是异想之旅的一篇水文 xff0c 技术无关 占个坑 xff0c 晚上更新 说说初赛 xff1a 我的竞赛老师是很重视初赛的 xff0c 整个暑假一半的时间集训 xff0c 而一半的集训时间都是面对初赛 模拟题大家做的量不同 xff0c 但

  • linux命令解压压缩rar文件的详细步骤

    一 widonds下打包rar文件并上传 yum install lrzsz rz test rar 二 下载并安装rar软件 2 1 下载 mkdir p home oldboy tools cd home oldboy tools wg

  • 配置pvst详解

    配置 pvst 在学习pvst之前 xff0c 先要学习一下stp STP生成树 思科默认有stp配置 1 选择根网桥 xff08 root bridge xff09 xff08 这个是必须的配置 xff09 选择根网桥的依据是网桥ID x

  • （真）手把手教你配置Ubuntu大数据Hadoop环境

    目录 一 前期准备 VMware tools安装 基本配置 root配置 网络配置 软件源配置 二 创建hadoop用户和文件 用户创建 小插曲 三 FTP配置 四 配置java环境及安装eclipse 安装eclipse 安装java环境

  • Ubuntu安装配置hbase完美解决方案

    目录 一 解决版本号打印失败问题 二 配置伪分布式 三 运行简单的hbase shell命令 这篇文章需要配合前一篇文章一起食用更加美味 xff08 真 xff09 手把手教你配置Ubuntu大数据Hadoop环境 一 解决版本号打印失败问

  • Linux shell实现阶乘

    bin sh read p 34 请输入想计算的数字 34 num 首先定义一个num参数接受为命令行的第一个参数 expr num 43 1 amp gt dev null 利用expr计算时参数必须是整数的原则 xff0c 如果返回零则

  • DHCP服务器搭建

    DHCP服务器搭建 安装dhcp服务器 使用yum y install dhcp 命令安装dhcp服务 修改配置文件 修改最大租约和默认租约为8天和2天 修改地址池 网关地址 以及子网掩码相关配置 总配置如下 Dhcp服务启动成功

随机推荐

热门标签