package com.timebusker.algorithm.sort;
import com.timebusker.algorithm.AbstractAlgorithm;
import org.junit.Test;
import java.util.Arrays;
/**
* @Description: AlgorithmSort:排序算法
* <p>
* 参考博客地址：
* https://www.cnblogs.com/guoyaohua/p/8600214.html
* @Author: Administrator
* @Date: 2020/1/17 14:10
**/
public class SortAlgorithm extends AbstractAlgorithm {
/**
* 选择排序:每一轮排序，选择数组中数字最小的那一个放到指定的位置上。
* 时间复杂度o(n^2),无论数组顺序如何都要选择一个最小的值，
* 因为数组的是否有序，不影响时间复杂度
* 空间复杂度o(1)
* 不稳定排序
*/
@Test
public void chooseSort() {
int length = array.length;
for (int i = 0; i < length; i++) {
// 申请额外的空间o(1)
int min = i;
for (int j = i + 1; j < length; j++) {
if (array[min] > array[j]) {
min = j;
}
}
//将最小的下标代表的数与i位置的进行交换
int tmp = array[i];
array[i] = array[min];
array[min] = tmp;
}
println(array);
}
/**
* 直接插入排序:每一轮排序，都是在i坐标之前，包括i坐标的序列是有序的，但是并不是最终的排序位置。
* 时间复杂度o（n^2),对于第二重循环，只会在非有序的环境下才会执行每个元素后移，
* 因此针对有序的数组，时间复杂度最好的情况是o(N)。
* 空间复杂度o(1)
* 稳定排序
*/
@Test
public void insertDirectlySort() {
int length = array.length;
for (int i = 1; i < length; i++) {
for (int j = i; j > 0; j--) {
// 这一步导致该算法是稳定排序
if (array[j] < array[j - 1]) {
int tmp = array[j - 1];
array[j - 1] = array[j];
array[j] = tmp;
}
}
}
println(array);
}
/**
* 折半插入排序:针对直接排序而言，每一个要插入的元素都是插入在有序的数组中，
* 因此，只需要查找到插入的位置即可，查找的方式利用二分查找
* 时间复杂度和直接插入是一样的，只是快在了查找的过程中，还是o(N^2),最好的环境下是o（N）
* 空间复杂度还是o(1)
*/
@Test
public void insertBinarySort() {
int length = array.length;
for (int i = 1; i < length; i++) {
int tmp = array[i];
int low = 0;
int high = i - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (tmp < array[mid]) {
high = mid - 1;
} else {
low = mid + 1;
}
}
for (int j = i; j >= low + 1; j--) {
array[j] = array[j - 1];
}
array[low] = tmp;
}
println(array);
}
/**
* 冒泡排序，每i轮排序，就是不断交换两个元素，直到将最大的元素放到(n-i)的位置上
* 这种实现是按照算法定义的，但是效率是最低的
* 时间复杂度o(n^2)
* 空间复杂度o(1)
* 稳定排序
*/
@Test
public void bubbleSort1() {
int length = array.length;
for (int i = 1; i < length; i++) {
for (int j = 0; j < length - i; j++) {
//这一步导致该算法是稳定排序
if (array[j] > array[j + 1]) {
int tmp = array[j];
array[j] = array[j + 1];
array[j + 1] = tmp;
}
}
}
println(array);
}
/**
* 冒泡排序:高效率实现，因为只需要用一个flag变量来记录本次的排序，是否修改;如果没有修改，说明已经有序
*/
@Test
public void bubbleSort2() {
int length = array.length;
boolean flag = true;
while (flag) {
flag = false;
for (int j = 0; j < length - 1; j++) {
if (array[j] > array[j + 1]) {
int tmp = array[j];
array[j] = array[j + 1];
array[j + 1] = tmp;
flag = true;
}
}
length--;
}
println(array);
}
/**
* 归并排序，将数组一分为二，对于每一子数组继续进行上述步骤，直到子数组只有1个元素，那么自然是有序的。
* 然后不断合并两个数组，直到合并到整个数组。
* 时间复杂度o(NlgN)
* 空间复杂度o(N)
* <p>
* 归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是O(n log n）的时间复杂度。
* 代价是需要额外的内存空间。
*/
@Test
public void mergeSort() {
int length = array.length;
int low = 0;
int high = length - 1;
realSort(array, low, high);
println(array);
}
/**
* 归并排序真正的sort函数
*
* @param array 待排序的数组
* @param low 最低位
* @param high 最高位
*/
private void realSort(int[] array, int low, int high) {
int mid = (low + high) / 2;
if (low < high) {
realSort(array, low, mid);
realSort(array, mid + 1, high);
realMerge(array, low, mid, high);
}
}
private void realMerge(int[] array, int low, int mid, int high) {
int[] tmp = new int[high - low + 1];
int leftPoint = low;
int rightPoint = mid + 1;
int index = 0;
while (leftPoint <= mid && rightPoint <= high) {
if (array[leftPoint] < array[rightPoint]) {
tmp[index++] = array[leftPoint++];
} else {
tmp[index++] = array[rightPoint++];
}
}
while (leftPoint <= mid) {
tmp[index++] = array[leftPoint++];
}
while (rightPoint <= high) {
tmp[index++] = array[rightPoint++];
}
System.arraycopy(tmp, 0, array, low, tmp.length);
}
/**
* 快速排序，选定一个切分元素，每一轮排序后，都保证切分元素之前的元素都小于切分元素，切分元素之后的元素都大于切分元素
* <p>
* 通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，
* 则可分别对这两部分记录继续进行排序，以达到整个序列有序。
* <p>
* 从数列中挑出一个元素，称为 “基准”（pivot）；
* 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。
* 在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
* 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
* <p>
* 时间复杂度o(NlgN)
* 空间复杂度o(lgN)
* 不稳定排序
*/
@Test
public void quickSort() {
int low = 0;
int high = array.length - 1;
sort(array, low, high);
println(array);
}
/**
* 快速排序的递归实现
*
* @param array
* @param low
* @param high
*/
public void sort(int[] array, int low, int high) {
if (low >= high) {
return;
}
int j = partition(array, low, high);
sort(array, low, j - 1);
sort(array, j + 1, high);
}
/**
* 快速排序的辅助方法，来对排序的数组，进行切分,
*
* @param array
* @param low
* @param high
* @return
*/
public int partition(int[] array, int low, int high) {
int i = low;
int j = high;
int x = array[i];
while (i < j) {
// 从右向左找到array[j]小于x的元素
while (i < j && array[j] >= x) {
j--;
}
if (i < j) {
array[i] = array[j];
i++;
}
// 从左向右找到array[i]大于x的元素
while (i < j && array[i] <= x) {
i++;
}
if (i < j) {
array[j] = array[i];
j--;
}
}
array[i] = x;
return i;
}
/**
* 堆排序，建立一个小顶堆，小顶堆满足父节点比两个子节点的值要小
* <p>
* 堆的性质满足:
* 1. 只能在堆顶删除元素
* 2. 只能在堆的最后一位存元素。
* 3. 堆的存储利用数组，满足i节点是父节点，则子节点是2 * i+ 1,2 * i + 2
* 4. 堆的两种建方法，第一种是从上到下，@see sink（）,第二种是从下到上 @see swim
* 5. 堆排序是指在弄好的堆中，输出第一个元素，然后将最后一个元素与第一个元素互换，
* 换后调用sink，找到自己的位置后，在重复这个步骤，就输出一个有序的堆
* 6. 如果要生序就需要大顶堆，要降序就需要小顶堆。
* <p>
* 时间复杂度：o(NlgN)
* 空间复杂度: o(1)
* 这是小顶堆的排序，所以array数组最后是降序的
* 不稳定，不稳定的原因在建堆的时候，就可能把相同元素的位置换了，比如两个相同元素在不同的子树上
*/
@Test
public void heapSort() {
int length = array.length;
// 只能从前一半开始sink
for (int i = length / 2; i >= 0; i--) {
sink(array, i, length);
}
while (length > 0) {
int temp = array[0];
array[0] = array[length - 1];
array[length - 1] = temp;
length--;
sink(array, 0, length);
}
}
/**
* 将i放入对堆中,i的父节点是（i - 1）/ 2,父节点的值是小于他的两个子节点的
* i节点放入后，要向上移动，如果父节点比i节点的值大，则i节点要继续上移。
*
* @param array
* @param i
*/
private void swim(int array[], int i) {
while (i > 0) {
int father = (i - 1) / 2;
if (array[father] > array[i]) {
int temp = array[father];
array[father] = array[i];
array[i] = temp;
}
i = father;
}
}
/**
* 从i节点由上到下开始调整，i节点的子节点为2*i + 1, 2 * i + 2
* i节点要向下移动，直到满足i节点小于两个子节点
*
* @param array array[] 数组
* @param i i节点
*/
public void sink(int[] array, int i, int n) {
int son = 2 * i + 1;
while (son <= n - 1) {
if (son < n - 1 && array[son] > array[son + 1]) son++;
if (array[i] > array[son]) {
int temp = array[i];
array[i] = array[son];
array[son] = temp;
i = son;
son = 2 * i + 1;
} else {
break;
}
}
}
}
