/**
* 冒泡排序
*/
public class BubbleSort {
/**
* 冒泡排序，持续比较相邻元素，大的挪到后面，因此大的会逐步往后挪，故称之为冒泡。
* 复杂度分析：平均情况与最坏情况均为 O(n^2), 使用了 temp 作为临时交换变量，空间复杂度为 O(1).
*/
public static void main(String[] args) {
int[] list = {27, 76, 47, 23, 7, 32, 19, 86};
System.out.println("************冒泡排序************");
System.out.println("排序前：");
display(list);
System.out.println("排序后：");
bubbleSort(list);
display(list);
}
/**
* 遍历打印
*/
public static void display(int[] list) {
if (list != null && list.length > 0) {
for (int num :
list) {
System.out.print(num + " ");
}
System.out.println("");
}
}
/**
* 冒泡排序算法
*/
public static void bubbleSort(int[] list) {
int len = list.length ;
// 做多少轮排序（最多length-1轮）
for (int i = 0; i < len - 1; i++) {
// 每一轮比较多少个
for (int j = 0; j < len - 1 - i; j++) {
if (list[j] > list[j + 1]) {
// 交换次序
int temp = list[j];
list[j] = list[j + 1];
list[j + 1] = temp;
}
}
}
}
}
/**
* 堆排序
*/
public class HeapSort {
/**
* 堆排序的是集合了插入排序的单数组操作，又有归并排序的时间复杂度，完美的结合了2者的优点。
* 参考：https://www.cnblogs.com/huenchao/p/5906193.html
*/
public static void main(String[] args) {
int[] list = {27, 76, 47, 23, 7, 32, 19, 86};
System.out.println("************堆排序************");
System.out.println("排序前：");
display(list);
System.out.println("排序后：");
heapSort(list);
display(list);
}
/**
* 堆排序算法
*/
public static void heapSort(int[] list) {
// 将无序堆构造成一个大根堆，大根堆有length/2个父节点
for (int i = list.length / 2 - 1; i >= 0; i--) {
headAdjust(list, i, list.length);
}
// 逐步将每个最大值的根节点与末尾元素交换，并且再调整其为大根堆
for (int i = list.length - 1; i > 0; i--) {
// 将堆顶节点和当前未经排序的子序列的最后一个元素交换位置
swap(list, 0, i);
headAdjust(list, 0, i);
}
}
/**
* 构造大根堆
*/
public static void headAdjust(int[] list, int parent, int length) {
// 保存当前父节点
int temp = list[parent];
// 得到左孩子节点
int leftChild = 2 * parent + 1;
while (leftChild < length) {
// 如果parent有右孩子，则要判断左孩子是否小于右孩子
if (leftChild + 1 < length && list[leftChild] < list[leftChild + 1]) {
leftChild++;
}
// 父亲节点大于子节点，就不用做交换
if (temp >= list[leftChild]) {
break;
}
// 将较大子节点的值赋给父亲节点
list[parent] = list[leftChild];
// 然后将子节点做为父亲节点
parent = leftChild;
// 找到该父亲节点较小的左孩子节点
leftChild = 2 * parent + 1;
}
// 最后将temp值赋给较大的子节点，以形成两值交换
list[parent] = temp;
}
/**
* 交换数组中两个位置的元素
*/
public static void swap(int[] list, int top, int last) {
int temp = list[top];
list[top] = list[last];
list[last] = temp;
}
/**
* 遍历打印
*/
public static void display(int[] list) {
if (list != null && list.length > 0) {
for (int num :list) {
System.out.print(num + " ");
}
System.out.println("");
}
}
}
/**
* 直接插入排序
*/
public class InsertSort {
/**
* 直接插入排序是一种最简单的排序方法，它的基本操作是将一个记录插入到已排好的有序的表中，从而得到一个新的、记录数增1的有序表。
* 当前元素的前面元素均为有序，要插入时，从当前元素的左边开始往前找（从后往前找），比当前元素大的元素均往右移一个位置，最后把当前元素放在它应该呆的位置就行了。
* 参考：https://www.cnblogs.com/mengdd/archive/2012/11/24/2786490.html
*/
public static void main(String[] args) {
int[] list = {27, 76, 47, 23, 7, 32, 19, 86};
System.out.println("************直接插入排序************");
System.out.println("排序前：");
display(list);
System.out.println("排序后：");
insertSort(list);
display(list);
}
/**
* 直接插入排序算法
*/
public static void insertSort(int[] list) {
int len = list.length ;
// 从无序序列中取出第一个元素 (注意无序序列是从第二个元素开始的)
for (int i = 1; i < len; i++) {
int temp = list[i];
int j;
// 遍历有序序列
// 如果有序序列中的元素比临时元素大，则将有序序列中比临时元素大的元素依次后移
for (j = i - 1; j >= 0 && list[j] > temp; j--) {
list[j + 1] = list[j];
}
// 将临时元素插入到腾出的位置中
list[j + 1] = temp;
}
}
/**
* 遍历打印
*/
public static void display(int[] list) {
if (list != null && list.length > 0) {
for (int num :list) {
System.out.print(num + " ");
}
System.out.println("");
}
}
}
/**
* 归并排序
*/
public class MergeSort {
/**
* 归并排序（Merge Sort）与快速排序思想类似：将待排序数据分成两部分，继续将两个子部分进行递归的归并排序；然后将已经有序的两个子部分进行合并，最终完成排序。
* 其时间复杂度与快速排序均为O(nlogn)，但是归并排序除了递归调用间接使用了辅助空间栈，还需要额外的O(n)空间进行临时存储。从此角度归并排序略逊于快速排序，但是归并排序是一种稳定的排序算法，快速排序则不然。
* 所谓稳定排序，表示对于具有相同值的多个元素，其间的先后顺序保持不变。对于基本数据类型而言，一个排序算法是否稳定，影响很小，但是对于结构体数组，稳定排序就十分重要。例如对于student结构体按照关键字score进行非降序排序：
*/
public static void main(String[] args) {
int[] list = {50, 10, 90, 30, 70};
System.out.println("************归并排序************");
System.out.println("排序前：");
display(list);
System.out.println("排序后：");
mergeSort(list, new int[list.length], 0, list.length - 1);
display(list);
}
/**
* 归并排序算法
* @param list 待排序的列表
* @param tempList 临时列表
* @param head 列表开始位置
* @param rear 列表结束位置
*/
public static void mergeSort(int[] list, int[] tempList, int head, int rear) {
if (head < rear) {
// 取分割位置
int middle = (head + rear) / 2;
// 递归划分列表的左序列
mergeSort(list, tempList, head, middle);
// 递归划分列表的右序列
mergeSort(list, tempList, middle + 1, rear);
// 列表的合并操作
merge(list, tempList, head, middle + 1, rear);
}
}
/**
* 合并操作(列表的两两合并)
* @param list
* @param tempList
* @param head
* @param middle
* @param rear
*/
public static void merge(int[] list, int[] tempList, int head, int middle, int rear) {
// 左指针尾
int headEnd = middle - 1;
// 右指针头
int rearStart = middle;
// 临时列表的下标
int tempIndex = head;
// 列表合并后的长度
int tempLength = rear - head + 1;
// 先循环两个区间段都没有结束的情况
while ((headEnd >= head) && (rearStart <= rear)) {
// 如果发现右序列大，则将此数放入临时列表
if (list[head] < list[rearStart]) {
tempList[tempIndex++] = list[head++];
} else {
tempList[tempIndex++] = list[rearStart++];
}
}
// 判断左序列是否结束
while (head <= headEnd) {
tempList[tempIndex++] = list[head++];
}
// 判断右序列是否结束
while (rearStart <= rear) {
tempList[tempIndex++] = list[rearStart++];
}
// 交换数据
for (int i = 0; i < tempLength; i++) {
list[rear] = tempList[rear];
rear--;
}
}
/**
* 遍历打印
*/
public static void display(int[] list) {
if (list != null && list.length > 0) {
for (int num :list) {
System.out.print(num + " ");
}
System.out.println("");
}
}
}
/**
* 快速排序
*/
public class QuickSort {
/**
* 通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
*/
public static void main(String[] args) {
int[] list = {6, 1, 2, 7, 9, 3, 4, 5, 10, 8};
System.out.println("************快速排序************");
System.out.println("排序前：");
display(list);
System.out.println("排序后：");
quickSort(list, 0, list.length - 1);
display(list);
}
/**
* 快速排序算法
*/
public static void quickSort(int[] list, int left, int right) {
if (left < right) {
// 分割数组，找到分割点
int point = partition(list, left, right);
// 递归调用，对左子数组进行快速排序
quickSort(list, left, point - 1);
// 递归调用，对右子数组进行快速排序
quickSort(list, point + 1, right);
}
}
/**
* 分割数组，找到分割点
*/
public static int partition(int[] list, int left, int right) {
// 用数组的第一个元素作为基准数
int first = list[left];
while (left < right) {
while (left < right && list[right] >= first) {
right--;
}
// 交换
swap(list, left, right);
while (left < right && list[left] <= first) {
left++;
}
// 交换
swap(list, left, right);
}
// 返回分割点所在的位置
return left;
}
/**
* 交换数组中两个位置的元素
*/
public static void swap(int[] list, int left, int right) {
int temp;
if (list != null && list.length > 0) {
temp = list[left];
list[left] = list[right];
list[right] = temp;
}
}
/**
* 遍历打印
*/
public static void display(int[] list) {
if (list != null && list.length > 0) {
for (int num :list) {
System.out.print(num + " ");
}
System.out.println("");
}
}
}
/**
* 直接选择排序
*/
public class SelectionSort {
/**
* 所谓选择排序，就是每次找到未排序中最小的（最大的也行）元素的位置，找到后与该位置与未排序序列的第一个元素交换值，直到该序列成为有序序列。
* 初始状态整个序列为无序序列，每次交换都使有序序列的长度加一，无序序列的起始位置后移一位。选择排序的平均时间复杂度为O(n^2)，且选择排序相对不稳定。
*/
public static void main(String[] args) {
int[] list = {27, 76, 47, 23, 7, 32, 19, 86};
System.out.println("************直接选择排序************");
System.out.println("排序前：");
display(list);
System.out.println("排序后：");
selectionSort(list);
display(list);
}
/**
* 直接选择排序算法
*/
public static void selectionSort(int[] list) {
int len = list.length ;
// 要遍历的次数（length-1次）
for (int i = 0; i < len - 1; i++) {
// 将当前下标定义为最小值下标
int min = i;
// 遍历min后面的数据
for (int j = i + 1; j <= len - 1; j++) {
// 如果有小于当前最小值的元素，将它的下标赋值给min
if (list[j] < list[min]) {
min = j;
}
}
// 如果min不等于i，说明找到真正的最小值
if (min != i) {
swap(list, min, i);
}
}
}
/**
* 交换数组中两个位置的元素
*/
public static void swap(int[] list, int min, int i) {
int temp = list[min];
list[min] = list[i];
list[i] = temp;
}
/**
* 遍历打印
*/
public static void display(int[] list) {
if (list != null && list.length > 0) {
for (int num :list) {
System.out.print(num + " ");
}
System.out.println("");
}
}
}
/**
* 希尔排序
*/
public class ShellSort {
/**
* Shellsort是最古老的排序算法之一，该算法以其发明者Donald L. Shell的名字命名（1959）。
* 在ShellSort排序算法之前的算法时间复杂度基本都是O(n2)O(n2)，该算法是突破这个时间复杂度的第一批算法之一。
* 另外 Shellsort 是快速、易于理解和易于实现的。 然而，其复杂度分析有点复杂。
*/
public static void main(String[] args) {
int[] list = {27, 76, 47, 23, 7, 32, 19, 86};
System.out.println("************希尔排序************");
System.out.println("排序前：");
display(list);
System.out.println("");
System.out.println("排序后：");
shellSort(list);
display(list);
}
/**
* 希尔排序算法
*/
public static void shellSort(int[] list) {
int len = list.length ;
// 取增量
int gap = len / 2;
while (gap >= 1) {
// 无序序列
for (int i = gap; i < len; i++) {
int temp = list[i];
int j;
// 有序序列
for (j = i - gap; j >= 0 && list[j] > temp; j = j - gap) {
list[j + gap] = list[j];
}
list[j + gap] = temp;
}
// 缩小增量
gap = gap / 2;
}
}
/**
* 遍历打印
*/
public static void display(int[] list) {
if (list != null && list.length > 0) {
for (int num :list) {
System.out.print(num + " ");
}
System.out.println("");
}
}
}
/**
*
* 百亿数据中取中位数
* 场景：股市上一个股票的价格从开市开始是不停的变化的，需要开发一个系统，给定一个股票，它能实时显示从开市到当前时间的这个股票的价格的中位数（中值）。
* 创建者 柒
* 创建时间 2018年12月21日
*/
public class FindMedian {
//maxHeap保存较小的半边数据，minHeap保存较大的半边数据。
private static PriorityQueue<Integer> maxHeap, minHeap;
public static void main(String[] args) {
Comparator<Integer> revCmp = new Comparator<Integer>() {
@Override
public int compare(Integer left, Integer right) {
return right.compareTo(left);
}
};
maxHeap = new PriorityQueue<Integer>(100, revCmp);
minHeap = new PriorityQueue<Integer>(100);
Random ra =new Random();
for(int i=0;i<=100;i++){
int number = ra.nextInt(200);
addNumber(number);
}
System.out.println(minHeap);
System.out.println(maxHeap);
System.out.println(getMedian());
}
/*
* offer 新增元素
* peek 头部查询元素
* poll 队列中删除从头部
* 1)比较两个堆的大小，第一次肯定相同，此时两个堆都没有数据，把第一个数据放入大堆
* 2)比较两个堆的大小，第二次肯定不同，如果value值小于大堆头部的值，小堆加入大堆头部元素，大堆加入当前值
* 注意：
* 并不是线程安全的，多线程访问操作会有并发问题
*/
public static void addNumber(int value) {
if (maxHeap.size() == minHeap.size()) {
if (minHeap.peek() != null && value > minHeap.peek()) {
maxHeap.offer(minHeap.poll());
minHeap.offer(value);
} else {
maxHeap.offer(value);
}
} else {
if (value < maxHeap.peek()) {
minHeap.offer(maxHeap.poll());
maxHeap.offer(value);
} else {
minHeap.offer(value);
}
}
}
/*
* If maxHeap and minHeap are of different sizes,
* then maxHeap must have one extra element.
*/
public static double getMedian() {
if (maxHeap.isEmpty()) {
return -1;
}
if (maxHeap.size() == minHeap.size()) {
return (double)(minHeap.peek() + maxHeap.peek())/2;
} else {
return maxHeap.peek();
}
}
}
