java的排序算法有哪些
这篇文章主要介绍“java的排序算法有哪些”,在日常操作中,相信很多人在java的排序算法有哪些问题上存在疑惑,小编查阅了各式资料,整理出简单好用的操作方法,希望对大家解答”java的排序算法有哪些”的疑惑有所帮助!接下来,请跟着小编一起来学习吧!
网站的建设创新互联专注网站定制,经验丰富,不做模板,主营网站定制开发.小程序定制开发,H5页面制作!给你焕然一新的设计体验!已为成都工商代办等企业提供专业服务。
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]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 && insertValue4.希尔排序(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=a[i] && i 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 (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 < 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; imax) { max = arr[i]; } else if(arr[i] < min) { min = arr[i]; } } //最大值和最小值的差 int diff = max - min; //桶列表 ArrayList > 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 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] }}基数排序是用空间换时间的经典算法,当数据足够多时,达到几千万级别时内存空间可能不够用了,发生堆内存溢出
到此,关于“java的排序算法有哪些”的学习就结束了,希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习,快去试试吧!若想继续学习更多相关知识,请继续关注创新互联网站,小编会继续努力为大家带来更多实用的文章!
文章标题:java的排序算法有哪些
标题来源:http://myzitong.com/article/pgeego.html