- 浏览: 179988 次
- 性别:
- 来自: 深圳
文章分类
- 全部博客 (103)
- Java综合 (19)
- java模式 (1)
- java 包详解 (8)
- 需要阅读的书目 (1)
- Json (1)
- MySQL (2)
- zkoss (2)
- svn (1)
- JavaScript (1)
- html (1)
- 试题集锦 (6)
- 试题集锦_poj (1)
- Vim 操作 (2)
- Linux 操作 (5)
- NS2 学习 (2)
- 网络 (4)
- c/c++ (7)
- WNS - Wired Network Simulator (1)
- 网络信息体系结构 (16)
- MIPS (1)
- Java图形化编程 (2)
- 数据结构 (1)
- 数学 (3)
- 爬虫 (1)
- 搜索引擎 (1)
- NetFPGA (1)
- Directshow (1)
- 小软件 (2)
- FFMPEG (1)
- Windows Socket 网络编程 (5)
- Git (1)
- IntelliJ IDEA (0)
- Plone (1)
- Python (1)
最新评论
-
不要叫我杨过:
受教了,高手
Heritrix架构分析 -
springaop_springmvc:
apache lucene开源框架demo使用实例教程源代码下 ...
Lucene 3.0.2 使用入门 -
zxw961346704:
值得学习的算法
Java 计算器 -
medicine:
Thread.sleep(1000); 会使线程进入 TIM ...
Java.lang.Thread 和 Java.lang.ThreadGroup -
tangzlboy:
嗯,不错!收藏。
Java 入门
详见代码。
向一个已经排好序的数组中插入新的数据,使用二分查找来进行位置确定,时间复杂度为(log N)。
package com.java.sort; import java.util.Arrays; public class Sort { /** * 冒泡排序 * * @param array */ public static void bubble(int[] array) { for (int i = 0; i < array.length; i++) { for (int j = i + 1; j < array.length; j++) { if (array[i] > array[j]) { int temp = array[i]; array[i] = array[j]; array[j] = temp; } } } } /** * 选择排序 * * @param array */ public static void selection(int[] array) { for (int i = 0; i < array.length; i++) { int min = i;// the index of minimum number for (int j = i + 1; j < array.length; j++) { if (array[j] < array[min]) { min = j; } } if (i != min) { int temp = array[i]; array[i] = array[min]; array[min] = temp; } } } /** * 从index=1开始,然后index+1,一直到index=array.length-1。每次比较排序index。 插入排序的递归实现,尾递归 * * @param array * @param index */ public static void insertion1(int[] array, int index) { if (index > 0 && index < array.length) { int key = array[index]; int i = index - 1; for (; i >= 0 && array[i] > key; i--) { array[i + 1] = array[i]; } array[i + 1] = key; insertion1(array, index + 1); } } /** * 插入排序 使用场合:数组越接近于有序,插入排序所需做的工作越少 * * @param array */ public static void insertion(int[] array) { for (int i = 1; i < array.length; i++) { int key = array[i]; int j = i - 1; for (; j >= 0 && array[j] > key; j--) { array[j + 1] = array[j]; } array[j + 1] = key; } } /** * 希尔排序 改进的插入排序算法 * * @param array */ public static void shell(int[] array) { for (int space = array.length / 2; space > 0; space /= 2) { space = (space % 2 == 0 ? (space + 1) : (space));// 为了来取消那些space为偶数的情况。因为如果不排除这一项,在排序的时候会有重复的排序. for (int i = 0; i < space; i++) { sort_array_space(array, i, space); } } } /** * 为了辅助shell排序而设计的,类似于插入排序,只不过加入了space * * @param array * @param first * @param space */ private static void sort_array_space(int[] array, int first, int space) { for (int i = first + space; i < array.length; i += space) { int key = array[i]; int j = i - space; for (; j >= first && array[j] > key; j -= space) { array[j + space] = array[j]; } array[j + space] = key; } } /** * 归并排序的主函数。 * 为了让调用变得简单,实际上可以直接使用第二个主函数 * 在java中,sort(Object[] arr)使用便是归并排序 * 归并排序的效率是 nlog2n(2是底数),缺点是需要另外一个数组 * @param array */ public static void merge(int[] array){ mergeSort(array,0,array.length-1); } /** * 归并排序第二个主函数 * @param array * @param left * @param right */ private static void mergeSort(int[] array, int left, int right) { if (left < right) { int middle = (left + right) / 2; mergeSort(array, left, middle); mergeSort(array, middle + 1, right); mergeArray(array, left, middle, right); } } /** * 将 array 数组中left 到 right的内容进行排序,并 * @param array * @param left * @param middle * @param right */ private static void mergeArray(int[] array, int left, int middle, int right) { int[] temp = new int[array.length]; int i = left; int j = middle + 1; int index = left; while ((i <= middle) && (j <= right)) { if (array[i] <= array[j]) { temp[index++] = array[i++]; } else { temp[index++] = array[j++]; } } if (i > middle) { for (int k = j; k <= right; k++) { temp[index++] = array[k]; } } else { for (int k = i; k <= middle; k++) { temp[index++] = array[k]; } } for (int k = left; k <= right; k++) { array[k] = temp[k]; } } /** * 快速排序的主要入口 * Java中对于基本数据类型使用的是快速排序 sort(type[] array) * @param array */ public static void quick(int[] array){ int p = 0; int r = array.length-1; qsort(array,p,r); } /** * 快速排序主函数 * @param array * @param p * @param r */ private static void qsort(int array[], int p, int r) { if (p < r) { int q = partition(array, p, r); qsort(array, p, q - 1); qsort(array, q + 1, r); } } /** * 进行一次排序,并得到分支点 * 过程如下: * 对p到r位置上的元素进行一一排序(标记位置由i来负责) * index负责交换位置的确定。没交换一次位置,index++ * for循环结束的时候,比key小的元素会都在index的左边 * 这样再将index和r位置上的两个元素交换 * @param array * @param left * @param right * @return */ private static int partition(int array[], int left, int right) { int key = array[right]; int index = left; for (int i = left; i < right; i++) { if (array[i] <= key) {//不关是否交换,index都要增加 if(i != index){//避免交换相同的元素,不过index还是要增加的。 swap(array, index, i); } index++; } } swap(array, index, right); return index; } private static void swap(int a[], int i, int j) { int tmp = a[i]; a[i] = a[j]; a[j] = tmp; } /** * 桶式排序 * * @param array */ public static void bucket(int[] array) { } /** * 基数排序 * @param array */ public static void base(int[] array){ } public static void main(String[] args) { int[] array = new int[] { 3, 4, 5, 2, 6, 7, 1, 9, 8, 10 }; bubble(array); System.out.println("bubble:\t\t" + Arrays.toString(array)); array = new int[] { 3, 4, 5, 2, 6, 7, 1, 9, 8, 10 }; selection(array); System.out.println("selection:\t" + Arrays.toString(array)); array = new int[] { 3, 4, 5, 2, 6, 7, 1, 9, 8, 10 }; insertion(array); System.out.println("insertion:\t" + Arrays.toString(array)); array = new int[] { 3, 4, 5, 2, 6, 7, 1, 9, 8, 10 }; shell(array); System.out.println("shell:\t\t" + Arrays.toString(array)); array = new int[] { 3, 4, 5, 2, 6, 7, 1, 9, 8, 10 }; merge(array); System.out.println("merge:\t\t" + Arrays.toString(array)); array = new int[] { 3, 5, 2, 6, 7, 1, 9, 8, 10, 4}; quick(array); System.out.println("quick:\t\t" + Arrays.toString(array)); } }
/** * @author Yuanbo Han */ public class HeapSort { private double[] elements = new double[10]; private int size = 0; private HeapSort(){ this.elements = new double[10]; this.size = 0; } public void add(double e){ if(size + 1 > elements.length){ int newCapacity = elements.length * 3 / 2 + 1; double[] newElements = new double[newCapacity]; System.arraycopy(elements, 0, newElements, 0, size); newElements[size++] = e; elements = newElements; }else{ elements[size++] = e; } } public void heapsort(){ for(int i=0;i<size;i++){ int length = size - i; this.heapsort(length); } } /** * 对前length个数据进行排序,得到最大的数据为index = 0,然后跟index = length-1的数据进行交换 * @param length */ private void heapsort(int length){ int index = length / 2 - 1; for(int i=index;i>=0;i--){ int head = i; for(;;){//进行交换之后,子树可能不是最大堆,所以要for循环进行重构最大堆 int max = head; int left = 2 * head + 1; int right = 2 * head + 2; if(left < length && elements[max] < elements[left]){ max = left; } if(right < length && elements[max] < elements[right]){ max = right; } if(max != head){ double tmp = elements[max]; elements[max] = elements[head]; elements[head] = tmp; head = left; }else{ break; } } } double tmp = elements[0]; elements[0] = elements[length-1]; elements[length-1] = tmp; } @Override public String toString() { StringBuilder sb = new StringBuilder(); sb.append("["); for(int i=0;i<size;i++){ sb.append(elements[i] + ", "); } if(size > 0){ sb = new StringBuilder(sb.substring(0, sb.length() - 2)); } sb.append("]"); return sb.toString(); } public static void main(String[] args) { HeapSort hs = new HeapSort(); hs.add(15); hs.add(60); hs.add(72); hs.add(70); hs.add(56); hs.add(32); hs.add(62); hs.add(92); hs.add(45); hs.add(30); hs.add(65); hs.heapsort(); System.out.println(hs); } }
向一个已经排好序的数组中插入新的数据,使用二分查找来进行位置确定,时间复杂度为(log N)。
/** * @author Yuanbo Han */ public class Sort { private double[] elements = new double[10]; private int size = 0; private Sort(){ this.elements = new double[10]; this.size = 0; } @Override public String toString() { StringBuilder sb = new StringBuilder(); sb.append("["); for(int i=0;i<size;i++){ sb.append(elements[i] + ", "); } if(size > 0){ sb = new StringBuilder(sb.substring(0, sb.length() - 2)); } sb.append("]"); return sb.toString(); } /** * 升序排列 * @param a * @return */ public void insert(double a){ int index = this.getInsertIndex(a, 0, size-1); if(size + 1 > elements.length){ int newCapacity = elements.length * 3 / 2 + 1; double[] newElements = new double[newCapacity]; System.arraycopy(elements, 0, newElements, 0, index); newElements[index] = a; System.arraycopy(elements, index, newElements, index+1, size - index); elements = newElements; }else{ System.arraycopy(elements, index, elements, index+1, size - index); elements[index] = a; } size++; } /** * 升序排列 * @param a * @param leftIndex * @param rightIndex * @return */ private int getInsertIndex(double a, int leftIndex, int rightIndex){ if(rightIndex < 0){//the first time return leftIndex; } if(leftIndex == rightIndex){ if(a > elements[rightIndex]){ return rightIndex + 1; } return leftIndex; } int midIndex = (leftIndex + rightIndex) / 2; if(a > elements[midIndex]){ return this.getInsertIndex(a, midIndex+1, rightIndex); }else if(a < elements[midIndex]){ return this.getInsertIndex(a, leftIndex, midIndex-1); }else{ return midIndex; } } public void testInsert(){ this.insert(15);System.out.println(this); this.insert(60);System.out.println(this); this.insert(72);System.out.println(this); this.insert(70);System.out.println(this); this.insert(56);System.out.println(this); this.insert(32);System.out.println(this); this.insert(62);System.out.println(this); this.insert(92);System.out.println(this); this.insert(45);System.out.println(this); this.insert(30);System.out.println(this); this.insert(65);System.out.println(this); } public static void main(String[] args) { Sort hs = new Sort (); hs.testInsert(); } } //输出结果 /* [15.0] [15.0, 60.0] [15.0, 60.0, 72.0] [15.0, 60.0, 70.0, 72.0] [15.0, 56.0, 60.0, 70.0, 72.0] [15.0, 32.0, 56.0, 60.0, 70.0, 72.0] [15.0, 32.0, 56.0, 60.0, 62.0, 70.0, 72.0] [15.0, 32.0, 56.0, 60.0, 62.0, 70.0, 72.0, 92.0] [15.0, 32.0, 45.0, 56.0, 60.0, 62.0, 70.0, 72.0, 92.0] [15.0, 30.0, 32.0, 45.0, 56.0, 60.0, 62.0, 70.0, 72.0, 92.0] [15.0, 30.0, 32.0, 45.0, 56.0, 60.0, 62.0, 65.0, 70.0, 72.0, 92.0] */
发表评论
-
applet 您的安全设置已阻止本地应用程序运行
2013-08-23 19:13 1721控制面板中把JAVA的安全设置调至最低,然后重启浏览器。 -
Failed to create the Java Virtual Machine
2010-10-31 11:14 1289今天启动Eclipse,告诉我“Failed to creat ... -
udp sender 精确到毫秒
2010-10-22 20:14 12241。源文件。 package sender; impor ... -
Java的System.getProperty()方法可以获取的值
2010-09-29 16:14 890ava的System.getProperty()方法可以获取的 ... -
Java 执行系统文件
2010-09-29 14:59 986以下两个事例是执行Windows下的命令或者可执行文件。 ... -
Java access control
2010-08-19 18:31 856Java中有4个访问级别(不同于C或者C++的3个)。但规则同 ... -
Java中需要注意的函数
2010-08-17 22:23 1008(持续更新中。。。) ... -
Java面试题
2010-08-08 18:39 810最近在网上看到很多Java ... -
Java 入门
2010-08-06 16:59 1786(转载 IBM DeveloperWorks) ... -
Java中的深拷贝与浅拷贝
2010-08-06 06:32 925在Java中,一个重要的,而且是每个类都有的方法,clone( ... -
Java 容器类
2010-08-06 05:05 825Java功能丰富的集 ... -
java 解惑 1
2010-08-05 22:06 986_1.java package itepub.net._201 ... -
java5 新特性
2010-08-05 19:31 37931.静态导入方法 package c ... -
Comparator and Comparable in Java
2010-08-05 19:10 9161. java.lang.Comparable java ... -
Java中 synchronize、wait和notify3
2010-08-05 19:07 838package com.java.lang.thread. ... -
Java中 synchronize、wait和notify2
2010-08-05 19:06 1505有一个生产者消费者实例,修改了一下,觉得还行,javaeye上 ... -
Java中 synchronize、wait和notify
2010-08-05 18:53 2293认识Java一段时间了了,到目前为止还没有好好认识一下其中的s ... -
Java中的String类
2010-08-05 18:42 10031. 正像很多人所说的那样,equals 和 == 是完全两个 ...
相关推荐
提供了Java实现几种常见排序方法和原理介绍
堆排序7.java 使用java实现的堆排序堆排序7.java 使用java实现的堆排序堆排序7.java 使用java实现的堆排序堆排序7.java 使用java实现的堆排序堆排序7.java 使用java实现的堆排序堆排序7.java 使用java实现的堆排序堆...
Java实现六种常用排序 并用多线程进行速度比较(其实意义不大) 含有代码
java 实现归并排序,有代码实现,复杂度分析,基本步骤,适合初学者吧,
快速排序算法的Java实现。下载后把Package信息稍作修改即可运行。
主要介绍了Java实现拖拽列表项的排序功能,非常不错,具有参考借鉴价值,需要的朋友可以参考下
Java实现的常见排序算法.pdfJava实现的常见排序算法.pdfJava实现的常见排序算法.pdfJava实现的常见排序算法.pdfJava实现的常见排序算法.pdfJava实现的常见排序算法.pdf
Java ip 地址排序Java ip 地址排序Java ip 地址排序Java ip 地址排序
堆排序12.java 使用java代码实现堆排序12.java 使用java代码实现堆排序12.java 使用java代码实现堆排序12.java 使用java代码实现堆排序12.java 使用java代码实现堆排序12.java 使用java代码实现堆排序12.java 使用...
堆排序10.java 使用java来实现堆排序10.java 使用java来实现堆排序10.java 使用java来实现堆排序10.java 使用java来实现堆排序10.java 使用java来实现堆排序10.java 使用java来实现堆排序10.java 使用java来实现堆...
java实现的冒泡排序 很简单一看就懂
提供Java版七种排序算法代码大全,包括冒泡排序、选择排序、插入排序、希尔排序、快速排序、归并排序、堆排序
实现合并排序,插入排序,希尔排序,快速排序,冒泡排序,桶排序算法的java实现。
java实现的插入排序 都是静态的例子 很简单
Java实现堆排序不是C,Java实现堆排序不是C,Java实现堆排序不是C,Java实现堆排序不是C
冒泡排序,插入排序,希尔排序,选择排序,堆排序,归并排序,快速排序,桶排序,计数排序,基数排序,TimeSort排序
Java实现计数排序不是C,Java实现计数排序不是C,Java实现计数排序不是C
用java实现了10种基础排序,其内容包括: 1.冒泡排序 2.选择排序 3.插入排序 4.快速排序 5.希尔排序 6.归并排序 7.堆排序 8.桶排序 9.基数排序 10.计数排序 如有疑问请私信我
8中业务中常用的排序方法的java类实现,自己搞得,少点分分享给大家