用Java寫一個(gè)冒泡排序。?
答：冒泡排序幾乎是個(gè)程序員都寫得出來(lái)，但是面試的時(shí)候如何寫一個(gè)逼格高的冒泡排序卻不是每個(gè)人都能做到，下面提供一個(gè)
import java.util.Comparator;
public interface Sorter {
? /**
? ? * 排序
? ? * @param list 待排序的數(shù)組
? ? */
? public <T extends Comparable<T>> void sort(T[] list);
? /**
? ? * 排序
? ? * @param list 待排序的數(shù)組
? ? * @param comp 比較兩個(gè)對(duì)象的比較器
? ? */
? public <T> void sort(T[] list, Comparator<T> comp);
}
import java.util.Comparator;
/**
* 冒泡排序
* @author mch
*/
public class BubbleSorter implements Sorter {
? ? @Override
? ? public <T extends Comparable<T>> void sort(T[] list) {
? ? ? ? boolean swapped = true;
? ? ? ? for (int i = 1, len = list.length; i < len && swapped; ++i) {
? ? ? ? ? ? swapped = false;
? ? ? ? ? ? for (int j = 0; j < len - i; ++j) {
? ? ? ? ? ? ? ? if (list[j].compareTo(list[j + 1]) > 0) {
? ? ? ? ? ? ? ? ? ? T temp = list[j];
? ? ? ? ? ? ? ? ? ? list[j] = list[j + 1];
? ? ? ? ? ? ? ? ? ? list[j + 1] = temp;
? ? ? ? ? ? ? ? ? ? swapped = true;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? }
? ? }
? ? @Override
? ? public <T> void sort(T[] list, Comparator<T> comp) {
? ? ? ? boolean swapped = true;
? ? ? ? for (int i = 1, len = list.length; i < len && swapped; ++i) {
? ? ? ? ? ? swapped = false;
? ? ? ? ? ? for (int j = 0; j < len - i; ++j) {
? ? ? ? ? ? ? ? if (comp.compare(list[j], list[j + 1]) > 0) {
? ? ? ? ? ? ? ? ? ? T temp = list[j];
? ? ? ? ? ? ? ? ? ? list[j] = list[j + 1];
? ? ? ? ? ? ? ? ? ? list[j + 1] = temp;
? ? ? ? ? ? ? ? ? ? swapped = true;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? }
? ? }
}
95、用Java寫一個(gè)折半查找
折半查找，也稱二分查找、二分搜索，是一種在有序數(shù)組中查找某一特定元素的搜索算法。搜素過程從數(shù)組的中間元素開始，如果中間元素正好是要查找的元素，則搜素過程結(jié)束；如果某一特定元素大于或者小于中間元素，則在數(shù)組大于或小于中間元素的那一半中查找，而且跟開始一樣從中間元素開始比較
import java.util.Comparator;
public class MyUtil {
? public static <T extends Comparable<T>> int binarySearch(T[] x, T key) {
? ? ? return binarySearch(x, 0, x.length- 1, key);
? }
? // 使用循環(huán)實(shí)現(xiàn)的二分查找
? public static <T> int binarySearch(T[] x, T key, Comparator<T> comp) {
? ? ? int low = 0;
? ? ? int high = x.length - 1;
? ? ? while (low <= high) {
? ? ? ? ? int mid = (low + high) >>> 1;
? ? ? ? ? int cmp = comp.compare(x[mid], key);
? ? ? ? ? if (cmp < 0) {
? ? ? ? ? ? low= mid + 1;
? ? ? ? ? }
? ? ? ? ? else if (cmp > 0) {
? ? ? ? ? ? high= mid - 1;
? ? ? ? ? }
? ? ? ? ? else {
? ? ? ? ? ? return mid;
? ? ? ? ? }
? ? ? }
? ? ? return -1;
? }
? // 使用遞歸實(shí)現(xiàn)的二分查找
? private static<T extends Comparable<T>> int binarySearch(T[] x, int low, int high, T key) {
? ? ? if(low <= high) {
? ? ? ? int mid = low + ((high -low) >> 1);
? ? ? ? if(key.compareTo(x[mid])== 0) {
? ? ? ? ? return mid;
? ? ? ? }
? ? ? ? else if(key.compareTo(x[mid])< 0) {
? ? ? ? ? return binarySearch(x,low, mid - 1, key);
? ? ? ? }
? ? ? ? else {
? ? ? ? ? return binarySearch(x,mid + 1, high, key);
? ? ? ? }
? ? ? }
? ? ? return -1;
? }
}
