【Java面试题九】算法篇
发布日期:2021-06-29 15:41:30
浏览次数:3
分类:技术文章
本文共 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 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
关注你微信了!
[***.104.42.241]2024年05月01日 02时24分40秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
10个业余时间可完成的项目,助你飞速提升编码能力!
2019-04-29
用深度学习打造艺术大师:照片变身的“魔法”
2019-04-29
必看!今年最火的五大Python框架
2019-04-29
掌握代码背后的这种语言,让你一招通吃天下!
2019-04-29
最终榜单!2019年人工智能的15个热门趋势
2019-04-29
揭秘卷积神经网络热力图:类激活映射
2019-04-29
骂谷歌,怼百度,批腾讯,吴军为何DISS互联网公司没得怕的?
2019-04-29
网络爬虫初涉——用python爬取网络小说
2019-04-29
Pycharm+tensorflow dropout 学习(三)
2019-04-29
Pycharm+tensorflow CNN 学习(四)
2019-04-29
用python暴力破解压缩包密码
2019-04-29
基于OpenCV 将图片进行预处理,转变为MNIST图片格式
2021-07-02
PyCharm+Tensorflow CNN调用训练好的模型进行预测 (五)
2021-07-02
物联网平台Node-red初涉——访问搭建的简易服务器
2021-07-02
2020-10-27
2019-04-29
OpenCV+python识别并打印HSV颜色
2019-04-29
2021-03-29
2019-04-29
网络攻击与防御--引言
2019-04-29
网络攻击与防御--网络协议漏洞
2019-04-29
sql注入: 判断注入点类型
2019-04-29