几个常见的排序
选择排序：
for (int i = n - 1; i >= 0; i--)
{
int idx = 0;
for (int j = 0; j <= i; j ++)
{
if (n[j] > n[idx])
idx = j;
}
swap(n[idx], n[i]);
}
插入排序
import java.io.*;
import java.util.Scanner;
class Main{
static int n;
public static void main(String[] args){
Scanner scan = new Scanner(System.in);
n = scan.nextInt();
int []sort = new int[n];
for (int i = 0; i < n; i++)
sort[i] = scan.nextInt();
for (int i = 1; i < n; i ++){
for (int j = i - 1; j >= 0 && sort[j] > sort[j + 1]; j--){
int t = sort[j]; sort[j] = sort[j + 1]; sort[j + 1] = t;
}
}
for (int i = 0; i < n; i ++)
System.out.print(sort[i] + " ");
return;
}
}
关键点在于搞清楚一点：遍历完i, j指针作为临界点的意义 。
ij指针移动完后：
1. j == i or j = i - 1
2. q[l, i - 1]<=基准值， q[i， r]>=x
4. q[j + 1, r]>= x ; q[l, j] <= x
所以递归区间是 [l, i - 1](<=x) or [i , r](>=x) 基准为q[l]
[l, j](<=x)or [j + 1, r](>=x)
具体选择哪种情况，要看基准值x
当x == q[l]或者q[l + r >> 1], 选择区间[l, j] and [j + 1,r](因为以q[l]/q[l + r >> 1]为基准的时候，即使数组是递增的，j也不会最终停在r的位置。j停在右边的条件是j–只执行了一次，但x为基准，i指针会卡一次，j无论会不会卡都会至少执行两次)
当x == q[r]或者q[l + r + 1 >> 1], 选择区间[l, i - 1] and [i, r](同理)
public static void quickSort(int l, int r, int[] q){
if (l >= r) return;
int i = l - 1, j = r + 1;
int x = q[r];
while (i < j){
do i ++; while(q[i] < x);
do j --; while(q[j] > x);
if (i < j) {
int t = q[i];
q[i] = q[j];
q[j] = t;
}
}
quickSort(l, i - 1, q);
quickSort(i, r, q);
}
42. 有效的字母异位词
這道題手寫快排。 把String轉成StringBuilder做的。。轉成char[]好做一些（可以使用Arrays.sort）。
class Solution {
public boolean isAnagram(String s, String t) {
//把两个字符串快排 如果equals是一样的
int n1 = s.length(), n2 = t.length();
//轉換成StringBuilder，有replace函數，可以更換字符串
StringBuilder sb = new StringBuilder(s);
StringBuilder tb = new StringBuilder(t);
//轉成String
t = quickSort(0, n2 - 1, tb).toString();
s = quickSort(0, n1 - 1, sb).toString();
for(int i = 0; i < n1; i ++)
System.out.print(s.charAt(i));
System.out.println();
for(int i = 0; i < n2; i ++)
System.out.print(t.charAt(i));
if (s.equals(t)){
return true;
}
return false;
}
public StringBuilder quickSort(int l, int r, StringBuilder sb){
if (l >= r) return sb;
int i = l - 1, j = r + 1;
int mid = (i + j) / 2;
while(i < j){
do i ++; while(Integer.valueOf(sb.charAt(i)).intValue() < Integer.valueOf(sb.charAt(mid)).intValue());
do j --; while(Integer.valueOf(sb.charAt(j)).intValue() > Integer.valueOf(sb.charAt(mid)).intValue());
if (i < j){
String t = new String();
t = sb.substring(j, j + 1);
sb.replace(j, j + 1, sb.substring(i, i + 1));
sb.replace(i, i + 1, t);
}
}
sb = quickSort(l, j,sb);
sb = quickSort(j + 1, r, sb);
return sb;
}
}
或者使用hashMap
class Solution {
public boolean isAnagram(String s, String t) {
//使用hashMap,記錄每個字符和出現次數
char[] charS = s.toCharArray();
char[] charT = t.toCharArray();
HashMap<Character, Integer> hash1 = new HashMap<>();
HashMap<Character, Integer> hash2 = new HashMap<>();
for (int i = 0; i < charS.length; i ++)
hash1.put(charS[i], hash1.getOrDefault(charS[i], 0) + 1);
for (int i = 0; i < charT.length; i ++)
hash2.put(charT[i], hash2.getOrDefault(charT[i], 0) + 1);
return hash1.equals(hash2);
}
}`
toArray()不能把Integer拆箱成int有點死亡
class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
//由於每個元素是唯一的 使用HashSet，把第一個數組記入hashset，如果第二個數組的元素在hashset出現過，
//加入到arrayList， 并且把它從set中刪掉，這樣結果就是唯一的了
HashSet<Integer> hash = new HashSet<>();
for (int i = 0; i < nums1.length; i ++)
hash.add(nums1[i]);
ArrayList<Integer> list = new ArrayList<>();
for (int i = 0; i < nums2.length; i ++)
{
if (hash.contains(nums2[i])){
list.add(nums2[i]);
hash.remove(nums2[i]);
}
}
int[] res = new int[list.size()];
int idx = 0;
for (int num : list)
res[idx ++] = num;
//List轉int[]
return res;
}
}
class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
//由於每個元素是唯一的 使用HashSet，把第一個數組記入hashset，如果第二個數組的元素在hashset出現過，
//加入到arrayList， 并且把它從set中刪掉，這樣結果就是唯一的了
HashSet<Integer> hash = new HashSet<>();
for (int i = 0; i < nums1.length; i ++)
hash.add(nums1[i]);
ArrayList<Integer> list = new ArrayList<>();
for (int i = 0; i < nums2.length; i ++)
{
if (hash.contains(nums2[i])){
list.add(nums2[i]);
hash.remove(nums2[i]);
}
}
return list.stream().mapToInt(Integer::valueOf).toArray();
}
}
class Solution {
public int[] intersect(int[] nums1, int[] nums2) {
//使用哈希表
HashMap<Integer, Integer> hash = new HashMap<>();
ArrayList<Integer> list = new ArrayList<>();
for (int i = 0; i < nums1.length; i ++){
hash.put(nums1[i], hash.getOrDefault(nums1[i], 0) + 1);
}
for (int i = 0; i < nums2.length; i ++){
if (hash.getOrDefault(nums2[i], 0) >= 1){
hash.put(nums2[i], hash.get(nums2[i]) - 1);
list.add(nums2[i]);
}
}
int[] num = new int[list.size()];
int i = 0;
for (int number : list)
{
System.out.println(number);
num[i++] = number;
}
return num;
}
}
归并排序
归并排序
public static void mergeSort(int l, int r, int[] q, int[] t){
if (l >= r) return;
int k = 0;
int i = l, mid = (l + r) / 2, j = mid + 1;
mergeSort(l, mid, q, t);
mergeSort(j, r, q, t);
while(i <= mid && j <= r){
if (q[i] <= q[j])t[k ++] = q[i ++];
else t[k ++] = q[j ++];
}
while(i <= mid)t[k ++] = q[i++];
while(j <= r) t[k ++] = q[j ++];
for (i = l, j = 0; i <= r; i ++)
{
q[i] = t[j ++];
}
}
归并需要从小区间到大区间排序，因为他要求前后两个区间中的每个区间是**有序**的
解题思路
类似于归并排序（不需要分治）的思路解法。
代码
/**
* 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 mergeTwoLists(ListNode l1, ListNode l2) {
//合并有序的两个链表 ，类似于归并排序的思路
ListNode cur1 = l1, cur2 = l2;
ListNode head = new ListNode();
ListNode res = head;
while(cur1 != null && cur2 != null){
if (cur1.val <= cur2.val) {
res.next = new ListNode(cur1.val);
res = res.next;
cur1 = cur1.next;
}
else{
res.next = new ListNode(cur2.val);
res = res.next;
cur2 = cur2.next;
}
}
while(cur1 != null){
res.next = new ListNode(cur1.val);
res = res.next;
cur1 = cur1.next;
}
while(cur2 != null){
res.next = new ListNode(cur2.val);
res = res.next;
cur2 = cur2.next;
}
return head.next;
}
}
