目录
一、快速排序
1、数组实现
public static void quickSort(int[] arr,int low,int high){
int i,j,temp,t;
if(low>=high){
return;
}
i=low;
j=high;
//temp就是基准位
temp = arr[low];
while (i<j) {
//先看右边，依次往左递减
while (temp<=arr[j]&&i<j) {
j--;
}
//再看左边，依次往右递增
while (temp>=arr[i]&&i<j) {
i++;
}
//如果满足条件则交换
if (i<j) {
t = arr[j];
arr[j] = arr[i];
arr[i] = t;
}
}
//最后将基准为与i和j相等位置的数字交换
arr[low] = arr[i];
arr[i] = temp;
//递归调用左半数组
quickSort(arr, low, j-1);
//递归调用右半数组
quickSort(arr, j+1, high);
}
2、链表实现
public class QuickSortList {
public void quickSort(LNode head, LNode tail) {
if(head == null || head == tail)
return ;
LNode pBase = head;//作为枢纽值的结点
LNode pleft = pBase;//指向当前最后一个比枢纽值小的结点,pBase与pleft之间的结点值始终都比枢纽值小，
LNode pright = pBase.next;//指向比枢纽值大的结点
int temp;
while(pright != tail) {
//作为遍历的pright指针，此时当pright找到了下一个比基准值小的结点，就把pleft右移，将pright的值与pleft交换
if(pright.val < pBase.val) {
pleft = pleft.next;//移向下一个存储小值的位置
if(pright != pleft) {
temp = pleft.val;
pleft.val = pright.val;
pright.val = temp;
}
}
pright = pright.next;
}
temp = pBase.val;
pBase.val = pleft.val;
pleft.val = temp;//原pleft的下一个结点就比枢纽值大
quickSort(pBase, pleft);
quickSort(pleft.next, tail);
}
}
二、归并排序
1、数组实现
public static void merge(int []a,int left,int mid,int right){
int []tmp=new int[a.length];//辅助数组
int p1=left,p2=mid+1,k=left;//p1、p2是检测指针，k是存放指针
while(p1<=mid && p2<=right){
if(a[p1]<=a[p2])
tmp[k++]=a[p1++];
else
tmp[k++]=a[p2++];
}
while(p1<=mid) tmp[k++]=a[p1++];//如果第一个序列未检测完，直接将后面所有元素加到合并的序列中
while(p2<=right) tmp[k++]=a[p2++];//同上
//复制回原素组
for (int i = left; i <=right; i++)
a[i]=tmp[i];
}
public static void mergeSort(int [] a,int start,int end){
if(start<end){//当子序列中只有一个元素时结束递归
int mid=(start+end)/2;//划分子序列
mergeSort(a, start, mid);//对左侧子序列进行递归排序
mergeSort(a, mid+1, end);//对右侧子序列进行递归排序
merge(a, start, mid, end);//合并
}
}
2、链表实现
- 找到中间的拆分链表
//找到中间点，然后分割
public ListNode getMiddle(ListNode head) {
if (head == null) {
return head;
}
//快慢指针
ListNode slow, fast;
slow = fast = head;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
- 合并排好序的两个链表
// 合并排好序的链表
public ListNode merge(ListNode a, ListNode b) {
ListNode dummyHead, curr;
dummyHead = new ListNode(0);
curr = dummyHead;
while (a != null && b != null) {
if (a.val <= b.val) {
curr.next = a;
a = a.next;
} else {
curr.next = b;
b = b.next;
}
curr = curr.next;
}
curr.next = (a == null) ? b : a;
return dummyHead.next;
}
- 单链表的归并
/单链表的归并排序
public ListNode merge_sort(ListNode head) {
if (head == null || head.next == null) {
return head;
}
//得到链表中间的数
ListNode middle = getMiddle(head);
ListNode sHalf = middle.next;
//拆分链表
middle.next = null;
//递归调用
return merge(merge_sort(head), merge_sort(sHalf));
}
三、、堆排序
1、大根堆（用来升序）数组存储
- 首先将无需数组构造成一个大根堆（新插入的数据与其父结点比较）
- 固定一个最大值，将剩余的数重新构造成一个大根堆，重复这样的过程
//堆排序
public static void heapSort(int[] arr) {
//构造大根堆
heapInsert(arr);
int size = arr.length;
while (size > 0) {
//固定最大值
swap(arr, 0, size - 1);
size--;
//构造大根堆
heapify(arr, 0, size);
}
}
//构造大根堆（通过新插入的数上升）
public static void heapInsert(int[] arr) {
for (int i = 1; i < arr.length; i++) {
//当前插入的索引
int currentIndex = i;
//父结点索引
int fatherIndex = (currentIndex - 1) / 2;
//如果当前插入的值大于其父结点的值,则交换值，并且将索引指向父结点
//然后继续和上面的父结点值比较，直到不大于父结点，则退出循环
while (arr[currentIndex] > arr[fatherIndex]) {
//交换当前结点与父结点的值
swap(arr, currentIndex, fatherIndex);
//将当前索引指向父索引
currentIndex = fatherIndex;
//重新计算当前索引的父索引
fatherIndex = (currentIndex - 1) / 2;
}
}
}
//将剩余的数构造成大根堆（通过顶端的数下降）
public static void heapify(int[] arr, int index, int size) {
int left = 2 * index + 1;
int right = 2 * index + 2;
while (left < size) {
int largestIndex;
//判断孩子中较大的值的索引（要确保右孩子在size范围之内）
if (arr[left] < arr[right] && right < size) {
largestIndex = right;
} else {
largestIndex = left;
}
//比较父结点的值与孩子中较大的值，并确定最大值的索引
if (arr[index] > arr[largestIndex]) {
largestIndex = index;
}
//如果父结点索引是最大值的索引，那已经是大根堆了，则退出循环
if (index == largestIndex) {
break;
}
//父结点不是最大值，与孩子中较大的值交换
swap(arr, largestIndex, index);
//将索引指向孩子中较大的值的索引
index = largestIndex;
//重新计算交换之后的孩子的索引
left = 2 * index + 1;
right = 2 * index + 2;
}
}
//交换数组中两个元素的值
public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
2、小根堆（用来降序）数组存储
四、字典树(Trie)的实现
//字典树的java实现
public class Trie {
private TrieNode root;
public Trie() {
root = new TrieNode();
root.wordEnd = false;
}
public void insert(String word) {
TrieNode node = root;
for (int i = 0; i < word.length(); i++) {
Character c = new Character(word.charAt(i));
if (!node.childdren.containsKey(c)) {
node.childdren.put(c, new TrieNode());
}
node = node.childdren.get(c);
}
node.wordEnd = true;
}
public boolean search(String word) {
TrieNode node = root;
boolean found = true;
for (int i = 0; i < word.length(); i++) {
Character c = new Character(word.charAt(i));
if (!node.childdren.containsKey(c)) {
return false;
}
node = node.childdren.get(c);
}
return found && node.wordEnd;
}
public boolean startsWith(String prefix) {
TrieNode node = root;
boolean found = true;
for (int i = 0; i < prefix.length(); i++) {
Character c = new Character(prefix.charAt(i));
if (!node.childdren.containsKey(c)) {
return false;
}
node = node.childdren.get(c);
}
return found;
}
}
public class TrieNode {
Map<Character, TrieNode> childdren;
boolean wordEnd;
public TrieNode() {
childdren = new HashMap<Character, TrieNode>();
wordEnd = false;
}
}
五、树的非递归遍历
1、前序
//先序遍历非递归
public static void preOrder2(TreeNode root) {
if(root==null) return;
ArrayList<Integer> ans=new ArrayList();
Stack<TreeNode > stack=new Stack<>();
while(root!=null || !stack.empty()){
while(root!=null){
ans.add(root.val);
stack.push(root);
root=root.left;
}
//root的左为空就去pop这个root
if(!stack.empty()){
root=stack.pop();//right为空就去找栈里面的顶端节点
root=root.right;
}
}
}
2、中序
//中序遍历非递归
public static void inOrder2(TreeNode root) {
if(root==null) return;
ArrayList<Integer> ans=new ArrayList();
Stack<TreeNode > stack=new Stack<>();
while(root!=null || !stack.empty()){
while(root!=null){
stack.push(root);
root=root.left;
}
//root的左为空就去pop这个root
if(!stack.empty()){
root=stack.pop();
ans.add(root.val);
root=root.right;
}
}
}
3、后序
//后续遍历非递归
public static void postOrder2(TreeNode root) {
if(root==null) return;
ArrayList<Integer> ans=new ArrayList();
Stack<TreeNode > stack=new Stack<>();
Stack<Integer> tag=new Stack<>();
while(root!=null || !stack.empty()){
while(root!=null){
stack.push(root);
tag.push(0);
root=root.left;
}
//root的左为空就去pop这个root
if(!stack.empty() && tag.peek()==1){//tag为1说明访问过这个根的右节点了
tag.pop();
ans.add(stack.pop().val);
}
if(!stack.empty()){
tag.pop();
tag.push(1);
root=stack.peek();//此时的根节点
root=root.right;
}
}
}
六、其他常考代码
1、求二叉树的最大深度？
public int getHeight(TreeNode root) {
if (root == null) {
return 0;
}
int leftHeight = getHeight(root.getLeft());
int rightHeight = getHeight(root.getRight());
return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}
2、判断是否为平衡二叉树？
法一：每次都要算一遍高度，不好。
public class Solution {
public boolean IsBalanced_Solution(TreeNode root) {
if( root == null) { //一棵空树就是平衡二叉树
return true;
}
if( Math.abs(getDepth(root.left) - getDepth(root.right)) <= 1 ) {
//满足左右子树高度差小于等于1,那就接着判断左右子树是不是二叉树
return (IsBalanced_Solution(root.left) && IsBalanced_Solution(root.right));
} else {
//不满足左右子树高度差小于等于1,那这棵树肯定不是平衡二叉树啦
return false;
}
}
public int getDepth(TreeNode root) {
if( root == null ) return 0;
int left = getDepth(root.left);
int right = getDepth(root.right);
return ( left > right ? left : right ) + 1;//树的高度怎么计算就不用我讲了吧
}
}
法二，从下往上走，算出高度后可以继续使用这个高度，比较好。
public class Solution {
private boolean isBalanced = false;//最后的返回值
public boolean IsBalanced_Solution(TreeNode root) {
getDepth(root);
return isBalanced;
}
public int getDepth(TreeNode root) {
if(root == null) {
isBalanced = true;
return 0;
}
int left = getDepth(root.left);//左子树
int right = getDepth(root.right);//右子树
int depth = (left > right ? left : right) + 1;
if(Math.abs(left - right) <= 1) {
isBalanced = true;
} else {
isBalanced = false;
}
return depth;//下层的深度，上层可以接着用免得再遍历
}
}