Java中兑现的各种排序算法

2013-03-01

Java中实现的各种排序算法package cn.edu.hactcmimport java.io.BufferedReaderimport java.io.IOExcept

Java中实现的各种排序算法

package cn.edu.hactcm;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
/**
* 查找元素的位置
*/
public class TheFirstOne {

public static void main(String[] args) {
  int[] temp = { 10, 20, 32, 2, 565, 232, 54, 67, 34, 0 };
  System.out.print("请输入你要找的值：");
  BufferedReader buf = new BufferedReader(
    new InputStreamReader(System.in));
  int key = 0;
  try {
   key = Integer.parseInt(buf.readLine());
  } catch (NumberFormatException e) {
   e.printStackTrace();
  } catch (IOException e) {
   e.printStackTrace();
  } finally{
   if (buf != null) {
    try {
     buf.close();
    } catch (IOException e) {
     throw new RuntimeException(e.getMessage(), e);
    }
   }
   buf = null;
  }
  System.out.println("您要查找的元素在数组中的位置为：" + seqSearch(temp, key));
}

/**
*查询算法
*/
public static int seqSearch(int temp[], int key) {
  int i;
  for (i = 0; temp[i] != key; i++);
  if (i == temp.length) {
   return -1;
  } else {
   return i;
  }
}

}

package cn.edu.hactcm;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
/**
* 查找元素的位置
*/
public class TheSecondOne {

/**
* 中分查找
* @param temp
* @param key ：我们要找的值
* @return
*/
public static int BinSearch(int[] temp, int key) {
  int low = 0, high = temp.length - 1, mid; // high表示数组最后一个的下标
  while (low <= high) {
   mid = (low + high) / 2;
   //如果中间值恰好为我们要找的值
   if (temp[mid] == key)
    return mid;
   if (temp[mid] > key)
    high = mid - 1;
   else
    low = mid + 1;
  }
  return -1; // 当low》high时表示查找区间为空，查找失败
}
}

package cn.edu.hactcm;
/**
* 选择排序算法
*/
public class SelectSortDemo {

public static void main(String[] args) {
  int R[] = { 22, 12, 34, 123, 65, 34, 65, 34, 567, 3, 65, 45, 546, 4 };
  SelectSort(R);
  for (int i = 0; i < R.length; i++) {
   System.out.print(R[i] + " ");
  }
}

public static void SelectSort(int[] R) {
  int i, j, k;
  int temp;
  for (i = 0; i < R.length - 1; i++) {
   k = i; // 最开始是将k的值赋给要比较的数字
   for (j = i + 1; j < R.length; j++) {
    if (R[j] < R[k]) {
     k = j; // k记下目前找到的最小关键字所在的位置
    }
   }
   if (k != i) { // 一定要记住是k和i之间的比较
    temp = R[i];
    R[i] = R[k];
    R[k] = temp;
   }
  }
}

}

package cn.edu.hactcm;
/**
* 快排算法
*/
public class QuickSortDemo {

public static void main(String[] args) {
  int R[] = { 22, 12, 34, 123, 65, 34, 65, 34, 567, 3, 65, 45, 546, 4 };
  QuickSort(R, 0, 13);
  for (int i = 0; i < R.length; i++) {
   System.out.print(R[i] + " ");
  }
}

public static void QuickSort(int[] R, int low, int high) {
  if (low > high)
   return;
  int pivot = R[low];
  int i = low;
  int j = high;
  while (i < j) {
   while (i < j && R[j] >= pivot)
    j--;
   R[i] = R[j]; // 将后面的值赋给R[i],使小的数值排在前面
   while (i < j && R[i] <= pivot)
    i++;
   R[j] = R[i]; // 当前面的数值中有大于pivot的数值时，将之后排
  }
  R[i] = pivot; // 将空出来的位置放上pivot
  QuickSort(R, low, i - 1);
  QuickSort(R, i + 1, high);
}

}

package cn.edu.hactcm;
/**
* 插入排序算法
*/
public class InsertSortDemo01 {

public static void main(String[] args) {
  int R[] = { 110, 3, 23, 23, 231, 342, 45 };
  System.out.println("直接插入排序后的结果为：");
  InsertSort(R);
  for (int i = 0; i < R.length; i++) {
   System.out.print(R[i] + " ");
  }
}

public static void InsertSort(int[] R) {
  for (int i = 1; i < R.length; i++) { // 注意此处从1开始的
   if (R[i] < R[i - 1]) {
    int temp = R[i]; // 要排序的数字
    int j = 0;
    for (j = i - 1; j >= 0 && temp < R[j]; j--) {
     R[j + 1] = R[j]; // 将数据后移
    }
    // 若不符合上面的情况时让数组的i个的值为temp
    R[j + 1] = temp;
   }
  }
}

}

package cn.edu.hactcm;
/**
* 哈希算法
*/
public class HashDemo01 {

public static void main(String[] args) {
  System.out.println("输入数字：");
  int temp[] = { 110, 3, 23, 23, 231, 342, 45 };
  System.out.println("数字平方，去中间的三位数字的结果为：");
  Hash(temp);
  for (int i = 0; i < temp.length; i++) {
   System.out.print(temp[i] + " ");
  }
}

public static void Hash(int temp[]) {
  for (int i = 0; i < temp.length; i++) {
   temp[i] *= temp[i];
   temp[i] /= 100; // 先求平方，后去掉末尾的两位数字
   temp[i] = temp[i] % 1000; // 取得时余
  }
}

}

package cn.edu.hactcm;

/**
* 冒泡排序算法
*/
public class BubbleSortDemo {

public static void main(String[] args) {
  int R[] = { 22, 12, 34, 123, 65, 34, 65, 34, 567, 3, 65, 45, 546, 4 };
  BubbleSort(R);
  for (int i = 0; i < R.length; i++) {
   System.out.print(R[i] + " ");
  }
}

public static void BubbleSort(int[] R) {
  int i, j;
  Boolean exchange;
  int tmp;
  int n = R.length;
  for (i = 1; i < n; i++) {
   // 最多做n-1趟排序
   exchange = false; // 本趟排序开始前，交换标志应为假
   for (j = 0; j < n - i; j++) { // 对当前无序去R[0...n-i]自下向上扫描
    if (R[j] > R[j + 1]) {
     // 交换记录
     tmp = R[j + 1];
     R[j + 1] = R[j];
     R[j] = tmp;
     exchange = true; // 当发生了交换，提前终止算法
    }
   }
   if (!exchange) {// 本趟排序未发生交换，提前终止算法
    return;
   }
  }
}

}

热点排行

编程

Java中兑现的各种排序算法