快速排序

  • 利用分治，选择一个标兵使左右区间分别满足<=和>=标兵，递归子区间直到区间长度为1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static void quick_sort(int[] nums, int l, int r) {
	if(l>=r) return;
	int m = nums[l+r>>1],left = l-1,right = r+1;  //注意此处的标兵取值 必须与下面递归的标兵相反 l - right
	while (left<right){
		do left++; while (nums[left] < m);
		do right--; while (nums[right] > m);
		if(left<right) {
			int tmp = nums[left];
			nums[left] = nums[right];
			nums[right] = tmp;
		}
	}
	quick_sort(nums,l,right);
	quick_sort(nums,right+1, r);
}

持续优化：1.类似荷兰旗问题，当所求值与标兵相同时 不参与下一次递归
2.随机标兵 表现会比固定标兵的效果好

归并排序

  • 也是分治，先递归，再合并。每次递归二分直到区间长度为1，然后和并返回有序数组
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static void merge_sort(int[] nums,int l,int r){
    if(l>=r) return;
    int mid = l+r>>1;
    merge_sort(nums,l,mid);
    merge_sort(nums,mid+1,r);
    int[] tmp = new int[r-l+1];
    int k=0,left=l,right=mid+1;
    while(left<=mid && right<=r){
        if(nums[left]<nums[right]) tmp[k++] = nums[left++];
        else tmp[k++] = nums[right++];
    }
    while(left<=mid) tmp[k++] = nums[left++];
    while(right<=r) tmp[k++] = nums[right++];
    for(int n:tmp) nums[l++] = n;
}

快排重在切分区间，归并重在合并区间

java中的复合排序

  • 对新建的结构体使用继承 Comparable接口 实习排序对比
  • 对于普通的对比，使用 new Comparator类
  • 对于复合对比 使用多层if-else嵌套
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
// 对结构体排序
class Node implements Comparable<Node>{
	int x;
	int y;
	public Node(int x, int y) {
		this.x = x;
		this.y = y;
	}
	// 先按 x 排序 再按 y排序
	@Override
	public int compareTo(Node other) {
		if(other.x > this.x) return 1;
		else if(other.x < this.x) return -1;
		else {
			return other.y - this.y;
		}
	}
}

public class NodeSort {
	public static void main(String[] args) {
		List<Node> list = new ArrayList<>();
		list.sort(new Comparator<Node>() {
			@Override
			public int compare(Node o1, Node o2) {
				return o1.x-o2.x;
			}
		});
	}
}

java中的优先队列（堆排序）

  • 堆排序默认维护n大小的最值（默认最大值 小顶堆）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
import java.util.Comparator;
import java.util.PriorityQueue;

public class heapSort {
  public static void main(String[] args) {
    int[] arr = {1,5,3,2,7,6,4,9,8};
    int k = 3;      // 队的size
    PriorityQueue<Integer> q1 = new PriorityQueue<>(k);   // 维护小顶堆
    PriorityQueue<Integer> q = new PriorityQueue<>(k, new Comparator<Integer>() {   // 维护大顶堆
      @Override
      public int compare(Integer o1, Integer o2) {
        return o2-o1;
      }
    });
    for (int i = 0; i <9 ; i++) {
      if(q.size() < k) q.add(arr[i]);
      else if(arr[i] < q.peek()){
        q.poll();
        q.add(arr[i]);
      }
    }
    for (int i = 0; i <k ; i++) {
      System.out.println(q.poll());
    }
  }
}