插入排序
基本思想：在要排序的一組數(shù)中，假設(shè)前面(n-1) [n>=2] 個(gè)數(shù)已經(jīng)是排
好順序的等浊，現(xiàn)在要把第n個(gè)數(shù)插到前面的有序數(shù)中，使得這n個(gè)數(shù)
也是排好順序的摹蘑。如此反復(fù)循環(huán)筹燕，直到全部排好順序。
public static void sort(int[] a) {
if (a == null || a.length == 0) {
return;
}
for (int i = 1; i < a.length; i++) {
int j = i - 1;
int temp = a[i]; // 先取出待插入數(shù)據(jù)保存衅鹿，因?yàn)橄蚝笠莆贿^程中會(huì)把覆蓋掉待插入數(shù)
while (j >= 0 && temp < a[j]) { // 如果待是比待插入數(shù)據(jù)大撒踪，就后移
a[j+1] = a[j];
j--;
}
a[j+1] = temp; // 找到比待插入數(shù)據(jù)小的位置，將待插入數(shù)據(jù)插入
}
}
冒泡排序
基本思想：在要排序的一組數(shù)中大渤，對(duì)當(dāng)前還未排好序的范圍內(nèi)的全部數(shù)制妄，自上而下對(duì)相鄰的兩個(gè)數(shù)依次進(jìn)行比較和調(diào)整，讓較大的數(shù)往下沉泵三，較小的往上冒耕捞。即：每當(dāng)兩相鄰的數(shù)比較后發(fā)現(xiàn)它們的排序與排序要求相反時(shí)，就將它們互換烫幕。
public void bubbleSort() {
int[] a = {49, 38, 65, 97, 76, 13, 27, 49, 78, 34};
int temp;
for (int i = 0; i < a.length - 1; i++) {
for (int j = 0; j < a.length - 1 - i; j++) {
if (a[j] > a[j + 1]) {
temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
}
}
}
for (int value : a) System.out.print("-" + value);
}
選擇排序
基本思想：在要排序的一組數(shù)中俺抽，選出最小的一個(gè)數(shù)與第一個(gè)位置的數(shù)交換；
然后在剩下的數(shù)當(dāng)中再找最小的與第二個(gè)位置的數(shù)交換较曼，如此循環(huán)到倒數(shù)第二個(gè)數(shù)和最后一個(gè)數(shù)比較為止磷斧。
public class SelectSort {
public static void sort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
int min = i;
for (int j = i+1; j < arr.length; j ++) { //選出之后待排序中值最小的位置
if (arr[j] < arr[min]) {
min = j;
}
}
if (min != i) {
arr[min] = arr[i] + arr[min];
arr[i] = arr[min] - arr[i];
arr[min] = arr[min] - arr[i];
}
}
}
快速排序
基本思想：選擇一個(gè)基準(zhǔn)元素,通常選擇第一個(gè)元素或者最后一個(gè)元素,通過一趟掃描，將待排序列分成兩部分,一部分比基準(zhǔn)元素小,一部分大于等于基準(zhǔn)元素,此時(shí)基準(zhǔn)元素在其排好序后的正確位置,然后再用同樣的方法遞歸地排序劃分的兩部分捷犹。
/**
* 快速排序（挖坑法遞歸）
* @param arr 待排序數(shù)組
* @param low 左邊界
* @param high 右邊界
*/
public static void sort(int arr[], int low, int high) {
if (arr == null || arr.length <= 0) {
return;
}
if (low >= high) {
return;
}
int left = low;
int right = high;
int temp = arr[left]; //挖坑1：保存基準(zhǔn)的值
while (left < right) {
while (left < right && arr[right] >= temp) {
right--;
}
arr[left] = arr[right]; //坑2：從后向前找到比基準(zhǔn)小的元素弛饭，插入到基準(zhǔn)位置坑1中
while (left < right && arr[left] <= temp) {
left ++;
}
arr[right] = arr[left]; //坑3：從前往后找到比基準(zhǔn)大的元素，放到剛才挖的坑2中
}
arr[left] = temp; //基準(zhǔn)值填補(bǔ)到坑3中伏恐，準(zhǔn)備分治遞歸快排
System.out.println("Sorting: " + Arrays.toString(arr));
sort(arr, low, left-1);
sort(arr, left + 1, high);
}
二分查找
基本思想：假設(shè)表中元素是按升序排列孩哑，將表中間位置記錄的關(guān)鍵字與查找關(guān)鍵字比較，如果兩者相等翠桦，則查找成功横蜒；否則利用中間位置記錄將表分成前胳蛮、后兩個(gè)子表，如果中間位置記錄的關(guān)鍵字大于查找關(guān)鍵字丛晌，則進(jìn)一步查找前一子表仅炊，否則進(jìn)一步查找后一子表。重復(fù)以上過程澎蛛，直到找到滿足條件的記錄抚垄，使查找成功，或直到子表不存在為止谋逻，此時(shí)查找不成功呆馁。
條件是：
1.必須采用順序存儲(chǔ)結(jié)構(gòu)
2.必須按關(guān)鍵字大小有序排列。
public class BinarySearch {
/**
* 非遞歸方法毁兆，利用while循環(huán)
* @param arr
* @param des
* @return
*/
public static int binarySearch(int[] arr,int des){
int low = 0;
int high = arr.length-1;
while(low<=high){
int middle = (low+high)/2;
if (arr[middle] == des) {
return middle;
}else if (arr[middle]<des) {
low = middle+1;
}else {
high = middle-1;
}
}
return -1;
}
/**
* 遞歸查找
* @param arr
* @param des
* @param low
* @param high
* @return
*/
public static int binarySearch(int[] arr,int des,int low,int high){
int middle = (low+high)/2;
if (des<arr[low]||des>arr[high]||low>high) {
return -1;
}
if (arr[middle]<des) {
return binarySearch(arr, des, middle+1, high);
}else if (arr[middle]>des) {
return binarySearch(arr, des, low, middle-1);
}else{
return middle;
}
}
public static void main(String[] args){
int[] arr = {1,2,3,4,5,6,7,8,11,15,17};
int des = 15;
System.out.println(binarySearch(arr, des));
System.out.println(binarySearch(arr, des, 0, 10));
}
}