排序算法及比较
冒泡排序
java
/**
* 冒泡排序
* 时间复杂度 是 O(n^2)
* 空间复杂度 是 O(1)
* 稳定
*
*/
private static void bubbleSort(int[] arr) {
/* 标识符 flag true 表示执行过交换操作 否则没有进行交换*/
boolean flag = false;
for (int i = 0; i < arr.length-1; i++) {
/* 每循环一次，都会将最大的数放到最后 */
for (int j = 0; j < arr.length-1-i; j++){
if (arr[j] > arr[j+1]){
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
flag = true;
}
}
System.out.println("第"+(i+1)+"趟排序后："+ Arrays.toString(arr));
if (flag==false){
/* 在一趟排序操作中 没有执行过一次交换操作 则表示数组已经有序*/
break;
}else {
flag = false; /* 重置标识符 进行判断*/
}
}
}选择排序
java
/**
*
*/
private static void selectSort(int[] arr) {
for (int i = 0; i < arr.length-1; i++) {
int minIndex = i;
int min = arr[i];
for (int j = i+1; j <= arr.length-1 ; j++) {
/* 找到最小值 索引 */
if (min>arr[j]){
min = arr[j];
minIndex = j;
}
}
// if (minIndex!=i){
/* 交换 最小的索引*/
// arr[minIndex] = arr[i];
// arr[i] = min;
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
// }
}
}插入排序
java
/**
* 插入排序
*
*/
public static void insertSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int insertVal = arr[i];
int insertIndex =i-1;
while( insertIndex>=0 && insertVal <arr[insertIndex]){
arr[insertIndex +1] =arr[insertIndex];
insertIndex--;
System.out.println(Arrays.toString(arr));
}
arr[insertIndex+1]=insertVal;
}
}快速排序
java
/**
* 快速排序
*/
public static void quickSort(int arr[],int left ,int right){
if(left>=right){
return;
}
int pos = left;
int posVal = arr[left];
int i = left;
int j= right;
while(i != j){
// 先保证右侧找到一个比pos 小 的
while(i<j){
if(arr[j]<posVal){
break;
}
j--;
}
// 从 左侧找一个比基准值大的
while(i<j){
if(arr[i]>posVal){
break;
}
i++;
}
if(i==j){
break;
}else{
/* 交换变量的值 */
int temp = arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
}
if (i==j){
// 相等 则 交换 pos 和 指针的值
arr[pos]= arr[i];
arr[i]= posVal;
}
/* 像左侧递归*/
quickSort(arr,left,i-1);
/* 向右侧递归*/
quickSort(arr,i+1,right);
}堆排序
java
二分查找
java
/**
*
* 二分查找
*/
public static int binarySearch(int[] arr, int target) {
int left = 0;
int right = arr.length - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] > target) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return -1;
}
/** 二分查找基于 递归 */
/**
*
* 二分查找 递归
* @param arr 数组本身
* @param target 查找目标元素
* @param left 左指针
* @param right 右指针
* @return 返回下标
*/
public static int binarySearch(int[] arr, int target ,int left ,int right) {
if (left>right){
return -1;
}
int mid = (left + right) / 2;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] > target) {
right = mid - 1;
return binarySearch(arr,target,left,right);
} else {
left = mid + 1;
return binarySearch(arr,target,left,right);
}
}二叉树 前序遍历 中序遍历 后序遍历
java
public class TreeNode {
public int value;
public boolean visited;
public TreeNode left;
public TreeNode right;
public void visit(){
this.visited=true;
System.out.println("this value ="+this.value);
}
public TreeNode() {
}
public TreeNode(int value) {
this.value = value;
}
public TreeNode(int value, TreeNode left, TreeNode right) {
this.value = value;
this.left = left;
this.right = right;
}
}递归方式 实现 遍历
java
package com.me.demo2;
public class TreeNodeTest {
/* 1
2 3
4 5
*
* */
public static void main(String[] args) {
TreeNode root = new TreeNode(1);
TreeNode left = new TreeNode(2);
TreeNode right = new TreeNode(3);
TreeNode left_1 = new TreeNode(4);
TreeNode right_1 = new TreeNode(5);
left.left=left_1;
left.right=right_1;
root.left=left;
root.right =right;
// search(root);
System.out.println("================");
search3(root);
}
/* 前序遍历*/
public static void search(TreeNode root){
if (root ==null) return;
root.visit();
search(root.left);
search(root.right);
}
/* 中序遍历*/
public static void search2(TreeNode root){
if (root ==null) return;
search2(root.left);
root.visit();
search2(root.right);
}
/* 后序遍历*/
public static void search3(TreeNode root){
if (root ==null) return;
search3(root.left);
search3(root.right);
root.visit();
}
}链表反转
java
public class ListNode {
private int val;
public ListNode next;
public ListNode(int x) { val = x; }
public int getVal() {
return val;
}
public void setVal(int val) {
this.val = val;
}
public ListNode getNext() {
return next;
}
public void setNext(ListNode next) {
this.next = next;
}
@Override
public String toString() {
return "ListNode{" +
"val=" + val +
'}';
}
}使用 栈的方式 先进后出的特性
java
public static ListNode reverseList(ListNode head) {
Stack<ListNode> stack = new Stack();
while (head != null){
stack.push(head);
head = head.getNext();
}
// 栈顶指针
ListNode newHead = stack.pop();
ListNode temp= newHead;
while (!stack.isEmpty()){
ListNode pop = stack.pop();
temp.setNext(pop);
temp = pop;
}
temp.setNext(null);
return newHead;
}java