一、排序
1.简单选择排序（O(n*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)）
【特点】
原地排序，稳定。
插入排序所需的时间与输入的元素的初始顺序有关。
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)）
【思路】遍历数组，若相邻的两个元素大小顺序不对，交换这两个元素的位置。
【特点】
稳定。
每次冒泡，会有一个数字位于正确的位置。
import java.util.Arrays;
public class BubbleSort {
/**
* 冒泡排序
* @param a
*/
public static void sort(int[] a) {//大数从数组后面冒出
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) {//小数从数组前面冒出
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.希尔排序
【特点】
不稳定。
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）
需要额外的空间，稳定。
【】自顶向下和自底向上
6.快速排序（N*logN）
分治，将一个数组分成两个子数组，将其独立排序。
【思想】以数组第一个元素（key）对元素进行拆分，设置左右指针，分别从左边找到第一个大于key的元素下表，从右边找出第一个大于key的元素下表，交换其位置，最后将key插入到其位置。然后修改key。
归并排序数组是等分的，快排，切分的位置取决于数组的内容。
【特点】
- 不稳定。
- 每次切分就有一个元素处在正确的位置上。
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]
堆排序（完全二叉树，可以用数组实现而不需要指针）
不稳定。
- 大根堆：父节点都大于等于它的两个儿子结点。
- 小根堆：父节点都小于等于它的两个儿子结点。
int a[];
int n = 0;// 数组下标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是数组下表
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.二分查找（时间复杂度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) {// 递归实现
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.二叉排序树（时间复杂度O(logN)）
树
3.B树
B树是一种多路搜索树，主要用在文件系统和数据库系统，文件系统和数据库主要存储在磁盘，B树就是为了降低磁盘I/O次数。
二叉排序树深度是logN，所以时间复杂度是O(logN)，要降低复杂度，就要降低树的深度。它是一种平衡多路查找树。
B+树（查找两个值之间的多个元素时）
索引都是排好序的。
- 只有最底层的节点（叶子节点）才保存信息。
- 其它节点（非叶子结点）只是在搜索中用来指引到正确节点的。
- 结点个数多了一倍
- 叶子结点跟后续叶子结点是连接的，
- 插入和删除操作的时间复杂度是 O(log(N)) 。
