一震放、排序
1.簡單選擇排序（O(n*n)）
【思路】找出數(shù)組中最小的元素，將其與第一個元素交換位置驼修，然后再在剩下的元素中找出最小的元素殿遂，并與數(shù)組的第二個元素交換位置。
【特點】
原地排序乙各，不穩(wěn)定墨礁。
運行時間和輸入無關(guān)。一個已經(jīng)有序的數(shù)組和一個元素隨機排列的數(shù)組所用的時間一樣耳峦。
移動數(shù)據(jù)最少恩静。交換次數(shù)和數(shù)組大小是線性關(guān)系，每次交換都有一個元素位于正確的位置蹲坷。
import java.util.Arrays;
public class SelectSort {
/**
* 簡單選擇排序
* @param a
*/
public static void sort(int[] a) {
for(int i =0;i<a.length;i++) {
int minIndex = i;
for(int j=i+1;j<a.length;j++) {
if(a[minIndex]>a[j]) {
minIndex = j;
}
}
if(a[i]>a[minIndex]) {
int temp = a[i];
a[i] = a[minIndex];
a[minIndex] = temp;
}
System.out.println("第"+(i+1)+"次："+Arrays.toString(a));
}
}
public static void main(String[] args) {
int[] a = {9,8,7,5,4,2,1};
System.out.println("排序前:"+Arrays.toString(a));
sort(a);
}
}
輸出：
排序前:[9, 8, 7, 5, 4, 2, 1]
第1次：[1, 8, 7, 5, 4, 2, 9]
第2次：[1, 2, 7, 5, 4, 8, 9]
第3次：[1, 2, 4, 5, 7, 8, 9]
第4次：[1, 2, 4, 5, 7, 8, 9]
第5次：[1, 2, 4, 5, 7, 8, 9]
第6次：[1, 2, 4, 5, 7, 8, 9]
第7次：[1, 2, 4, 5, 7, 8, 9]
2.插入排序（O(n*n)）
【特點】
原地排序驶乾，穩(wěn)定。
插入排序所需的時間與輸入的元素的初始順序有關(guān)循签。
import java.util.Arrays;
public class InsertSort {
/**
* 插入排序
* @param a
*/
public static void sort(int[] a) {
for(int i = 1;i<a.length;i++) {
for(int j=0;j<i;j++) {
if(a[j]>a[i]) {
int temp = a[i];
for(int k = i;k>0;k--) {
exch(a,k,k-1);
}
a[j] = temp;
break;
}
}
System.out.println("第"+(i)+"次："+Arrays.toString(a));
}
}
public static void exch(int[]a ,int i,int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
public static void main(String[] args) {
int[] a = {9,8,7,5,4,2,2,1};
System.out.println("排序前："+Arrays.toString(a));
sort(a);
}
}
輸出：
排序前：[9, 8, 7, 5, 4, 2, 1]
第1次：[8, 9, 7, 5, 4, 2, 1]
第2次：[7, 8, 9, 5, 4, 2, 1]
第3次：[5, 7, 8, 9, 4, 2, 1]
第4次：[4, 5, 7, 8, 9, 2, 1]
第5次：[2, 4, 5, 7, 8, 9, 1]
第6次：[1, 2, 4, 5, 7, 8, 9]
3.冒泡排序（O(n*n)）
【思路】遍歷數(shù)組级乐，若相鄰的兩個元素大小順序不對，交換這兩個元素的位置县匠。
【特點】
穩(wěn)定风科。
每次冒泡，會有一個數(shù)字位于正確的位置乞旦。
import java.util.Arrays;
public class BubbleSort {
/**
* 冒泡排序
* @param a
*/
public static void sort(int[] a) {//大數(shù)從數(shù)組后面冒出
for(int i = a.length-1;i>0;i--) {
for(int j = 0;j<i;j++) {
if(a[j]>a[j+1]) {
int temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
}
}
System.out.println("第"+(a.length-i)+"次："+Arrays.toString(a));
}
}
public static void sort1(int[] a) {//小數(shù)從數(shù)組前面冒出
for(int i = 0;i<a.length;i++) {
for(int j = a.length-1;j>i;j--) {
if(a[j]<a[j-1]) {
int temp = a[j];
a[j] = a[j-1];
a[j-1] = temp;
}
}
System.out.println("第"+(i+1)+"次："+Arrays.toString(a));
}
}
public static void main(String[] args) {
int[] a = {9,8,7,5,4,2,2,1};
System.out.println("排序前："+Arrays.toString(a));
sort(a);
}
}
輸出：
排序前：[9, 8, 7, 5, 4, 2, 2, 1]
第1次：[8, 7, 5, 4, 2, 2, 1, 9]
第2次：[7, 5, 4, 2, 2, 1, 8, 9]
第3次：[5, 4, 2, 2, 1, 7, 8, 9]
第4次：[4, 2, 2, 1, 5, 7, 8, 9]
第5次：[2, 2, 1, 4, 5, 7, 8, 9]
第6次：[2, 1, 2, 4, 5, 7, 8, 9]
第7次：[1, 2, 2, 4, 5, 7, 8, 9]
4.希爾排序
【特點】
不穩(wěn)定贼穆。
package com.paixu;
import java.util.Arrays;
public class ShellSort {
/**
* 希爾排序
* @param a
*/
public static void sort(int[] a) {
int h = 1;
int l = a.length;
while(h<l/3)
h = h*3+1;
while(h>=1) {
for(int i=h;i<l;i++) {
for(int j=i;j>=h;j--) {
if(a[j]<a[j-h]) {
int temp = a[j];
a[j] = a[j-h];
a[j-h] = temp;
}
}
}
System.out.println("h="+(h)+"："+Arrays.toString(a));
h = h/3;
}
}
public static void main(String[] args) {
int[] a = {9,8,7,5,4,2,2,1};
System.out.println("排序前："+Arrays.toString(a));
sort(a);
}
}
輸出：
排序前：[9, 8, 7, 5, 4, 2, 2, 1]
h=4：[4, 2, 2, 1, 9, 8, 7, 5]
h=1：[1, 2, 2, 4, 5, 7, 8, 9]
5.歸并（Merge）排序（N*logN）
需要額外的空間，穩(wěn)定杆查。
【】自頂向下和自底向上
6.快速排序（N*logN）
分治，將一個數(shù)組分成兩個子數(shù)組臀蛛，將其獨立排序亲桦。
【思想】以數(shù)組第一個元素（key）對元素進(jìn)行拆分，設(shè)置左右指針浊仆，分別從左邊找到第一個大于key的元素下表客峭，從右邊找出第一個大于key的元素下表，交換其位置抡柿，最后將key插入到其位置舔琅。然后修改key。
歸并排序數(shù)組是等分的洲劣，快排备蚓，切分的位置取決于數(shù)組的內(nèi)容课蔬。
【特點】
- 不穩(wěn)定。
- 每次切分就有一個元素處在正確的位置上郊尝。
import java.util.Arrays;
public class QuickSort {
/**
* 快排
* @param args
*/
public static void main(String[] args) {
int[] a = {30,25,24,31,28,46,20,40};
System.out.println(Arrays.toString(a));
quickSort(a);
System.out.println(Arrays.toString(a));
}
public static void quickSort(int[] a) {
if(a.length>0) {
quickSort(a, 0 , a.length-1);
}
}
public static void quickSort(int[] a,int low,int high) {
if(low>high)//跳出遞歸
return;
int key = a[low];
int i = low;
int j = high;
int temp = i;
while(i<j) {
while(i<j&&a[j] > key) {
j--;
}
a[i] = a[j];
temp = i;
while(i<j&&a[i] <= key) {
//必須等于且i<j
i++;
}
a[j] = a[i];
temp = j;
}
a[temp] =key;
System.out.println(Arrays.toString(a));
quickSort(a,low,i-1);//key左邊快排
quickSort(a,i+1,high);//key右邊快排
}
}
輸出：
[30, 25, 24, 31, 28, 46, 20, 40]
[20, 25, 24, 28, 30, 46, 31, 40]
[20, 25, 24, 28, 30, 46, 31, 40]
[20, 24, 25, 28, 30, 46, 31, 40]
[20, 24, 25, 28, 30, 46, 31, 40]
[20, 24, 25, 28, 30, 46, 31, 40]
[20, 24, 25, 28, 30, 40, 31, 46]
[20, 24, 25, 28, 30, 31, 40, 46]
[20, 24, 25, 28, 30, 31, 40, 46]
[20, 24, 25, 28, 30, 31, 40, 46]
堆排序（完全二叉樹二跋，可以用數(shù)組實現(xiàn)而不需要指針）
不穩(wěn)定。
- 大根堆：父節(jié)點都大于等于它的兩個兒子結(jié)點流昏。
- 小根堆：父節(jié)點都小于等于它的兩個兒子結(jié)點扎即。
int a[];
int n = 0;// 數(shù)組下標(biāo)0不使用
public Duipaixu(int maxN){
a = new int[maxN+1];
}
public void exch(int i,int j) {
int k = a[i];
a[i] = a[j];
a[j] = k;
}
public void insert(int k) {
a[++n] = k;
swim(n);
}
public void del(int index) {//k是數(shù)組下表
exch(index,n--);
sink(index);
}
public boolean compare(int i,int j) {
if(a[i]>a[j])
return false;
else return true;
}
public void swim(int k){//上浮
while(k>1&&compare(k/2,k)) {
exch(k/2,k);
k = k/2;
}
}
public void sink(int k) {//下沉
while(2*k<n) {
int j = 2*k;
if(j<n&&compare(j,j+1)) {
j++;
}
exch(k,j);
k = j;
}
}
public void print() {// 輸出
int hang = 2;
for(int i = 1;i<=n;i++) {
System.out.print(a[i]+" ");
if(i == hang-1) {
hang = hang*2;
System.out.println();
}
}
}
}
二、查找
1.二分查找（時間復(fù)雜度O(logN)）
int l0 = 0;
int ln = arr.length-1;
while (l0<=ln) {
int mid = l0+(ln-l0)/2;
System.out.println(l0+" "+mid+" "+ln);
if(arr[mid] > key) {
ln = mid-1;
}
else if (arr[mid] < key) {
l0 = mid+1;
}
else return mid;
}
return -1;
}
public static int BinarySearch(int[] a,int key,int low,int high) {// 遞歸實現(xiàn)
int mid = low+(high-low)/2;
if(a[mid]==key) {
return mid;
}
else if(a[mid]>key) {
return DiguiBinary(a,key,low,mid-1);
}
else return DiguiBinary(a,key,mid+1,high);
}
2.二叉排序樹（時間復(fù)雜度O(logN)）
樹
3.B樹
B樹是一種多路搜索樹况凉，主要用在文件系統(tǒng)和數(shù)據(jù)庫系統(tǒng)谚鄙，文件系統(tǒng)和數(shù)據(jù)庫主要存儲在磁盤，B樹就是為了降低磁盤I/O次數(shù)刁绒。
二叉排序樹深度是logN闷营，所以時間復(fù)雜度是O(logN)，要降低復(fù)雜度膛锭，就要降低樹的深度粮坞。它是一種平衡多路查找樹。
B+樹（查找兩個值之間的多個元素時）
索引都是排好序的初狰。
- 只有最底層的節(jié)點（葉子節(jié)點）才保存信息莫杈。
- 其它節(jié)點（非葉子結(jié)點）只是在搜索中用來指引到正確節(jié)點的。
- 結(jié)點個數(shù)多了一倍
- 葉子結(jié)點跟后續(xù)葉子結(jié)點是連接的奢入，
- 插入和刪除操作的時間復(fù)雜度是 O(log(N)) 筝闹。
