简述稳定排序和非稳定排序的区别
稳定排序：排序前后两个相等的数相对位置不变，则算法稳定 非稳定排序：排序前后两个相等的数相对位置发生了变化，则算法不稳定
堆排序
什么是最大堆和最小堆？
最大（小）堆是指在树中，存在一个结点而且该结点有儿子结点，该结点的data域值都不小于（大于）其儿子结点的data域值，并且它是一个完全二叉树（不是满二叉树）
堆排序
import java.util.*; public class Main { // static int[] a = { 9, 5, 3, 2, 2, 2, 6, 1, 0 }; static int[] a = { 3, 2, 6, 1, 0 }; void downAdjust(int[] arr, int parentIndex, int length) { // temp保存父节点的值，用于最后赋值 int temp = arr[parentIndex]; int childrenIndex = 2 * parentIndex + 1; while (childrenIndex < length) { // 如果有右孩子，且右孩子大于左孩子的值，则定位到右孩子 // 这里其实是比较左、右子树的大小，选择更大的 if (childrenIndex + 1 < length && arr[childrenIndex + 1] > arr[childrenIndex]) { childrenIndex++; } // 如果父节点大于任何一个孩子得值，则直接跳出 if (temp >= arr[childrenIndex]) { break; } // 当左、右子树比父节点更大，进行交换 arr[parentIndex] = arr[childrenIndex]; parentIndex = childrenIndex; childrenIndex = 2 * childrenIndex + 1; } arr[parentIndex] = temp; } void swap(int a, int b) { int tmp = a; a = b; b = tmp; } /** * 堆排序(升序) * * @param {array} arr 待调整的堆 */ int[] heapSort(int[] arr) { // 把无序数组构建成最大堆, 这里-2,是因为从索引0开始、另外就是叶子节点【最后一层是不需要堆化的】 for (int i = (arr.length - 2) / 2; i >= 0; i--) {// (arr.length-2)/2:最后一个父节点 downAdjust(arr, i, arr.length); } // 循环删除堆顶元素，并且移到集合尾部，调整堆产生新的堆顶 for (int i = arr.length - 1; i > 0; i--) { // 交换最后一个元素与第一个元素 // swap(arr[0], arr[i]); int temp = arr[i]; arr[i] = arr[0]; arr[0] = temp; // swap(arr[0],arr[i])错误，无法交换 // 下沉调整最大堆 // downAdjust(arr, 0, i - 1);// 1 0 2 3 6 i-1的话 i==2时，无法重新更细为最大堆 downAdjust(arr, 0, i);// 0 1 2 3 6 } return arr; } public static void main(String agrs[]) { Main ma = new Main(); ma.heapSort(a); for (int x : a) { System.out.print(x + " "); } } }
输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。
class Solution { public int[] getLeastNumbers(int[] arr, int k) { if(arr.length==0 ||k==0){ return new int[0]; } PriorityQueue<Integer>que =new PriorityQueue<Integer>(new acomparator());//PriorityQueue默认最小堆，这里改为最大堆 for(int a:arr){ if(que.size()<k) que.offer(a); else if(a<que.peek()){ que.poll(); que.offer(a); } } int n =que.size(); int []b =new int[n]; // for(int i=0;i<que.size();i++) {//这里不能用que.size()，因为que.size()在变化 // b[i] =que.poll(); // } for(int i=0;i<n;i++) { b[i] =que.poll(); } return b; } } class acomparator implements Comparator<Integer>{ public int compare(Integer a,Integer b){ return b-a; } }
最大的K个数，需要修改如下：
PriorityQueue<Integer> que = new PriorityQueue<Integer>();
else if (a > que.peek()) {
que.poll();
que.offer(a);
}
归并排序
把两个有序的序列归并成一个序列
当小组只有一个数据时，可以认为这个小组组内已经达到了有序，然后再合并相邻的二个小组就可以了
import java.util.*; public class Main { int[] a = new int[5]; int[] b = new int[5]; int ans; void merge(int[] a, int l, int r) { if (l == r) return; int m = (l + r) >> 1; merge(a, l, m); merge(a, m + 1, r); int i = l, j = m + 1, k = l; while (i <= m && j <= r) { if (a[i] <= a[j]) b[k++] = a[i++]; else { b[k++] = a[j++]; ans += (m - i + 1);//逆序对数目 } } while (i <= m) b[k++] = a[i++]; while (j <= r) b[k++] = a[j++]; for (int p = l; p <= r; p++) a[p] = b[p]; } public static void main(String args[]) { Main ma = new Main(); Scanner input = new Scanner(System.in); for (int i = 0; i < 5; i++) { ma.a[i] = input.nextInt(); } ma.merge(ma.a, 0, 4); for (int i = 0; i < 5; i++) { System.out.print(ma.a[i] + " "); } System.out.println(" "); System.out.println(ma.ans); } }
链表归并
import java.util.*; import javax.swing.plaf.metal.MetalRadioButtonUI; public class Main { static class Node { int val; Node next; public Node(int val) { this.val = val; } } static Node head; public void addfirst(int val) { Node node = new Node(val); if (head == null) { head = node; return; } node.next = head; head = node; } public void addlast(int val) { Node px = head; Node node = new Node(val); if (head == null) { head = node; return; } while (px.next != null) { px = px.next; } px.next = node; } public void printl(Node p) { Node px = p; while (px != null) { System.out.print(px.val + " "); px = px.next; } System.out.println(" "); } public Node bingsort(Node head) { if (head == null || head.next == null) return head; Node mid = getmid(head); Node ri = mid.next; mid.next = null; return merge(bingsort(head), bingsort(ri)); } public Node getmid(Node head) { if (head == null || head.next == null) return head; Node sl = head, fa = head; while (fa.next != null && fa.next.next != null) { sl = sl.next; fa = fa.next.next; } return sl; } public Node merge(Node head1, Node head2) { Node p1 = head1, p2 = head2, head; if (head1.val <= head2.val) { head = head1; p1 = p1.next; } else { head = head2; p2 = p2.next; } Node p = head; while (p1 != null && p2 != null) { if (p1.val <= p2.val) { p.next = p1; p1 = p1.next; p = p.next; } else { p.next = p2; p2 = p2.next; p = p.next; } } if (p1 != null) p.next = p1; if (p2 != null) p.next = p2; return head; } public static void main(String[] args) { Main ma = new Main(); ma.addlast(1); ma.addlast(7); ma.addlast(10); ma.addlast(19); ma.addlast(1); ma.addlast(7); ma.addlast(100); ma.addlast(1999); ma.printl(head); ma.bingsort(head); ma.printl(head); } }
快速排序
import java.util.*; public class Main { private static void sort(int[] arr, int l, int r) { int i = l; int j = r; if (l < r) { while (l < r) { while (l < r && arr[r] >= arr[l]) { r--; } int tmp = arr[l]; arr[l] = arr[r]; arr[r] = tmp; while (l < r && arr[l] <= arr[r]) { l++; } tmp = arr[l]; arr[l] = arr[r]; arr[r] = tmp; } sort(arr, i, l - 1);// 递归左边，此时l=5 sort(arr, l + 1, j);// 递归右边，此时l=5 } } public static void main(String agrs[]) { int[] arr = { -5, 1, 1, 8, 7, 300, 7, 0, 0, 6 }; sort(arr, 0, arr.length - 1); for (int i : arr) { System.out.print(i + " "); } } }
链表快排 https://www.cnblogs.com/morethink/p/8452914.html
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode sortList(ListNode head) { quicksort(head,null); return head; } public void quicksort(ListNode head,ListNode end){ if(head!=end){//注意边界 ListNode node =partion(head,end); quicksort(head,node); quicksort(node.next,end); } } public ListNode partion(ListNode head,ListNode end){//p1前面的都小于key,p1,p2之间的都大于key,p2=end时交换p1 head,p1就是partion ListNode p1 =head,p2 =head.next; while(p2!=end){ if(p2.val<head.val){ p1 = p1.next; int tmp = p1.val; p1.val =p2.val; p2.val =tmp; } p2 =p2.next; } if(p1!=head){//已经有序不需要交换 int tmp = p1.val; p1.val =head.val; head.val =tmp; } return p1; } }
剑指 Offer 40. 最小的k个数
输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。
class Solution { public int[] getLeastNumbers(int[] arr, int k) { if (k == 0 || arr.length == 0) { return new int[0]; } // 最后一个参数表示我们要找的是下标为k-1的数 return quickSearch(arr, 0, arr.length - 1, k - 1); } private int[] quickSearch(int[] nums, int lo, int hi, int k) { // 每快排切分1次，找到排序后下标为j的元素，如果j恰好等于k就返回j以及j左边所有的数； int j = partition(nums, lo, hi); if (j == k) { return Arrays.copyOfRange(nums,0, j + 1); } // 否则根据下标j与k的大小关系来决定继续切分左段还是右段。 return j > k? quickSearch(nums, lo, j - 1, k): quickSearch(nums, j + 1, hi, k); } private int partition(int[] arr, int l, int r) { int i = l; int j = r; if (l < r) { while (l < r) { while (l < r && arr[r] >= arr[l]) { r--; } int tmp = arr[l]; arr[l] = arr[r]; arr[r] = tmp; while (l < r && arr[l] <= arr[r]) { l++; } tmp = arr[l]; arr[l] = arr[r]; arr[r] = tmp; } } return r; //arr[r]左边不大于他，右边不小于他 } }
