- 浏览: 189440 次
- 性别:
- 来自: 武汉
文章分类
最新评论
-
shuaijie506:
以前有点疑惑,现在终于明白了,线程安全是没问题的,想想也是,如 ...
jsp自定义标签 线程安全 -
Laster2800:
原来如此,想不到传统的标记处理器也是线程安全的,受教了。
jsp自定义标签 线程安全 -
GoingForward:
这篇文章是不是可以浓缩为下面几点:1.在非静态内部类中不可以声 ...
static class -
wellse:
呵呵,就是这样!!要的就是这个效果
jsp自定义标签 线程安全 -
xiaohuafyle:
JNDI
从大学到现在,参加过很多面试,经常会被问到一些基本的算法题,而大部分算法的理论及思想,我们曾经都能倒背如流,并且也用语言实现过,可由于在项目开发中应用的比较少,久而久之就忘记了,造成在面试中很尴尬的局面,然后回来查阅相关资料才发现就那么一回事,怎么在面试中就卡壳了呢?在此写下我在面试中经常被问到的一些基本的算法,全当复习。
一、冒泡排序
- package sort.bubble;
- import java.util.Random;
- /**
- * 依次比较相邻的两个数,将小数放在前面,大数放在后面
- * 冒泡排序,具有稳定性
- * 时间复杂度为O(n^2)
- * 不及堆排序,快速排序O(nlogn,底数为2)
- * @author liangge
- *
- */
- public class Main {
- public static void main(String[] args) {
- Random ran = new Random();
- int[] sort = new int[10];
- for(int i = 0 ; i < 10 ; i++){
- sort[i] = ran.nextInt(50);
- }
- System.out.print("排序前的数组为");
- for(int i : sort){
- System.out.print(i+" ");
- }
- buddleSort(sort);
- System.out.println();
- System.out.print("排序后的数组为");
- for(int i : sort){
- System.out.print(i+" ");
- }
- }
- /**
- * 冒泡排序
- * @param sort
- */
- private static void buddleSort(int[] sort){
- for(int i=1;i<sort.length;i++){
- for(int j=0;j<sort.length-i;j++){
- if(sort[j]>sort[j+1]){
- int temp = sort[j+1];
- sort[j+1] = sort[j];
- sort[j] = temp;
- }
- }
- }
- }
- }
package sort.bubble; import java.util.Random; /** * 依次比较相邻的两个数,将小数放在前面,大数放在后面 * 冒泡排序,具有稳定性 * 时间复杂度为O(n^2) * 不及堆排序,快速排序O(nlogn,底数为2) * @author liangge * */ public class Main { public static void main(String[] args) { Random ran = new Random(); int[] sort = new int[10]; for(int i = 0 ; i < 10 ; i++){ sort[i] = ran.nextInt(50); } System.out.print("排序前的数组为"); for(int i : sort){ System.out.print(i+" "); } buddleSort(sort); System.out.println(); System.out.print("排序后的数组为"); for(int i : sort){ System.out.print(i+" "); } } /** * 冒泡排序 * @param sort */ private static void buddleSort(int[] sort){ for(int i=1;i<sort.length;i++){ for(int j=0;j<sort.length-i;j++){ if(sort[j]>sort[j+1]){ int temp = sort[j+1]; sort[j+1] = sort[j]; sort[j] = temp; } } } } }
二、选择排序
- package sort.select;
- import java.util.Random;
- /**
- * 选择排序
- * 每一趟从待排序的数据元素中选出最小(或最大)的一个元素,
- * 顺序放在已排好序的数列的最后,直到全部待排序的数据元素排完。
- * 选择排序是不稳定的排序方法。
- * @author liangge
- *
- */
- public class Main {
- public static void main(String[] args) {
- Random ran = new Random();
- int[] sort = new int[10];
- for (int i = 0; i < 10; i++) {
- sort[i] = ran.nextInt(50);
- }
- System.out.print("排序前的数组为");
- for (int i : sort) {
- System.out.print(i + " ");
- }
- selectSort(sort);
- System.out.println();
- System.out.print("排序后的数组为");
- for (int i : sort) {
- System.out.print(i + " ");
- }
- }
- /**
- * 选择排序
- * @param sort
- */
- private static void selectSort(int[] sort){
- for(int i =0;i<sort.length-1;i++){
- for(int j = i+1;j<sort.length;j++){
- if(sort[j]<sort[i]){
- int temp = sort[j];
- sort[j] = sort[i];
- sort[i] = temp;
- }
- }
- }
- }
- }
package sort.select; import java.util.Random; /** * 选择排序 * 每一趟从待排序的数据元素中选出最小(或最大)的一个元素, * 顺序放在已排好序的数列的最后,直到全部待排序的数据元素排完。 * 选择排序是不稳定的排序方法。 * @author liangge * */ public class Main { public static void main(String[] args) { Random ran = new Random(); int[] sort = new int[10]; for (int i = 0; i < 10; i++) { sort[i] = ran.nextInt(50); } System.out.print("排序前的数组为"); for (int i : sort) { System.out.print(i + " "); } selectSort(sort); System.out.println(); System.out.print("排序后的数组为"); for (int i : sort) { System.out.print(i + " "); } } /** * 选择排序 * @param sort */ private static void selectSort(int[] sort){ for(int i =0;i<sort.length-1;i++){ for(int j = i+1;j<sort.length;j++){ if(sort[j]<sort[i]){ int temp = sort[j]; sort[j] = sort[i]; sort[i] = temp; } } } } }
三、快速排序
- package sort.quick;
- /**
- * 快速排序 通过一趟排序将要排序的数据分割成独立的两部分, 其中一部分的所有数据都比另外一部分的所有数据都要小,
- * 然后再按此方法对这两部分数据分别进行快速排序, 整个排序过程可以递归进行,以此达到整个数据变成有序序列。
- * @author liangge
- *
- */
- public class Main {
- public static void main(String[] args) {
- int[] sort = { 54, 31, 89, 33, 66, 12, 68, 20 };
- System.out.print("排序前的数组为:");
- for (int data : sort) {
- System.out.print(data + " ");
- }
- System.out.println();
- quickSort(sort, 0, sort.length - 1);
- System.out.print("排序后的数组为:");
- for (int data : sort) {
- System.out.print(data + " ");
- }
- }
- /**
- * 快速排序
- * @param sort 要排序的数组
- * @param start 排序的开始座标
- * @param end 排序的结束座标
- */
- public static void quickSort(int[] sort, int start, int end) {
- // 设置关键数据key为要排序数组的第一个元素,
- // 即第一趟排序后,key右边的数全部比key大,key左边的数全部比key小
- int key = sort[start];
- // 设置数组左边的索引,往右移动判断比key大的数
- int i = start;
- // 设置数组右边的索引,往左移动判断比key小的数
- int j = end;
- // 如果左边索引比右边索引小,则还有数据没有排序
- while (i < j) {
- while (sort[j] > key && j > start) {
- j--;
- }
- while (sort[i] < key && i < end) {
- i++;
- }
- if (i < j) {
- int temp = sort[i];
- sort[i] = sort[j];
- sort[j] = temp;
- }
- }
- // 如果左边索引比右边索引要大,说明第一次排序完成,将sort[j]与key对换,
- // 即保持了key左边的数比key小,key右边的数比key大
- if (i > j) {
- int temp = sort[j];
- sort[j] = sort[start];
- sort[start] = temp;
- }
- //递归调用
- if (j > start && j < end) {
- quickSort(sort, start, j - 1);
- quickSort(sort, j + 1, end);
- }
- }
- }
package sort.quick; /** * 快速排序 通过一趟排序将要排序的数据分割成独立的两部分, 其中一部分的所有数据都比另外一部分的所有数据都要小, * 然后再按此方法对这两部分数据分别进行快速排序, 整个排序过程可以递归进行,以此达到整个数据变成有序序列。 * @author liangge * */ public class Main { public static void main(String[] args) { int[] sort = { 54, 31, 89, 33, 66, 12, 68, 20 }; System.out.print("排序前的数组为:"); for (int data : sort) { System.out.print(data + " "); } System.out.println(); quickSort(sort, 0, sort.length - 1); System.out.print("排序后的数组为:"); for (int data : sort) { System.out.print(data + " "); } } /** * 快速排序 * @param sort 要排序的数组 * @param start 排序的开始座标 * @param end 排序的结束座标 */ public static void quickSort(int[] sort, int start, int end) { // 设置关键数据key为要排序数组的第一个元素, // 即第一趟排序后,key右边的数全部比key大,key左边的数全部比key小 int key = sort[start]; // 设置数组左边的索引,往右移动判断比key大的数 int i = start; // 设置数组右边的索引,往左移动判断比key小的数 int j = end; // 如果左边索引比右边索引小,则还有数据没有排序 while (i < j) { while (sort[j] > key && j > start) { j--; } while (sort[i] < key && i < end) { i++; } if (i < j) { int temp = sort[i]; sort[i] = sort[j]; sort[j] = temp; } } // 如果左边索引比右边索引要大,说明第一次排序完成,将sort[j]与key对换, // 即保持了key左边的数比key小,key右边的数比key大 if (i > j) { int temp = sort[j]; sort[j] = sort[start]; sort[start] = temp; } //递归调用 if (j > start && j < end) { quickSort(sort, start, j - 1); quickSort(sort, j + 1, end); } } }
四、插入排序
- package sort.insert;
- /**
- * 直接插入排序
- * 将一个数据插入到已经排好序的有序数据中,从而得到一个新的、个数加一的有序数据
- * 算法适用于少量数据的排序,时间复杂度为O(n^2)。是稳定的排序方法。
- */
- import java.util.Random;
- public class DirectMain {
- public static void main(String[] args) {
- Random ran = new Random();
- int[] sort = new int[10];
- for (int i = 0; i < 10; i++) {
- sort[i] = ran.nextInt(50);
- }
- System.out.print("排序前的数组为");
- for (int i : sort) {
- System.out.print(i + " ");
- }
- directInsertSort(sort);
- System.out.println();
- System.out.print("排序后的数组为");
- for (int i : sort) {
- System.out.print(i + " ");
- }
- }
- /**
- * 直接插入排序
- *
- * @param sort
- */
- private static void directInsertSort(int[] sort) {
- for (int i = 1; i < sort.length; i++) {
- int index = i - 1;
- int temp = sort[i];
- while (index >= 0 && sort[index] > temp) {
- sort[index + 1] = sort[index];
- index--;
- }
- sort[index + 1] = temp;
- }
- }
- }
package sort.insert; /** * 直接插入排序 * 将一个数据插入到已经排好序的有序数据中,从而得到一个新的、个数加一的有序数据 * 算法适用于少量数据的排序,时间复杂度为O(n^2)。是稳定的排序方法。 */ import java.util.Random; public class DirectMain { public static void main(String[] args) { Random ran = new Random(); int[] sort = new int[10]; for (int i = 0; i < 10; i++) { sort[i] = ran.nextInt(50); } System.out.print("排序前的数组为"); for (int i : sort) { System.out.print(i + " "); } directInsertSort(sort); System.out.println(); System.out.print("排序后的数组为"); for (int i : sort) { System.out.print(i + " "); } } /** * 直接插入排序 * * @param sort */ private static void directInsertSort(int[] sort) { for (int i = 1; i < sort.length; i++) { int index = i - 1; int temp = sort[i]; while (index >= 0 && sort[index] > temp) { sort[index + 1] = sort[index]; index--; } sort[index + 1] = temp; } } }
五、顺便贴个二分搜索法
- package search.binary;
- public class Main {
- public static void main(String[] args) {
- int[] sort = {1,2,3,4,5,6,7,8,9,10};
- int mask = binarySearch(sort,6);
- System.out.println(mask);
- }
- /**
- * 二分搜索法,返回座标,不存在返回-1
- * @param sort
- * @return
- */
- private static int binarySearch(int[] sort,int data){
- if(data<sort[0] || data>sort[sort.length-1]){
- return -1;
- }
- int begin = 0;
- int end = sort.length;
- int mid = (begin+end)/2;
- while(begin <= end){
- mid = (begin+end)/2;
- if(data > sort[mid]){
- begin = mid + 1;
- }else if(data < sort[mid]){
- end = mid - 1;
- }else{
- return mid;
- }
- }
- return -1;
- }
- }
发表评论
-
Jetty例子
2010-11-07 22:04 1490import java.io.IOException; ... -
IReport一些注意
2010-09-05 22:02 1318用的是 Ireport2.0版本 更高版本可能没有这个问题 ... -
jsp自定义标签 线程安全
2010-08-28 14:21 3964我们在编写自定义标签的时候设置属性如下 public cl ... -
[转]Java类加载原理解析
2009-11-04 21:47 1163转载 Java 类加载原理解析 ... -
线程上下文类加载器
2009-11-04 21:46 5552线程上下文类加载器 问题:何时使用Thread. ... -
JDBC Sybase
2009-11-04 21:02 4015import java.sql.Connection; im ... -
JDK 5.0 泛型 动态参数 枚举
2009-11-04 21:02 3061import java.util.ArrayList;impo ... -
再看heap 和stack,还有多了解内存
2009-11-03 16:28 1165heap 1.堆石一个“运行时”数据区,类实例化的对象就是从 ... -
java中读取Properties文件
2009-10-23 12:58 1540java 中读取Properties 文 ... -
JNI
2009-10-22 22:15 1421... -
Hibernate经典文章
2009-10-19 12:37 923Lazy Loading (Load&Get) ... -
JNDI
2009-10-15 14:15 2635最近写书,写到JNDI,到处查资料,发现所有的中文资料都对JN ... -
JDBC连接各种数据库
2009-10-14 10:13 940常用JDBC连接数据库方法总结如下: 一、DB2 Cl ... -
java并发的一些题目
2009-09-24 23:41 989a 回答 结果又一下 几种情况 execute here Ca ... -
static class
2009-08-19 14:55 18132在一个类中创建另外 ... -
C++ 对象参数传递
2009-08-07 12:08 1655#include<iostream.h> cla ... -
递归与间接递归
2009-08-07 11:02 48841. 介绍 递归技术允许 ... -
concurrent lib的学习
2009-07-13 17:51 9811.关于BlockingQueue的学习,这是一个阻塞的队列, ... -
应该看的书籍
2009-07-12 21:33 9311.代码大全 2.人月神话 3.设计模式 4.网格计算 ... -
错误总结
2009-07-02 17:46 7621.static inner class和 non-s ...
相关推荐
各种查找与排序算法,笔试面试过程中经常遇到的题目。。
一个堆排序算法 c++写的 逻辑相同 可自行 改为java 写一个堆排序算法 c++ 写一个堆排序算法 c++ 写一个堆排序算法 c++ 写一个堆排序算法 c++ 写一个堆排序算法 c++ 写一个堆排序算法 c++ 写一个堆排序算法 c++ 写一...
java实现的常用的几种基本排序算法,插入、交换、选择、归并
经典面试算法题N道,经典面试算法题N道,经典面试算法题N道,经典面试算法题N道
基于C++/C实现 7种面试管经常问到的排序算法
IT常见的面试题目,各种排序算法的Java代码实现,内部有代码和详细的注释信息。
2. 冒泡排序 3. 1~100共一百个自然数,放入一个只有99个元素的数组中,找出没有被放入数组的这个数; 4. 字符串的反转输出 5. 截取字符串, 如果该字符串是“abc我的”,当截取的字节数是3时候就是"abc',如果是4,...
it面试算法题整理 全 包括笔试面试常考的 剑指offer 程序员面试宝典 各种排序算法等 自己总结的 自己总结的 找工作笔试面试用
排序算法是程序员必备的基础知识,弄明白它们的原理和实现很有必要。本文中将通过非常细节的动画展示出算法的原理,配合代码更容易理解。 由于待排序的元素数量不同,使得排序过程中涉及的存储器不同,可将排序方法...
面试算法总结1.把二元查找树转变成排序的双向链表 题目: 输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。 要求不能创建任何新的结点,只调整指针的指向。 10 / \ 6 14 / \ / \ 4 8 12 16 ...
八种排序算法分别是: 1.冒泡排序; 2.选择排序; 3.插入排序; 4.快速排序; 5.归并排序; 6.希尔排序; 7.二叉排序; 8.计数排序; 其中快排尤为重要,几乎可以说IT开发类面试必考内容,而希尔排序和归并...
国庆在家没事做,写了下几个排序算法,int转char char转int,经常在面试中会遇到,给大家提供参考
快速排序 插入排序 冒泡排序 选择排序 面试经典
最快的排序算法 腾讯算法面试题:64匹马8个跑道需要多少轮才能选出最快的四匹(详解)?,排序算法数据结构
汇总了计算机研究生复试有关算法分析与设计各章节简答题,使用了易于口头表达的语言进行了总结。包括算法分析与设计基本概念及各章节问题回答。可供研究生复试或相关专业岗位面试...18. 基于分治法的排序算法有哪些?
C++实现各种排序算法,是初学者和面试应聘者必备资料
常见:排序算法相关面试题1
问题四:冒泡排序问题五:快速排序2017/5/9 下午4:06前端算法面试题第2页 共5页问题六:不借助临时变量,进行两个整数的交换问题七:找出下列正数组的最大
包含了四种常见的排序算法,是招聘面试时常出的题目,最好自己编译跑一遍
常见排序算法java实现,包括快速排序,归并排序,堆排序三个常用nlogn复杂度的算法