华为面试时,最爱考这个!!!
解决方案 »
- 一道简单的java,看看你能答对吗
- 求一个JAVA+ACCESS做的图书馆管理系统~~
- java关闭窗口对话框
- Thinking in Java
- 如何构建一个可用于密码输入的文本框
- weblogic和jbulider整和后出现的问题!问题应该比较容易,我给50分!
- 关于sun的java大家看怎么样?
- 小弟初用java碰到一个想不通的问题
- 为什么用JDBC、ODBC桥连接数据库时,总是说“No suitable driver"呢???
- 打印嵌有applet的网页,Canon的BJC-4200没有问题,而用HP的黑白激光打印机打印,applet部分是一片黑??各位热心人请帮帮我,谢谢
- java调用存储过程返回值始终为0?查询分析器中运行没错,在java中调用就出错了,到底哪出错了?
- 帮我看看这个配置文件有错吗?谢谢,
//Java排序算法 package com.cucu.test;public class Sort { public void swap(int a[], int i, int j) { int tmp = a[i]; a[i] = a[j]; a[j] = tmp; } public int partition(int a[], int low, int high) { int pivot, p_pos, i; p_pos = low; pivot = a[p_pos]; for (i = low + 1; i <= high; i++) { if (a[i] > pivot) { p_pos++; swap(a, p_pos, i); } } swap(a, low, p_pos); return p_pos; } public void quicksort(int a[], int low, int high) { int pivot; if (low < high) { pivot = partition(a, low, high); quicksort(a, low, pivot - 1); quicksort(a, pivot + 1, high); } } public static void main(String args[]) { int vec[] = new int[] { 37, 47, 23, -5, 19, 56 }; int temp; //选择排序法(Selection Sort) long begin = System.currentTimeMillis(); for (int k = 0; k < 1000000; k++) { for (int i = 0; i < vec.length; i++) { for (int j = i; j < vec.length; j++) { if (vec[j] > vec[i]) { temp = vec[i]; vec[i] = vec[j]; vec[j] = temp; } } } } long end = System.currentTimeMillis(); System.out.println("选择法用时为:" + (end - begin)); //打印排序好的结果 for (int i = 0; i < vec.length; i++) { System.out.println(vec[i]); } // 冒泡排序法(Bubble Sort) begin = System.currentTimeMillis(); for (int k = 0; k < 1000000; k++) { for (int i = 0; i < vec.length; i++) { for (int j = i; j < vec.length - 1; j++) { if (vec[j + 1] > vec[j]) { temp = vec[j + 1]; vec[j + 1] = vec[j]; vec[j] = temp; } } } } end = System.currentTimeMillis(); System.out.println("冒泡法用时为:" + (end - begin)); //打印排序好的结果 for (int i = 0; i < vec.length; i++) { System.out.println(vec[i]); } //插入排序法(Insertion Sort) begin = System.currentTimeMillis(); for (int k = 0; k < 1000000; k++) { for (int i = 1; i < vec.length; i++) { int j = i; while (vec[j - 1] < vec[i]) { vec[j] = vec[j - 1]; j--; if (j <= 0) { break; } } vec[j] = vec[i]; } } end = System.currentTimeMillis(); System.out.println("插入法用时为:" + (end - begin)); //打印排序好的结果 for (int i = 0; i < vec.length; i++) { System.out.println(vec[i]); } //快速排序法(Quick Sort) Sort s = new Sort(); begin = System.currentTimeMillis(); for (int k = 0; k < 1000000; k++) { s.quicksort(vec, 0, 5); } end = System.currentTimeMillis(); System.out.println("快速法用时为:" + (end - begin)); //打印排序好的结果 for (int i = 0; i < vec.length; i++) { System.out.println(vec[i]); } }} 以下是运行结果:选择法用时为:2345647372319-5冒泡法用时为:1725647372319-5插入法用时为:785647372319-5快速法用时为:2975647372319-5
网上很多相关的资料.
public class JoSort {
public void sort(int[] n){
for (int i = 0; i < n.length; i += 2){
for (int j = 0; j < n.length - 1; j += 2){
if (n[j] > n[j + 1]){
n[j] = n[j + 1] + n[j];
n[j + 1] = n[j] - n[j + 1];
n[j] = n[j] - n[j + 1];
}
}
for (int j = 1; j < n.length - 1; j += 2){
if (n[j] > n[j + 1]){
n[j] = n[j + 1] + n[j];
n[j + 1] = n[j] - n[j + 1];
n[j] = n[j] - n[j + 1];
}
}
}
}
public static void main(String[] args){
int[] n = new int[10000];
Random r = new Random();
for (int i = 0; i < n.length; i++){
n[i] = r.nextInt(10000);
}
JoSort js = new JoSort();
long s = System.currentTimeMillis();
js.sort(n);
long e = System.currentTimeMillis();
for (int i = 0; i < n.length - 1; i++){
System.out.print(n[i]+",");
}
System.out.println(n[n.length-1]);
System.out.println("奇偶排序耗时:"+(e - s) / 1000.0 + "秒");
}
} p.s:当数组长度为奇数时,用奇偶排序算法对其进行排序最后会多进行n/2-1次的比较。 在AMD 速龙 3800+,1G内存,JDK6.0的运行环境下耗时0.39秒左右。与冒泡排序法的效率差不多,看不出有什么好处。 但书上说:“奇偶排序实际上在多处理器环境中很有用,处理器可以分别同时处理每一个奇数对,然后又同时处理偶数对。因为奇数对是彼此独立的,每一对都可以用不同的处理器比较和交换。这样可以非常快速的排序。”
插入排序在最不理想的情况下的效率和选择排序一样,当对一个需要将它排到最左端的元素进行排序的时候,将会移动很多个元素,而希尔排序算法通过加大插入排序中元素之间的间隔,并在这些有间隔的元素中进行插入排序,从而使数据项能够大跨度地移动。当这些数据项排过一趟序后,希尔排序算法减小数据项的间隔再进行排序,这时,因为经过之前的排序,数组已经是“基本有序”的了,减少间隔后再排序,数组越来越有序,最后所有元素的位置与它最终位置的距离非常小(也就是说这时再用插入排序法对其排序需要移动的元素是很少的),这时间隔已经减小到了1,也就是原始的插入排序法了。希尔排序算法大大减小了插入排序的时间复杂度。 下面是我自己写的一个用希尔算法实现的排序代码: import java.util.Random;
class Shell{
public void sort(int[] source){
int h = 1;
int temp;
while (h*3+1<source.length+1){
h = h*3+1;
}
while (h != 0){
for(int i=0; i<h; i++){
for (int j=i; j<source.length-h; j+=h){
temp = source[j+h];
int k;
for (k=j; k>i-h; k-=h){
if (temp<source[k]){
source[k+h] = source[k];
} else {
break;
}
}
source[k+h] = temp;
}
}
h = (h-1)/3;
}
}
public static void main(String[] args){
Shell shell = new Shell();
Random random = new Random();
int[] test = new int[10000];
for (int i=0; i<test.length; i++){
test[i] = random.nextInt(10000);
}
for(int i : test){
System.out.print(i+",");
}
System.out.println();
long s = System.currentTimeMillis();
shell.sort(test);
long e = System.currentTimeMillis();
for(int i : test){
System.out.print(i+",");
}
System.out.println("\n"+(e-s)/1000.0+"秒");
}
} 执行结果是0.0秒。
我把数组扩大10倍,结果是0.031秒,比插入排序快得太多了。
对1000000长度的数组排序,平均时间是0.595秒。
package sort;public class SortDemo {
public static void main(String args[]){
int[] bigArr = new int[100000];
for(int i=0;i<100000;i++)
bigArr[i] = (int)(Math.random()*400000);
Sort.insertSort(bigArr, 100000);
//Sort.quickSort(0,99999,bigArr);
//display result, optional
//for(int i=0;i<bigArr.length;i++)
// System.out.print(bigArr[i]+",");
System.out.println("Done");
}
}class Sort{
public static void swap(int x,int y,int[] target){
int temp = target[x];
target[x] = target[y];
target[y] = temp;
}
public static void insertSort(int[] target,int length){
for(int i=1;i<length;i++)
for(int j=i;j>0&&target[j-1]>target[j];j--)
swap(j-1,j,target);
}
public static void quickSort(int low, int high, int[] target){
if(high<=low)
return;
int temp = target[low];
int i = low, j=high+1;
while(true){
do{
i++;
}while(i<=high&&target[i]<temp);
do{
j--;
}while(target[j]>temp);
if(i>j)
break;
swap(i,j,target);
}
swap(low,j,target);
quickSort(low,j-1,target);
quickSort(j+1,high,target);
}
}
这是笔者曾经写过的一个老例子了,弄了10万个随机数来测试,插入排序比快速排序确实要慢很多。lz可以自己跑一跑这个例子,其实排序的算法有很多,基本都是在不断的优化比较和移动数组元素的次数来提高效率,把握这个才是掌握排序算法的最核心的本质。至于名字是快速排序,希尔排序,插入排序,冒泡排序,归并排序,选择排序,堆排序,都是各自有自己比较元素和移动元素的此略不同而适应不同的场景。好好学习数据结构就能搞明白了,排序是数据结构中数组这块必须用心体会的……
这个方法的一个变形是用2.2而非2来整除每一个间隔。对于n=100的数组来说,会产生序列45,20,9,4,1。这比用2整除显著改善了效果,因为这样避免了某些导致时间复杂度为O(N^2)的最坏情况的发生。不论N为何值,都需要一些额外的代码来保证序列的最后取值为1。
间隔序列中的数字互质通常被认为很重要:也就是说,除了1之外它们没有公约数。这个约束条件使每一趟排序更有可能保持前一趟排序已经排好的效果。希尔最初以N/2为间隔的低效性就是归咎于它没有遵守这个准则。
或许还可以设计出像如上讲述的间隔序列一样好的(甚至更好的)间隔序列。但是不管这个间隔序列是什么,都应该能够快速地计算,而不会降低算法的执行速度。
private int[] source;
public QuickSort(int[] source){
this.source = source;
}
public void sort(){
recQuickSort(0,source.length-1);
}
private void recQuickSort(int left, int right){
if (left >= right){
return;
} else {
int pivot = source[right];//选择子数组的最右端为枢纽
int partition = partition(left, right, pivot);
recQuickSort(left, partition-1);
recQuickSort(partition+1, right);
}
}
private int partition(int left, int right, int pivot){//划分算法
int leftIdx = left - 1;
int rightIdx = right ;
while (true){
while (source[++leftIdx] < pivot);
while (rightIdx > 0 && source[--rightIdx] >= pivot);
if(leftIdx < rightIdx){
swap(leftIdx, rightIdx);
} else {
break;
}
}
swap(leftIdx, right);
return leftIdx;
}
private void swap(int idx1, int idx2){
int temp = source[idx1];
source[idx1] = source[idx2];
source[idx2] = temp;
}
public static void main(String[] args){
int[] n = new int[6046]; //超过6046溢出
for (int i=0; i<6046; i++){
n[i] = 6046-i;
}
QuickSort qs = new QuickSort(n);
qs.sort();
for (int i: n){
System.out.print(i+",");
}
}
} 快速排序2:(用三数据项取中法选择枢纽,用手动排序为长度为3或3以下的子数组进行排序。)import java.util.Random;
class QuickSort2{
private int[] source;
public QuickSort2(int[] source){
this.source = source;
}
public void sort(){
recQuickSort(0,source.length-1);
}
private void recQuickSort(int left, int right){
int size = right - left + 1;
if (size <= 3){
manualSort(left, right);
} else {
int median = medianOf3(left, right);
int partition = partition(left, right, median);
recQuickSort(left, partition - 1);
recQuickSort(partition + 1, right);
}
}
private int medianOf3(int left, int right){//用三数据项取中法选择枢纽
int center = (left + right) / 2;
if (source[left] > source[center])
swap(left, center);
if (source[left] > source[right])
swap(left, right);
if (source[center] > source[right])
swap(center, right);
swap(center, right-1);
return source[right-1];
}
private int partition(int left, int right, int pivot){
int leftPtr = left;
int rightPtr = right - 1;
while (true){
while (source[++leftPtr] < pivot);
while (source[--rightPtr] > pivot);//这里不能加等号,否则数组索引有可能越界。
if (leftPtr > rightPtr){
break;
} else {
swap(leftPtr, rightPtr);
}
}
swap(leftPtr, right - 1);
return leftPtr;
}
private void swap(int idx1, int idx2){
int temp = source[idx1];
source[idx1] = source[idx2];
source[idx2] = temp;
}
private void manualSort(int left, int right){//用手动排序为长度为3或3以下的子数组进行排序
int size = right - left + 1;
switch (size){
case 2:
if (source[left] > source[right])
swap (left, right);
break;
case 3:
if (source[left] > source[left + 1])
swap(left, left + 1);
if (source[left] > source[right])
swap(left, right);
if (source[left + 1] > source[right])
swap(left + 1, right);
break;
}
}
public static void main(String args[]){
int[] source = new int[10000];
QuickSort2 qs2;
Random random = new Random();
for (int i=0; i<source.length; i++){
source[i] = random.nextInt(source.length);
}
qs2 = new QuickSort2(source);
long s = System.currentTimeMillis();
qs2.sort();
long e = System.currentTimeMillis();
for (int i: source){
System.out.print(i+",");
}
System.out.println("耗时:"+(e-s)/1000.0+"秒");
}
}
10次对长度为10^6的数组进行排序:
耗时:0.188秒
耗时:0.172秒
耗时:0.172秒
耗时:0.187秒
耗时:0.172秒
耗时:0.172秒
耗时:0.188秒
耗时:0.172秒
耗时:0.188秒
耗时:0.171秒
class QuickSort3{
private int[] source;
public QuickSort3(int[] source){
this.source = source;
}
public void sort(){
recQuickSort(0,source.length-1);
}
private void recQuickSort(int left, int right){
int size = right - left + 1;
if (size < 10){//当子数组长度为9时使用插入排序
insertionSort(left, right);
} else {
int median = medianOf3(left, right);
int partition = partition(left, right, median);
recQuickSort(left, partition - 1);
recQuickSort(partition + 1, right);
}
}
private int medianOf3(int left, int right){
int center = (left + right) / 2;
if (source[left] > source[center])
swap(left, center);
if (source[left] > source[right])
swap(left, right);
if (source[center] > source[right])
swap(center, right);
swap(center, right-1);
return source[right-1];
}
private int partition(int left, int right, int pivot){
int leftPtr = left;
int rightPtr = right - 1;
while (true){
while (source[++leftPtr] < pivot);
while (source[--rightPtr] > pivot);
if (leftPtr > rightPtr){
break;
} else {
swap(leftPtr, rightPtr);
}
}
swap(leftPtr, right - 1);
return leftPtr;
}
private void swap(int idx1, int idx2){
int temp = source[idx1];
source[idx1] = source[idx2];
source[idx2] = temp;
}
private void insertionSort(int left, int right){//插入排序法
int temp;
for (int i=left+1; i<right+1; i++){
int j;
temp = source[i];
for (j=i-1; j>-1; j--){
if (temp < source[j])
source[j] = source[j+1];
else
break;
}
}
}
public static void main(String args[]){
int[] source = new int[10000];
QuickSort3 qs3;
Random random = new Random();
for (int i=0; i<source.length; i++){
source[i] = random.nextInt(10000);
}
qs3 = new QuickSort3(source);
long s = System.currentTimeMillis();
qs3.sort();
long e = System.currentTimeMillis();
for (int i: source){
System.out.print(i+",");
}
System.out.println("耗时:"+(e-s)/1000.0+"秒");
}
}
10次对长度为10^6的数组进行排序:
耗时:0.157秒
耗时:0.172秒
耗时:0.156秒
耗时:0.156秒
耗时:0.157秒
耗时:0.172秒
耗时:0.156秒
耗时:0.172秒
耗时:0.172秒
耗时:0.156秒引用书上作者的话:===================================================================
如果使用三数据项取中划分方法,则必须要遵循快速排序算法不能执行三个或者少于三个数据项的划分的规则。在这种情况下,数字3被称为切割点(cutoff)。在第2个例子中,是用一段代码手动地对两个或三个数据项的子数组来排序的。这并不是最好的方法。
处理小划分的另一个选择是使用插入排序。当使用插入排序的时候,不用限制以3为切割点。可以把界限定为10、20或者其他任何数。试验不同切割点的值以找到最好的执行效率,这件事是很有意义的。Knuth推荐使用9作为切割点。但是,最好的选择值取决于计算机、操作系统、编译器等。上面这个例子(第3个例子)使用插入排序来处理小于10个数据项(即长度为9)的子数组。在第3个例子中,对小的子数组使用插入排序被证实为最快的一种方法,但是它不比在第2个例子中对三个或者更少的数据项的子数组手动地排序快。比较和复制的次数在快速排序阶段都大大地减少了,但是在插入排序阶段却又上升了差不多相同的次数,因此并没有明显地节省时间。但是,要想把快速排序的性能发挥到极限,这个方法大概还是有用的。另一个选择是对数组整个使用快速排序,不去考虑小于界限的划分的排序。如果使用这种做法,那么应该从recQuickSort()中删除对方法insertionSort()的调用。当快速排序结束时,数组已经是基本有序的了。然后可以对整个数组应用插入排序。插入排序对基本有序的数组执行效率很高,而且很多专家都提倡使用这个方法,但是在我们的设置中,这个方法运行得很慢。插入排序显然更合适做很多小规模的排序,而不是一个大的排序。
===================================================================
以下是改动了第3个例子后运行的结果,看起来要比第3个例子慢,甚至比第2个例子慢。
耗时:0.187秒
耗时:0.187秒
耗时:0.187秒
耗时:0.187秒
耗时:0.188秒
耗时:0.172秒
耗时:0.188秒
耗时:0.187秒
耗时:0.188秒
耗时:0.187秒当时看的这本书叫《Java数据结构和算法》,中国电力出版社的。
不过,实际应用中用Java提供的api就可以了,api是开发人员反复测试和用户长期体验的结果,其效率和可靠性都是信得过的。
对一般Java程序员来说,用好Comparable接口和Comparator类就足够了,没必要自己去写排序算法。
冒泡排序
插入排序
选择排序
快速排序
楼主【xieqian_ssmc】截止到2008-07-18 09:37:54的历史汇总数据(不包括此帖):
发帖的总数量:0 发帖的总分数:0 每贴平均分数:0
回帖的总数量:0 得分贴总数量:0 回帖的得分率:0%
结贴的总数量:0 结贴的总分数:0
无满意结贴数:0 无满意结贴分:0
未结的帖子数:0 未结的总分数:0
结贴的百分比:---------------------结分的百分比:---------------------
无满意结贴率:---------------------无满意结分率:---------------------
如何结贴请参考这里:http://topic.csdn.net/u/20080501/09/ef7ba1b3-6466-49f6-9d92-36fe6d471dd1.html