牛客网数据结构3
牛客网 3
排序的稳定性
相同的值会不会因为排序算法而被打乱次序。
三种O(n2) ：冒泡排序和插入排序可以做到，而选择排序做不到！
O(nlogn) ：归并排序可以做到，快排做不到稳定性！堆排序也做不到稳定性！
在保证稳定性的情况下。可以做到两种不同维度的比较的排序。就是说排序之前的信息可能对用户很重要，不希望排序打乱。
工程中的综合排序
1、如果数组类型时基础类型：快排
2、如果数组时自己定义的类型：归并排序
3、如果数组量过小：插入排序。 插排的常数项极低。
总体的是相互结合的，在快排和归并最后剩下60个元素时，就会选择使用插入排序。
前两个的选择是从排序稳定性出发的。
比较器
public static class Student {
public String name;
public int id;
public int age;
public Student(String name, int id, int age) {
this.name = name;
this.id = id;
this.age = age;
}
}
public static class IdAscendingComparator implements Comparator<Student> {
@Override
public int compare(Student o1, Student o2) {
return o1.id - o2.id;
}
}
public static class IdDescendingComparator implements Comparator<Student> {
@Override
public int compare(Student o1, Student o2) {
return o2.id - o1.id;
}
}
public static class AgeAscendingComparator implements Comparator<Student> {
@Override
public int compare(Student o1, Student o2) {
return o1.age - o2.age;
}
}
public static class AgeDescendingComparator implements Comparator<Student> {
@Override
public int compare(Student o1, Student o2) {
return o2.age - o1.age;
}
}
compare 方法可以自定义比较的排序，他的返回值：1、负数，o1小于o2。 2、正数，o1大于o2。那么什么时候返回正数，什么时候返回负数是自己定义的。
使用方法：
public static void printStudents(Student[] students) {
for (Student student : students) {
System.out.println("Name : " + student.name + ", Id : " + student.id + ", Age : " + student.age);
}
System.out.println("===========================");
}
public static void main(String[] args) {
Student student1 = new Student("A", 1, 23);
Student student2 = new Student("B", 2, 21);
Student student3 = new Student("C", 3, 22);
Student[] students = new Student[] { student3, student2, student1 };
printStudents(students);
//在sort中多写一个比较器的参数！！！！
Arrays.sort(students, new IdAscendingComparator());
printStudents(students);
Arrays.sort(students, new IdDescendingComparator());
printStudents(students);
Arrays.sort(students, new AgeAscendingComparator());
printStudents(students);
Arrays.sort(students, new AgeDescendingComparator());
printStudents(students);
}
不基于比较的排序
桶排序，基数排序，计数排序。
与样本的实际数据状况很有关系，所以实际中不常使用。
时间与空间复杂度都是O(n)。
稳定的。
public class MaxGap {
public static int maxGap(int[] nums) {
if(nums.length < 2) {
return 0;
}
int maxnumber = Integer.MAX_VALUE;
int minnumber = Integer.MIN_VALUE;
int len = nums.length;
//计算出最大值最小值来做判断
for(int i = 0; i < len; i++) {
maxnumber = Math.max(maxnumber, nums[i]);
minnumber = Math.min(minnumber, nums[i]);
}
//判断最大最小值，如果相同就直接返回0就好
if(maxnumber == minnumber) return 0;
//最大最小值存在并且不相同
boolean[] excit = new boolean[len];
int[] mins = new int[len + 1];
int[] maxs = new int[len + 1];
//遍历数组中每个元素，并且完成装桶
for(int i = 0; i < len; i++) {
int where = bucket(nums[i], len, minnumber, maxnumber);
mins[where] = excit[where] ? Math.min(mins[where], nums[i]) : nums[i];
maxs[where] = excit[where] ? Math.max(maxs[where], nums[i]) : nums[i];
excit[where] = true;
}
//装完后就可以计算，最大的差值一定出现在相邻的桶中
int res = 0;
int lastMax = maxs[0];
int i = 1;
for(; i < len; i++) {
if(excit[i]) {
res = Math.min(res, mins[i] - lastMax);
lastMax = maxs[i];
}
}
return res;
}
//判断放在那个桶中
public static int bucket(long num, long len, long min, long max) {
return (int) ((num - min) * len / (max - min));
}
}
用数组结构实现大小固定的队列
public class ArrayToQueue {
//数组表示队列
public static int size;
public static int head = 0;
public static int tail = 0;
public static Object[] array;
//入队
public static void enqueue(Object obj) {
if(array.length ==size) {
return;
}else {
if(head == tail) {
array[tail] = obj;
if(tail == size) tail = 0;
else tail++;
}
}
}
//出队
public static void dequeue() {
if(array.length <0)
return;
if(head == size) head = 0;
else head ++;
}
}
用数组结构实现大小固定的栈
public class ArrayToStack {
//用固定长度数组实现栈
//固定大小
public static int size;
//确定头指针
public static int index;
//确定数组
public static Object[] array;
//入栈
public static void push(Object obj) {
if(index <= size) {
//放入元素后，需要把index++
array[index++] = obj;
}
}
//出栈
public static void pop() {
if(index >= 1) {
index --;
}
}
}
public class getMinStack {
//可返回最小值的自定义栈
public static Stack<Integer> stack;
public static Stack<Integer> help;
//入栈
public static void push(int obj) {
stack.push(obj);
//最小值压入help栈
if(help.isEmpty()) help.push(obj);
else {
help.push((help.peek() < obj) ? help.peek() : obj);
}
}
//出栈
public static void pop() {
stack.pop();
help.pop();
}
//获得最小值
public static int getmin() {
return help.peek();
}
}
用队列实现栈
public class QueueToStack {
//用队列表示栈
//建立两个队列
public static Queue<Object> queuepush;
public static Queue<Object> queuepop;
//建立一个临时索引
public static Queue<Object> tmp = queuepush;
//出栈
public static Object Spop() {
if(queuepush.isEmpty()) {
return null;
}
while(queuepush.size() > 1) {
queuepop.add(queuepush.poll());
}
//交换索引，这就能保证每次入栈的索引都是push！
tmp = queuepop;
queuepop = queuepush;
queuepush = tmp;
//pop中剩下的一个用来返回！
return queuepop.poll();
}
//入栈
public static void Spush(Object obj) {
queuepush.add(obj);
}
}
用栈实现队列
public class StackToQueue {
//分成两个栈，一个用于出队pop栈，另一个用于入队push
//通过栈实现队列
static Stack<Object> stackpush = new Stack<>();
static Stack<Object> stackpop = new Stack<>();
//主要就是通过这个方法完成栈向队列的转化
public static void poll() {
//如果pop栈不为空，则不能把push中的元素到给pop。
if(!stackpop.empty()) {
return;
}else {
//否则就可以把push栈中的元素压入Pop栈
stackpop.push(stackpush.pop());
}
}
//入队
public static void enqueue(Object obj) {
stackpush.push(obj);
poll();
}
//出队
public static void dequeue() {
if(stackpop.empty()) {
poll();
}
stackpop.pop();
}
}