【Java面试题九】算法篇
发布日期:2021-06-29 15:41:30
浏览次数:2
分类:技术文章
本文共 4789 字,大约阅读时间需要 15 分钟。
比较一下几种常用的排序算法,简单的写一下你知道的几种排序算法?
比较:
1.稳定性比较
插入排序、冒泡排序、二叉树排序、二路归并排序及其他线形排序是稳定的
选择排序、希尔排序、快速排序、堆排序是不稳定的
2.时间复杂性比较
插入排序、冒泡排序、选择排序的时间复杂性为O(n2)
其它非线形排序的时间复杂性为O(nlog2n)
线形排序的时间复杂性为O(n);
3.辅助空间的比较
线形排序、二路归并排序的辅助空间为O(n);
其它排序的辅助空间为O(1);
4.其它比较
*插入、冒泡排序的速度较慢,但参加排序的序列局部或整体有序时,这种排序能达到较快的速度,但是在这种情况下,快速排序反而慢了。
*当n较小时,对稳定性不作要求时宜用选择排序,对稳定性有要求时宜用插入或冒泡排序。
*若待排序的记录的关键字在一个明显有限范围内时,且空间允许是用桶排序。
*当n较大时,关键字元素比较随机,对稳定性没要求宜用快速排序。
*当n较大时,关键字元素可能出现本身是有序的,对稳定性有要求时,空间允许的情况下宜用归并排序。
*当n较大时,关键字元素可能出现本身是有序的,对稳定性没有要求时宜用堆排序。
常见的排序算法:
选择排序
public class SelectionSort { public void selectionSort(int[] array) { int temp; for (int i = 0; i < array.length - 1; i++) { for (int j = i + 1; j <= array.length - 1; j++) { if (array[i] > array[j]) { // 注意和冒泡排序的区别,这里是i和j比较。 temp = array[i]; array[i] = array[j]; array[j] = temp; } } // 打印每趟排序结果 for (int m = 0; m <= array.length - 1; m++) { System.out.print(array[m] + "\t"); } System.out.println(); } } public static void main(String[] args) { SelectionSort selectionSort = new SelectionSort(); int[] array = { 5, 69, 12, 3, 56, 789, 2, 5648, 23 }; selectionSort.selectionSort(array); for (int m = 0; m <= array.length - 1; m++) { System.out.print(array[m] + "\t"); } }}
插入排序
public class InsertSort { public void insertSort(int[] array, int first, int last) { int temp, i, j; for (i = first + 1; i <= last - 1; i++) { temp = array[i]; j = i - 1; while (j >= first && array[j] > temp) { array[j + 1] = array[j]; j--; } array[j + 1] = temp; // 打印每次排序结果 for (int m = 0; m <= array.length - 1; m++) { System.out.print(array[m] + "\t"); } System.out.println(); } } public static void main(String[] args) { InsertSort insertSort = new InsertSort(); int[] array = { 5, 69, 12, 3, 56, 789, 2, 5648, 23 }; insertSort.insertSort(array, 0, array.length); for (int i = 0; i <= array.length - 1; i++) { System.out.print(array[i] + "\t"); } }}
快速排序
public class QuickSort { public int partition(int[] sortArray, int low, int height) { int key = sortArray[low]; while (low < height) { while (low < height && sortArray[height] >= key) height--; sortArray[low] = sortArray[height]; while (low < height && sortArray[low] <= key) low++; sortArray[height] = sortArray[low]; } sortArray[low] = key; // 打印每次排序结果 for (int i = 0; i <= sortArray.length - 1; i++) { System.out.print(sortArray[i] + "\t"); } System.out.println(); return low; } public void sort(int[] sortArray, int low, int height) { if (low < height) { int result = partition(sortArray, low, height); sort(sortArray, low, result - 1); sort(sortArray, result + 1, height); } } public static void main(String[] args) { QuickSort quickSort = new QuickSort(); int[] array = { 5, 69, 12, 3, 56, 789, 2, 5648, 23 }; for (int i = 0; i <= array.length - 1; i++) { System.out.print(array[i] + "\t"); } System.out.println(); quickSort.sort(array, 0, 8); for (int i = 0; i <= array.length - 1; i++) { System.out.print(array[i] + "\t"); } }}
希尔排序
public class ShellSort { public void shellSort(int[] array, int n) { int i, j, gap; int temp; for (gap = n / 2; gap > 0; gap /= 2) { for (i = gap; i < n; i++) { for (j = i - gap; j >= 0 && array[j] > array[j + gap]; j -= gap) { temp = array[j]; array[j] = array[j + gap]; array[j + gap] = temp; } // 打印每趟排序结果 for (int m = 0; m <= array.length - 1; m++) { System.out.print(array[m] + "\t"); } System.out.println(); } } } public static void main(String[] args) { ShellSort shellSort = new ShellSort(); int[] array = { 5, 69, 12, 3, 56, 789, 2, 5648, 23 }; shellSort.shellSort(array, array.length); for (int m = 0; m <= array.length - 1; m++) { System.out.print(array[m] + "\t"); } }}
转载地址:https://codingchaozhang.blog.csdn.net/article/details/79650599 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
第一次来,支持一个
[***.219.124.196]2024年04月30日 11时00分48秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
torch 模型运行时间与forward没对应的可能原因
2019-04-29
JavaScript 的addEventListener() 事件监听详解!
2019-04-29
上传图片到阿里云OSS和获取上传图片的url的详解 !
2019-04-29
经典面试题:如何保证缓存与数据库的双写一致性?
2019-04-29
一份来自亚马逊工程师的Google面试指南,GitHub收获9.8万星,已翻译成中文
2019-04-29
硬货 | Redis 性能问题分析
2019-04-29
Kafka为什么这么快?
2019-04-29
Java 生产者和消费者面试题
2019-04-29
生产者消费者问题
2019-04-29
本机电脑连接虚拟机redis失败解决方法
2019-04-29
DM365 应用层gpio控制
2019-04-29
linux i2c子系统abc
2019-04-29
力扣的买卖股票的最佳时机 III之解法(Python3)
2019-04-29
LeetCode 合并两个有序链表 解法 (Python)
2019-04-29
力扣的删除排序链表中的重复元素解法 (Python3)
2019-04-29
力扣的环形链表解法 (Python)
2019-04-29
CSS3 帧动画(Sprite,直译叫雪碧图)
2019-04-29
Java 父线程与子线程相互通信的方法
2019-04-29
Java CompletableFuture
2019-04-29
Redis 六种淘汰策略和三种删除策略
2019-04-29