十堰网站制作,快速网站,网站的百度推广怎么做,手机建设银行网站进不去排序算法汇总
参考书籍–《啊哈#xff01;算法》 作者#xff1a;啊哈磊
首先提出一个问题#xff1a;班内有5名同学#xff0c;成绩分别为5#xff0c;8#xff0c;2#xff0c;4#xff0c;2分#xff08;满分10分#xff09;#xff0c;需要将成绩从小到大排序…排序算法汇总
参考书籍–《啊哈算法》 作者啊哈磊
首先提出一个问题班内有5名同学成绩分别为58242分满分10分需要将成绩从小到大排序
简化版 桶排序 时间复杂度O(N)
import java.util.Scanner;public class Bucket_sort {public static void main(String[] args) {Scanner input new Scanner(System.in);int n input.nextInt();/*** 需要进行排序的数字范围在 0-5之间* */int[] a new int[6];/*** 注意并非将数据存起来而是在对应的“桶”内计数最后统计出现次数* */for (int i 0; i n; i) {int k input.nextInt();a[k];}/*** 打印 内循环控制重复数据要重复读取* */for (int i 0; i 6; i) {for (int j 0; j a[i] ; j) {System.out.println(i);}}}
}存疑一这样成绩是按顺序存起来了但是如果现在的情况是Lili 5分Tony 8分Joy 2分Peter 3分Ben 2分。如何在保证姓名和成绩对应的情况下排序呢 另一方面桶排序需要用到的“桶”的个数跟数据的最大值有关系这里满分为10分只需要10个桶但是如果数据量较少但是数据的值较大的时候则会浪费大量空间。
冒泡排序算法 时间复杂度O(n^2)
import java.util.Scanner;public class Bubble_sort {public static void main(String[] args) {Scanner input new Scanner(System.in);int[] a new int[100];int n input.nextInt();/*** 输入n个数* */for (int i 0; i n; i) {a[i] input.nextInt();}/*** 冒泡排序核心算法* */for (int i 0; i n-1; i) {for (int j i1; j n; j) {if (a[i] a[j]) {int temp a[i];a[i] a[j];a[j] temp;}}}/*** 打印* */for (int i 0; i n; i) {System.out.print(a[i] );}}
}上面的冒泡排序为基本的算法若想解决存疑一只需要稍加变通即可实现
存疑二冒泡排序解决了桶排序浪费空间的难题但是这种排序算法采用双重循环时间复杂度为指数级别效率实在是不够好有没有可以更快捷的方法呢
快速排序 时间复杂度O(N·logN)
import java.util.Scanner;public class Fast_sort {static int n;static int[] a;public static void main(String[] args) {Scanner input new Scanner(System.in);n input.nextInt();a new int[n];for (int i 0; i n; i) {a[i] input.nextInt();}fastsort(0, n-1);/*** 打印* */for (int i 0; i n; i) {System.out.print(a[i] );}}public static void fastsort(int left, int right) {if (left right) {return;}int temp a[left];int i left;int j right;/*** i j 的时候为“一趟”结束的时候* */while (i ! j) {/*** 顺序一定要从j开始* a[j]如果不小于temp则前进,a[i]如果不大于temp则前进** */while (a[j] temp i j) {j--;}while (a[i] temp i j) {i;}/*** 前进过程出现跳出while循环则需要进行交换* */if (i j) {int t a[i];a[i] a[j];a[j] t;}}/*** 基准归位* */a[left] a[i];a[i] temp;/*** 处理左侧* */fastsort(left, i-1);/*** 处理右侧* */fastsort(i1, right);}
}通过快速排序就可以很好的解决存疑二中没有解决的问题了这种排序算法在时间和空间上都得到了一个很好的利用。
再来一个问题给出一串数字这些数字没有顺序而且还有许多重复的我们需要完成排序和去重两个步骤 那么问题可以通过两种方法解决 1先去重后排序 解决思路利用桶排序在往“桶”中添加的时候不采用a[i];而是a[i] 1;这样即使是重复的也不会多次计数了。 2先排序后去重 解决思路可以利用冒泡和快排由于排序完的序列重复值都会在一个区间内这样在输出的时候加个if判断即可实现。
存疑三若是数据值十分巨大该如何选择算法 若数据量十分庞大又该如何选择算法
显然对于数据值较大的题目桶排序并不适合 而对于数据量较多的题目冒泡排序要运行相当长的时间。所以快速排序真的是一个有效、方便的算法呢
