目录：
- 算法简介
- 排序算法
- 递归与穷举
- 贪心与分治
- 动态规划和回溯
1.算法简介
解题方案的准确而完整的描述，是一系列解决问题的清晰指令。
特征
- 有穷性
- 确切性
- 输入项
- 输出项
- 可行性
算法优劣评定
- 时间复杂度
- 空间复杂度
- 正确性
- 可读性
- 健壮性
2.算法排序
2.1 插入排序
- 冒泡排序
public static void main(String [] args){
int[] a = {49,38,65,97,23,22,76,1,5,8,2,0,-1};
//直接插入排序开始
for(int i = 1;i<a.length;i++){
int temp = a[i];//新遍历的值，等待插入到前面的有序数组
int j;
for(j = i-1;j>=0;j--){
//将大于temp的数往后面移一步
if(a[j]>temp){
a[j+1] = a[j];
}else{
break;
}
}
//break数据代表j处数据小于temp，j之前的数据又是从小到大排列，所以temp就放在j后面
a[j+1] = temp;
}
System.out.println("排序后：");
for(int i = 0;i<a.length;i++){
System.out.println(" "+a[i]);
}
}
时间复杂度：O(N^2)
- 二分法排序
时间复杂度：O(logN)
- 希尔排序
时间复杂度：O(N^(3/2))
2.2 选择排序
- 简单选择排序
时间复杂度：O(N^(3/2))
- 堆排序
//堆排序
public static void main(String[] args){
int[] array = {39,44,1,0,8,66,23,67,9,15,100,70,22,3,6,54};
HeapSort heapSort = new HeapSort();
heapSort.heapSort(array);
for(int i = 0;i<array.length;i++){
System.out.println(" "+array[i]);
}
}
public void heapSort(int [] a){
if(a == null||a.length<=1){
return;
}
//创建大堆
buildMaxHeap(a);
for(int i = a.length-1;i>=1;i--){
//最大元素已经排在了下标为0的地方
exchangeElements(a, 0, i);//每交换换一次，就沉淀一个大元素
maxHeap(a, i, 0);
}
}
private void buildMaxHeap(int[] a) {
int half = (a.length -1)/2;//假设长度为9
for(int i = half;i>=0;i--){
//只需遍历43210
maxHeap(a,a.length,i);
}
}
//length表示用于构造大堆的数组长度元素数量
private void maxHeap(int[] a, int length, int i) {
int left = i*2+1;
int right = i*2+2;
int largest = i;
if(left<length&&a[left]>a[i]){
largest = left;
}
if(right<length&&a[right]>a[largest]){
largest = right;
}
if(i!=largest){
//进行数据交换
exchangeElements(a,i,largest);
maxHeap(a, length, largest);
}
}
//在数组a里进行两个下标元素交换
private void exchangeElements(int[] a, int i, int largest) {
int temp = a[i];
a[i] = a[largest];
a[largest] = temp;
}
时间复杂度：O(NlogN)
2.3 交换排序
- 快速排序
/**
* 快速排序
*
* @param a
* @param i
* @param j
*/
private void quickSort(int[] a, int low, int high) {
if (low < high) {
int middle = getMiddle(a, low, high);
quickSort(a, 0, middle - 1);
quickSort(a, middle + 1, high);
}
}
/**
* 获取中间下标
*
* @param a
* @param low
* @param high
* @return
*/
private int getMiddle(int[] a, int low, int high) {
int temp = a[low];// 基准元素
while (low < high) {
while (low < high && a[high] >= temp) {
high--;
}
a[low] = a[high];
while (low < high && a[low] <= temp) {
low++;
}
a[high] = a[low];
}
a[low] = temp;// 插入到排序后正确的位置
return low;
}
public static void main(String[] args) {
QuickSort quickSort = new QuickSort();
int[] a = { 19, 2, 3, 90, 67, 33, -7, 24, 3, 56, 34, 5 };
quickSort.quickSort(a, 0, a.length - 1);
for (int num : a) {
System.out.println(" " + num);
}
}
时间复杂度：O(NlogN)
2.4 归并排序
//归并排序
public void mergeSort(int[] a, int left, int right) {
if (left < right) {
int middle = (left + right) / 2;
mergeSort(a, left, middle);
mergeSort(a, middle + 1, right);
merge(a, left, middle, right);// 合并
}
}
private void merge(int[] a, int left, int middle, int right) {
int[] tmpArray = new int[a.length];
int rightStart = middle + 1;
int tmp = left;
int third = left;
// 比较两个小数组相应下标位置的数组大小，小的先放进新数组
while (left <= middle && rightStart <= right) {
if (a[left] <= a[rightStart]) {
tmpArray[third++] = a[left++];
} else {
tmpArray[third++] = a[rightStart++];
}
}
// 如果左边还有数据需要拷贝，把左边数组剩下的拷贝到新数组
while (left <= middle) {
tmpArray[third++] = a[left++];
}
// 如果右边还有数据......
while (rightStart <= right) {
tmpArray[third++] = a[rightStart++];
}
while (tmp <= right) {
a[tmp] = tmpArray[tmp++];
}
}
public static void main(String[] args) {
MergeSort mergeSort = new MergeSort();
int[] a = new int[] { 90, 3, 2, 67, 44, -9, 87, 65, 11, 9, 2, 8 };
mergeSort.mergeSort(a, 0, a.length - 1);
for (int n : a) {
System.out.print(" " + n);
}
}
时间复杂度：O(NlogN)
2.5 基数排序
public void sort(int[] array) {
int max = 0;// 获取最大值
for (int i = 0; i < array.length; i++) {
if (max < array[i]) {
max = array[i];
}
}
int times = 0;// 获取最大值位数
while (max > 0) {
max = max / 10;
times++;
}
List<ArrayList> queue = new ArrayList<ArrayList>();// 多维数组
for (int i = 0; i < 10; i++) {
ArrayList<Object> q = new ArrayList<>();
queue.add(q);
}
for (int i = 0; i < times; i++) {
for (int j = 0; j < array.length; j++) {
// 获取对应的位的值（i为0是个位，1是10位，2是百位）
int x = array[j] % (int) Math.pow(10, i + 1) / (int) Math.pow(10, i);
ArrayList<Integer> q = queue.get(x);
q.add(array[j]);// 把元素添加进对应下标数组
// queue.set(x,q);//待定
}
// 开始收集
int count = 0;
for (int j = 0; j < 10; j++) {
while (queue.get(j).size() > 0) {
ArrayList<Integer> q = queue.get(j);// 拿到每一个数组
array[count] = q.get(0);
q.remove(0);
count++;
}
}
}
}
public static void main(String[] args) {
BasicSort basicSort = new BasicSort();
int[] a = { 136, 2, 6, 8, 9, 2, 8, 11, 23, 56, 34, 90, 89, 29, 145, 209, 320, 78, 3 };
basicSort.sort(a);
for (int n : a) {
System.out.print(" " + n);
}
}
时间复杂度：O(NlogN)
3.递归与穷举
- 二分法查找
