0.总结
常见算法复杂度.jpg
O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n)，logn的底数为2
1.归并排序
package DailyPractice;
import java.util.*;
public class Test1 {
/**
* 归并排序的思路：先将数组的左边和右边分开排完序之后再合并，
* 其中左边和右边的排序也是递归用这种先分开排序再合并的思想。
* 步骤：
* 1.MergeSort左边
* 2.MergeSort右边
* 3.Merge两边（两边的头先开始比较，把较小的放进临时数组，
* 然后将左边剩余的移进数组，再将右边剩余的移进数组，最后将临时数组覆盖特定部分的旧数组）
* @param args
*/
public static void main(String[] args) {
int[] a = new int[]{2,45,8,147,312,42,478};
MyMergeSort(a,0,a.length-1);
System.out.println(Arrays.toString(a));
}
private static void MyMergeSort(int[] a, int low, int high) {
int middle = (high+low)/2;
if (low<high){
MyMergeSort(a,low,middle);
MyMergeSort(a,middle+1,high);
MyMerge(a,low,middle,high);
}
}
private static void MyMerge(int[] a, int low, int middle, int high) {
int[] temp = new int[high-low+1];
int i = low;
int j = middle+1;
int k = 0;
//把较小的先移进数组
while(i<=middle && j <=high){
if (a[i]<a[j]){
temp[k++] = a[i++];
}else {
temp[k++] = a[j++];
}
}
while(i<=middle){
temp[k++] = a[i++];
}
while (j<=high){
temp[k++] = a[j++];
}
//将新数组覆盖旧数组
for (int l = 0; l < temp.length; l++) {
a[l+low] = temp[l];
}
}
}
2.快速排序
package DailyPractice;
import java.util.*;
public class Test1 {
/**
* 快速排序的思路：首先选择一个锚点，将比他小的数移到他的左边，比他大的数移到右边，
* 然后用同样的思想对左边和右边进行排序
* @param args
*/
public static void main(String[] args) {
int[] a = new int[]{2,45,8,147,312,42,478};
MyQuickSort(a,0,a.length-1);
System.out.println(Arrays.toString(a));
}
private static void MyQuickSort(int[] a, int low, int high) {
if (low>high)return;
int pivot = a[low];
int i = low;
int j = high;
while (i!=j){
//记得要先从右边先开始
while (a[j]>=pivot && i<j){
j--;
}
while (a[i]<=pivot && i<j){
i++;
}
if (i<j){
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
a[low] = a[i];
a[i] = pivot;
MyQuickSort(a, low, i-1);
MyQuickSort(a,i+1,high);
}
}
3.选择排序
package DailyPractice;
import java.util.*;
public class Test1 {
/**
* 选择排序的思路：首先第一次遍历数组找出最小的数，放在最左边，
* 第二次遍历找出第二小的数放在第二个位置，依次遍历直到数组排完。
* 其中的方法是：定一个索引，依次遍历数组，如果比他小的就将索引换为该数的下标，最后如果
* 索引和一开始的下标不一样就替换。
* @param args
*/
public static void main(String[] args) {
int[] a = new int[]{2,45,8,147,312,42,478};
MySelectionSort(a);
System.out.println(Arrays.toString(a));
}
private static void MySelectionSort(int[] a) {
for (int i = 0; i < a.length; i++) {
int minIndex = i;
for (int j = i; j < a.length; j++) {
if (a[j]<a[minIndex]){
minIndex = j;
}
}
if (minIndex != i){
int temp = a[i];
a[i] = a[minIndex];
a[minIndex] = temp;
}
}
}
}
4.冒泡排序
package DailyPractice.Sort;
public class BubbleSort {
/**
* 冒泡排序的思路：多次遍历数组，比较两两相邻的数，如果左边的比右边的大就交换，
* 直到数组排完序为止。（遍历的次数为(length-1)+(length-2)+(length-3)+...+2+1）
* @param args
*/
public static void main(String[] args) {
int[] arrays = {54,87,2541,7,5462,254};
int[] res = bubblesort(arrays);
for (int i = 0; i < res.length; i++) {
System.out.println(res[i]);
}
}
private static int[] bubblesort(int[] arrays) {
for (int i = 0; i < arrays.length-1; i++) {
for (int j = 0; j < arrays.length - i - 1; j++) {
if (arrays[j] > arrays[j+1]){
int temp = arrays[j];
arrays[j] = arrays[j+1];
arrays[j+1] = temp;
}
}
}
return arrays;
}
}
附：
二分查找，其中的关键点在于mid的选择是用了low+(high-low)/2，而不是(high+low)/2。
package DailyPractice.Search;
public class BinarySearch {
public static void main(String[] args) {
int[] arr = new int[]{1,5,8,9,10,45,98};
System.out.println(MyBinarySearch(arr,0,arr.length-1,100));
}
private static int MyBinarySearch(int[] arr, int low, int high, int target) {
if (low>high)return -1;
int mid = low+(high-low)/2;
if (arr[mid] == target){
return mid;
}
if (arr[mid]<target){
return MyBinarySearch(arr,mid+1,high,target);
}
else {
return MyBinarySearch(arr,low,mid-1,target);
}
}
}
5.算法笔记
- A序列中每个元素离最终的位置都不远，则应使用直接插入排序。
- 快排在序列有序时时间复杂度最差，为O(n²)，在序列有序时时间复杂度最好，为O(nlog₂n)。
- 叶子结点数等于度为2的结点数加1，结点总数等于叶子总数加上度为1的结点数，再加上度为2的结点数。
网友评论