本篇文章给大家带来了关于java的相关知识，其中主要整理了10种排序算法实例的相关问题，包括了冒泡排序、选择排序、插入排序等等内容，下面一起来看一下，希望对大家有帮助。
推荐学习：《java视频教程》
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[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:
立即学习“Java免费学习笔记（深入）”；
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[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.选择排序(ｓｅｌｅｃｔ 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 3.插入排序(ｉｎｓｅｒｔ Sort)
tps://img.php.cn/upload/article/000/000/067/b3f75638c97a493ecae2237fc6ea0427-2.gif" alt="在这里插入图片描述">
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 =0 && insertvalue 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 =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);//16System.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=a[i] && i6.归并排序(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 (left7.堆排序(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 arr[present]) { present = leftChild; } //下沉右边 if (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:8int 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+1int[] output = new int[array.length]; int[] count = new int[range];//初始化： count1数组for (int i = 0; i 9.桶排序(Bucket Sort)
参考链接
桶排序可以看成是计数排序的升级版，它将要排的数据分到多个有序的桶里，每个桶里的数据再单独排序，再把每个桶的数据依次取出，即可完成排序。
桶排序：将值为i的元素放入i号桶，最后依次把桶里的元素倒出来。
503
1463e4d10b7c44bcc-12.gif" alt="在这里插入图片描述">桶排序序思路：- 设置一个定量的数组当作空桶子。
- 寻访序列，并且把项目一个一个放到对应的桶子去。
- 对每个不是空的桶子进行排序。
- 从不是空的桶子里把项目再放回原来的序列中。
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 max) { max = arr[i]; } else if(arr[i] > bucketList = new ArrayList(); for(int i = 0; i ()); } //每个桶的存数区间 float section = (float) diff / (float) (length - 1); //数据入桶 for(int i = 0; i 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 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 基数排序是用空间换时间的经典算法,当数据足够多时，达到几千万级别时内存空间可能不够用了，发生堆内存溢出
推荐学习：《java视频教程》
