- 浏览: 778806 次
- 性别:
- 来自: 深圳
文章分类
最新评论
-
萨琳娜啊:
Java读源码之Netty深入剖析网盘地址:https://p ...
Netty源码学习-FileRegion -
飞天奔月:
写得有趣 ^_^
那一年你定义了一个接口 -
GoldRoger:
第二个方法很好
java-判断一个自然数是否是某个数的平方。当然不能使用开方运算 -
bylijinnan:
<script>alert("close ...
自己动手实现Java Validation -
paul920531:
39行有个bug:"int j=new Random ...
java-蓄水池抽样-要求从N个元素中随机的抽取k个元素,其中N无法确定
public static void bubbleSort(int[] c){ for(int i=0,len=c.length;i<len;i++){ for(int j=0;j<len-i-1;j++){ if(c[j]>c[j+1]){ Helper.swap(c, j+1, j); } } } } public static void selectionSort(int[] c){ for(int i=0,len=c.length;i<len;i++){ int k=i; for(int j=i+1;j<len;j++){ if(c[j]<c[k])k=j; } if(k!=i){ Helper.swap(c, i, k); } } } public static void insertionSort(int[] a){ for(int i=1,len=a.length;i<len;i++){ int j=i; while(j>0){ if(a[j]<a[j-1]){ Helper.swap(a,j,j-1); } j--; } } } public static void quickSort2(int[] c,int begin,int end){ //update 2012/7/1 if(c==null||c.length<2){ return; } if(begin>end)return; int len = c.length; if(begin<end&&(0<=begin&&begin<len)&&(0<=end&&end<len)){ int point=c[begin]; int i=begin,j=end; int index=i; while(i<j){ while(c[j]>=point&&i<j)j--; if(i<j){ c[index]=c[j]; index=j; } while(c[i]<=point&&i<j)i++; if(i<j){ c[index]=c[i]; index=i; } } c[index]=point; quickSort2(c,begin,i-1); quickSort2(c,i+1,end); } } public static void quickSort(int[] c,int begin,int end){ if(begin>end)return; int low=begin; int high=end; boolean flag=true; while(low!=high){ if(c[low]>c[high]){ Helper.swap(c, low, high); flag=!flag; } if(flag){ high--; }else{ low++; } } quickSort(c,begin,low-1); quickSort(c,high+1,end); } /** * 用最大堆实现“就地”升序排序 * 思路: * 1.“自下而上”,将整个数组初始化建成一个最大堆 * 从最右下方的子堆——也就是以最后一个非叶子结点为根结点(lastRootindex)的子堆——开始, * 调整各个子堆使之为最大堆,最后使得整个数组成为一个最大堆 * 注意到从 0, 1, 2, ...lastRootIndex 的结点都是非叶子结点,都作为子堆需要调整 * 2.将当前堆顶元素(最大元素)与堆的最后一个元素交换,这样,当前最大值就排到末尾了 * 3.将堆的大小减1(排除最后一个元素),重新调整使得堆仍为最大堆,直到排序完毕 * 注意这时候的调整是“自上而下”,选举出当前的最大值放至堆顶 */ public static void heapsort(int[] array) { int lastIndex = array.length - 1; int lastRootIndex = (lastIndex - 1) / 2; for (int root = lastRootIndex; root >= 0; root--) { reheap(array, root, lastIndex); } for (int last = lastIndex; last >= 0; last--) { swap(array, 0, last); reheap(array, 0, last - 1); //堆大小减1 } System.out.println(Arrays.toString(array)); } /** * 调整使之仍为最大堆 * @param heap heap是这样一个“半堆”:执行调整操作前是一个最大堆。将最大堆的堆顶元素移除,并替换为最大堆的最后一个元素,成为“半堆” * @param rootIndex “半堆”的根 * @param lastIndex “半堆”的最后一个元素 */ public static void reheap2(int[] heap, int rootIndex, int lastIndex) { int orphan = heap[rootIndex]; int leftIndex = rootIndex * 2 + 1; boolean done = false; while (!done && leftIndex <= lastIndex) { int largeIndex = leftIndex; int rightIndex = leftIndex + 1; if (rightIndex <= lastIndex && heap[rightIndex] > heap[leftIndex]) { largeIndex = rightIndex; } if (heap[largeIndex] > orphan) { heap[rootIndex] = heap[largeIndex]; rootIndex = largeIndex; leftIndex = rootIndex * 2 + 1; } else { done = true; } } heap[rootIndex] = orphan; } public static void mergeSort(int[] c,int low,int high,int[] tmp){ if(low>=high)return; int mid=(high&low)+((high^low)>>1); mergeSort(c,low,mid,tmp); mergeSort(c,mid+1,high,tmp); merge(c,low,mid,high,tmp); } public static void merge(int[] c,int low,int mid,int high,int[] tmp){ int begin01=low; int end01=mid; int begin02=mid+1; int end02=high; int k=0; while(begin01<=end01&&begin02<=end02){ if(c[begin01]<c[begin02]){ tmp[k]=c[begin01]; k++; begin01++; }else{ tmp[k]=c[begin02]; k++; begin02++; } } while(begin01<=end01){ tmp[k++]=c[begin01++]; } while(begin02<=end02){ tmp[k++]=c[begin02++]; } System.arraycopy(tmp, 0, c,low, k); }
评论
3 楼
bylijinnan
2012-06-29
neyshule 写道
quicksort2是不是有问题,c[i]<=point?
嗯 我当时没考虑有相等的情况
2 楼
neyshule
2012-06-27
quicksort2是不是有问题,c[i]<=point?
1 楼
pywepe
2012-02-05
备忘,,希望没有错误
发表评论
-
二维数组(矩阵)对角线输出
2014-04-28 17:55 4605/** 二维数组 对角线输出 两个方向 例如对于数 ... -
线段树-poj1177-N个矩形求边长(离散化+扫描线)
2013-01-05 20:34 2910package com.ljn.base; import ... -
线段树-入门
2013-01-05 20:32 2111/** * 线段树入门 * 问题:已知线段 ... -
bitmap求哈密顿距离-给定N(1<=N<=100000)个五维的点A(x1,x2,x3,x4,x5),求两个点X(x1,x2,x3,x4,x5)和Y(
2012-12-27 21:12 2892import java.util.Random; / ... -
百度笔试题:一个已经排序好的很大的数组,现在给它划分成m段,每段长度不定,段长最长为k,然后段内打乱顺序,请设计一个算法对其进行重新排序
2012-12-21 18:17 4053import java.util.Arrays; ... -
有一个数组,每次从中间随机取一个,然后放回去,当所有的元素都被取过,返回总共的取的次数。写一个函数实现。复杂度是什么。
2012-12-07 14:32 3547import java.util.Random; i ... -
三色旗算法
2012-11-29 12:19 3760import java.util.Arrays; ... -
单调队列-用一个长度为k的窗在整数数列上移动,求窗里面所包含的数的最大值
2012-11-11 22:32 2304import java.util.LinkedList; ... -
据说是2012年10月人人网校招的一道笔试题-给出一个重物重量为X,另外提供的小砝码重量分别为1,3,9。。。3^N。 将重物放到天平左侧,问在两边如何添加砝码
2012-10-28 23:41 1921public class ScalesBalance { ... -
编程之美-分层遍历二叉树
2012-08-12 10:02 5863import java.util.ArrayList; ... -
编程之美-最短摘要的生成
2012-08-10 18:37 2433import java.util.HashMap; ... -
编程之美-计算字符串的相似度
2012-08-09 19:25 2853public class StringDistance ... -
编程之美-电话号码对应英语单词
2012-08-09 19:24 4169import java.util.Arrays; ... -
编程之美-数组中最长递增子序列
2012-08-09 19:22 1961import java.util.Arrays; imp ... -
编程之美-数组中最长递增子序列
2012-08-09 19:22 6import java.util.Arrays; imp ... -
xxx
2012-08-09 00:35 0package beautyOfCoding; public ... -
编程之美-子数组的最大和(二维)
2012-08-05 23:51 2209package beautyOfCoding; impo ... -
编程之美-子数组的最大乘积
2012-08-06 00:00 2237public class MaxProduct { ... -
编程之美-找符合条件的整数 用字符串来表示大整数避免溢出
2012-07-26 19:26 1791import java.util.LinkedList ... -
sudoku
2012-07-25 20:36 0package a; public class Sudoku ...
相关推荐
下面列出了一些常见的排序算法。这里面插入排序和冒泡排序又被称作简单排序,他们对空间的要求不高,但是时间效率却不稳定;而后面三种排序相对于简单排序对空间的要求稍高一点,但时间效率却能稳定在很高的水平。...
几种内部排序算法总结!(冒泡排序、快速排序、直接插入排序、拆半插入排序、简单选择排序)
最经典的8大排序算法总结,插入排、冒泡排序、快速排序、简单选择排序、归并排序、二叉树排序、基数排序等。
个人原创总结的常用排序算法C语言示例代码解说PDF,可以动态输出排序过程,以便理解排序算法的主旨思想。包含有直接插入排序,折半插入排序,2路直接插入排序,起泡排序,简单选择排序,快速排序,堆排序,(希尔排序,归并...
常用排序算法总结 各种内排序方法的选择 对元素个数较多的排序,可以选快速排序、堆排序、归并排序,元素个数较少时,可以选简单的排序方法。
该 ppt 为课程讲义,讲解冒泡排序算法原理,及用一个简单实例进行具体分析,还有冒泡排序算法原理的总结等。
几乎把网上的排序算法小结找遍了,简单地小结一下算法的思路(不含代码,只是用易懂的话说清楚算法是怎么做的),算法时间复杂度和空间复杂的求法(用理解的方式而不是分析代码),各种排序算法的优缺点,稳定与否...
之前一段时间,由于需要,我复习了一下排序算法,并用Python实现了各种排序算法,放在这里作为参考。 最简单的排序有三种:插入排序,选择排序和冒泡排序。这三种排序比较简单,它们的平均时间复杂度均为O(n^2),在...
排序算法总结常见排序算法如下:直接插入排序希尔排序简单选择排序堆排序冒泡排序快速排序归并排序技术排序它们都属于内部排序,也就是只考虑数据量较小仅需要使用内部的排
数据结构中九大排序算法:直接插入排序,折半插入排序,希尔排序,冒泡排序,快速排序,简单选择排序,堆排序,归并排序,基数排序,就时间复杂度,空间复杂度,稳定性,基本原理的简要总结与比较
对开发时排序算法的总结,有简单排序,冒泡排序,二分法排序,且有对各种排序的优劣势的分析,谨供大家参考
对冒泡排序,直接插入排序,简单选择排序,快速排序,希尔排序,堆排序这六种常用的内排序方法的掌握,通过对各种排序算法的分析,对其关键字的比较次数和移动次数进行分析,运用数据结构所学的知识将其用程序实现。
八大排序方法详细图形解释,和算法复杂度分析,及最后总结。 1.直接插入排序 2.希尔排序 3.简单选择排序 4.堆排序 5.冒泡排序 6.快速排序 7.归并排序 8.基数排序
这里就把各种内部排序算法总结归纳了一下,包括插入排序(直接插入排序,折半插入排序,希尔排序)、交换排序(冒泡排序,快速排序)、选择排序(简单选择排序,堆排序)、2-路归并排序。(另:至于堆排序算法,前面...
以下是在编程面试中排名前10的算法相关的概念,通过一些简单的例子来阐述这些概念。由于完全掌握这些概念需要更多的努力,因此这份列表只是作为一个介绍。本文将从Java的角度看问题,包含下面的这些概念:
数据结构实验报告学习、实现、对比各种排序算法,掌握各种排序算法的优劣,以及各种算法使用的情况。 实验内容: 使用链表实现下面各种排序算法,并进行比较。 排序算法: 1、插入排序 2、冒泡排序 3、快速...
它由Sun Microsystems(现在是Oracle Corporation)的James Gosling等人在1995年推出,被设计为一种简单、健壮、可移植、多线程、动态的语言。Java的主要特点和优势包括以下几个方面: 跨平台性(Write Once, Run ...
如何准确、快速地帮助人们从海量网络数据中获取所需信息,是目前搜索引擎首要解决的问题,为此,各种搜索排序算法应运而生。但是目前,网页信息的表达形式都十分简单,用户描述查询的形式更是十分简单,这就造成了在...