1. 全栈程序员必看首页

java实现10种排序算法[通俗易懂]

全栈程序员-站长 • • 未分类 • 阅读 27

java实现10种排序算法[通俗易懂]1.冒泡排序(BubbleSort)importjava.util.Arrays;//冒泡排序publicclassBubbleSort_01{ publicstaticvoidmain(String[]args){ inta[]={3,44,38,5,47,15,36,26,27,2,46,4,19,50,48}; //记录比较次数 intcount=0; //i=0,第一轮比较 for(inti=0;i<a.length-1;i

大家好，又见面了，我是你们的朋友全栈君。

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

版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。

发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/151781.html原文链接：https://javaforall.net

赞 (0)
0 0

关于作者

全栈程序员-站长的头像

全栈程序员-站长

133.5K 文章
3 粉丝
本网站汇聚当前互联网主流语音，持续更新，欢迎关注公众号“全栈程序员社区”
上一篇 2022年6月21日 下午6:46
下一篇 2022年6月21日 下午7:00


相关推荐

  • Vue一到三年面试题总结

    Vue一到三年面试题总结

    Vue一到三年面试题总结笔者粉丝群里的朋友们多部分的人都在找vue的工作而没有再找react工作，所以我之前总结的html，css，js，react面试题还不行，还要继续拓展vue的。。于是我就把大家在出去面试的时候遇到的vue面试题以粉丝们投稿的方式收集了起来做个汇总，希望能帮助到更多的朋友们~Vue面试题正文：1.vue全家桶包含哪些？答案：vue全家桶与react全家桶介绍2.v-model是什么？怎么使…

    全栈程序员-站长的头像 全栈程序员-站长
    2022年6月11日
    41
  • Pycharm与Pipenv的配合使用

    Pycharm与Pipenv的配合使用

    Pycharm与Pipenv的配合使用Pycharm 与 Pipenv 的配合使用第一步 Pipenv 的安装第二步创建 Pycharm 工程 配置 PipenvPipenv 常用命令第一步 Pipenv 的安装打开 Pycharm 在 Terminal 中输入 pipinstallus 安装 pipenv 如图所示 安装过程有点慢 耐心等待就行 再输入 wherepipenv 如果输出了 pipenv 刚安装的路径就说明安装成功 环境变量它也自动添加好了 第二步创建 Pycharm 工程 配置 Pipenv 安装好 pipenv 之

    全栈程序员-站长的头像 全栈程序员-站长
    2026年3月27日
    3
  • UART和USART有区别

    UART和USART有区别

    UART和USART有区别UART　　UART是一种通用串行数据总线，用于异步通信。该总线双向通信，可以实现全双工传输和接收。在嵌入式设计中，UART用于主机与辅助设备通信，如汽车音响与外接AP之间的通信，与PC机通信包括与监控调试器和其它器件，如EEPROM通信。　　UART的功能计算机内部采用并行数据，不能直接把数据发到Modem，必须经过UART整理才能进行异步传输，其过程为：CPU先把准备写入串行设备的数据…

    全栈程序员-站长的头像 全栈程序员-站长
    2022年5月19日
    40
  • CCriticalSection与CSingleLock

    CCriticalSection与CSingleLock

    CCriticalSection与CSingleLockCCriticalSectionAnobjectofclassCCriticalSectionrepresentsa“criticalsection”—asynchronizationobjectthatallowsonethreadatatimetoaccessaresourceorsectionofcode.Criticalse

    全栈程序员-站长的头像 全栈程序员-站长
    2022年7月21日
    16
  • Nvue入坑总结

    Nvue入坑总结

    Nvue入坑总结引入外部的 css 在 App vue 里写的公用的样式在 nvue 里是不生效 多个 nvue 想要使用公用的样式 需要引入外部的 css 由于 weex 的限制 不能在 style 节点下使用 import xxx css 这样的方式引入外部 css 需要使用如下方式引入 css stylesrc common test css style test color E96900 style stylesrc

    全栈程序员-站长的头像 全栈程序员-站长
    2026年3月16日
    2
  • MATLAB实现线性插值interp1的功能

    MATLAB实现线性插值interp1的功能

    MATLAB实现线性插值interp1的功能1.关于插值插值，它根据已知的数据序列（也可以理解为坐标中一连串离散的点），找到其中的规律；然后根据找到的这个规律，来对其中尚未有数据记录的点进数值的估计。2.关于线性插值线性插值是一种针对一维数据的插值方法，它根据一维数据序列中需要插值的点的左右邻近两个数据点来进行数值的估计。当然了它不是求这两个点数据大小的平均值（当然也有求平均值的情况），而是根据到这两个点的距离来分配它们的比重的。而对于一些边缘处的点也需要使用到外插：即通过找出最近的两个点，通过建立该两点之间的一元一次线性方程通过带入x即可以得

    全栈程序员-站长的头像 全栈程序员-站长
    2022年5月20日
    32

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

关注全栈程序员社区公众号