随笔-60  评论-117  文章-0  trackbacks-0

     想总结一下这个问题是因为这是找工作的时候必考的东西。我最近很担心会被解雇。以后再什么事也不上心可不行。到了一个新环境毕竟不像在大学里那么游刃有余了。
接收数组的java源程序:
import java.io.BufferedReader;
import java.io.InputStreamReader;

 class Sort {
 int Length = 0;
 
 public int[]Input(){
  
  try {

   

    BufferedReader num = new BufferedReader(new InputStreamReader(
      System.in));
    Length = Integer.parseInt(num.readLine());
   

  } catch (Exception e) {
   e.printStackTrace();
  }//从客户端接收要排序的数组的长度。
  int[] a = new int[Length]; 
  try {

   for (int i = 0; i < a.length; i++) {

    BufferedReader array_int = new BufferedReader(new InputStreamReader(
      System.in));
    a[i] = Integer.parseInt(array_int.readLine());
   }

  } catch (Exception e) {
   e.printStackTrace();
  }//从客户端接收要排序的数组。
return(a);
 }
 
}
上面一段代码主要完成接收要排序的数组的功能。也可以自己指定一数组,不影响这里要讲的主要问题。
      直接插入排序:
算法思想:每次将一个待排序的数据元素,插入到前面已经排好序的数列中的适当位置,使数列依然有序;直到待排序数据元素全部插入完为止。
java 源程序:

package sort.insertSort;

import java.util.Arrays;


public class DirectInsertSort {
 private static Integer[] insert(Integer[] sourceNums) {
  
  //如果没有要排序的数据,直接返回
  if(sourceNums == null || sourceNums.length == 0) {
   return new Integer[]{};
  }
  
  Integer nums[] = new Integer[sourceNums.length];//已排好序的数组。
  nums[0] = sourceNums[0];//先将一个数值放到nums中(因为只有一个数,也可以看作排好序的。
  
  for(int i=1; i<sourceNums.length; i++) {
   Integer num = sourceNums[i];
   for(int j=i; j>0; j--) {
    if(num >= nums[j-1]){//如果要插入的数值不小于最后一个数值,则直接插入到最后面。
     nums[j] = num;
     break;
    } else if(num < nums[j-1]) {//如果要插入的数值小于nums最后一个数值,则将nums当前数值后移一位
     nums[j] = nums[j-1];
     if(j == 1) {
      nums[j-1] = num;//应对当要插入的数小于nums所有数的情况
     }
    }
   }
  }
  
  return nums;
 }

 public static void main(String[] args) {
  System.err.println(Arrays.toString(DirectInsertSort.insert(new Integer[]{34,56,78,-11,49,-45,-90,85})));
 }
}

选择排序:
算法思想:每一趟从待排序的数据元素中选出最小(或最大)的一个元素,顺序放在已排好序的数列的最后,直到全部待排序的数据元素排完。
public class SelectSort extends Sort{
 public static  void main(String args[]) {
  Sort sort=new Sort();
  int[] a=sort.Input();   //调用父类函数,接收字符串。
  int q;
  int i=0;
  while(i<a.length){
   int j=i;
   while(j<a.length){
    if(a[i]>a[j]){
     q=a[i];
     a[i]=a[j];
     a[j]=q;
    }
    
    j++;
   }
   i++;
  }//while循环部分完成排序。
   
  for(int j=0;j<a.length;j++){
   System.out.print(a[j]+"   "); 
 }
}
}
冒泡排序 :
算法思想:
两两比较待排序数据元素的大小,发现两个数据元素的次序相反时即进行交换,直到没有反序的数据元素为止。

package sort.bubbleSort;

import java.util.Arrays;

public class BubbleSort {
 
 static Integer[] bubbleSort(Integer[] nums) {
  boolean change = true;
  int i;
  for(i=0; i< nums.length-1 && change; i++) {
   change = false;
   for(int j=0; j<nums.length-i-1; j++) {
    if(nums[j]>nums[j+1]) {
     int num = nums[j];
     nums[j] = nums[j+1];
     nums[j+1] = num;
     change = true;
    }
   }
   System.err.println(Arrays.toString(nums));
  }

  return nums;
 }

 public static void main(String[] args) {
  BubbleSort.bubbleSort(new Integer[]{34,56,78,-11,49,-45,-90,85,65,63,-12,33,35});
 }

}


希尔排序(缩小增量法)  
算法思想:先取一个正整数d1<n,把所有相隔d1的记录放一组,组内进行直接插入排序;然后取d2<d1,重复上述分组和排序操作;直至di=1,即所有记录放进一个组中排序为止  
public class ShellSorter extends Sort {
 public static void main(String args[]) {

  Sort sort = new Sort();
  int[] a = sort.Input();
  int q = 0;
  
  int group = a.length / 3 + 1;
  while(group > 0) {
   int i = 0;
   while (i < group) {
    int j = i;
    while ( j < a.length) {
     int k = j;
     while ( k > i) {
      if (a[k] < a[k - group]) {
       q = a[k];
       a[k] = a[k -group];
       a[k - group] = q;
       
      }
       k -= group;
     }
     j += group;
    }
    i++;
   }
   group--;
  }
  for (int j = 0; j < a.length; j++) {
   System.out.print(a[j] + "   ");
  }
 }
}

posted on 2007-04-18 10:05 静儿 阅读(303) 评论(7)  编辑  收藏 所属分类: 技术

评论:
# re: 排序问题 2007-04-19 05:41 | 山风小子
如果作为对数据结构和算法的温习,自己实现排序算法是一个很不错的途径。
但如果在实际开发中,我建议你使用Arrays类中的sort方法,和Collections类中的sort方法。  回复  更多评论
  
# re: 排序问题 2007-04-19 05:45 | 山风小子
再补充一句,
Java对类名,接口名,方法名,变量名都有规范
类名,接口名:首字母大写,且用驼峰命名法命名,比如 HelloWorld
方法名,变量名:首字母小写,且用驼峰命名法命名,比如 sayHello()  回复  更多评论
  
# re: 排序问题 2007-04-19 08:28 | 静儿
@山风小子
十分感谢您的建议!  回复  更多评论
  
# re: 排序问题 2007-04-19 09:28 | cresposhi
Java API中的sort是使用优化了的合并排序算法,大多数情况下是效率是很高的,并且很稳定。不过如果设计到特殊的场景可能还是需要自己来实现排序算法,所以熟练掌握各种排序算法绝对是必要的。  回复  更多评论
  
# re: 排序问题 2007-04-21 22:59 | 小飞鸟
public voi maopao(int[] array)
{
int i,k;
for(i=0;i<array.length;i++)
{
for(k=0;k<array.length-1-i;k++)
{
if(array[i]<array[i+1])
{
int temp = array[i];
array[i] = array[i+1];
array[i+1] = temp;
}
}
}

}

一冒泡算法 呵呵 和你的比较一下 当然 方法名的命名别学我 不规范哟。。  回复  更多评论
  
# re: 排序问题 2007-04-27 10:43 | ddd
面试竟考这么些没用的。。

实际应用中,几乎用不到。。。  回复  更多评论
  
# re: 排序问题 2007-04-27 14:55 | 静儿
呵呵,你的看起来清晰多了。@小飞鸟
  回复  更多评论
  

只有注册用户登录后才能发表评论。


网站导航: