import java.util.Arrays;
import java.util.Stack;
public class Test {
public static void main(String[] args) {
int[] array = {10,20,8,25,35,6,18,30,5,15,28};
shellSort1(array);
System.out.println(Arrays.toString(array));
float b = (float) 1 / 3;
System.out.println(b);
}
//直接插入排序，
// 时间复杂度，O(n^2) 最好情况下为O(n) 越有序越快
//空间复杂度为：O(1)
//稳定性：稳定的排序（一个稳定的排序，可以实现为不稳定的排序，如果本身是一个不稳定的排序，你是不能实现为一个稳定的排序）
//技巧：如何快速判断一个排序是否有序？就看是否发生跳跃式交换。
public static void insertSort(int[] array){
for (int i = 1; i < array.length; i++) {
int j = i-1;
int tmp = array[i];
for( ; j >= 0 ; j--){
if(array[j] > tmp){
array[j+1] = array[j];
}else{
break;
}
}
array[j+1] = tmp;
}
}
//希尔排序
//时间复杂度为O(n^1.3 - n^1.5)
public static void shellSort(int[] array) {
int gap = array.length;
while (gap > 1) {
shell(array, gap);
gap = (gap / 5) + 1; // OR gap = gap / 2;
}
shell(array, 1); //保证最后增量为1
}
public static void shellSort1(int[] array){
int[] drr = {5};//增量序列不好求
for (int i = 0; i < drr.length; i++) {
shell(array,drr[i]);
}
}
public static void shell(int[] array,int gap){
for (int i = gap; i < array.length; i++) {
int j = i-gap;
int tmp = array[i];
for( ; j > 0 ; j-=gap){
if(array[j] > tmp){
array[j+gap] = array[j];
}else{
break;
}
}
array[j+gap] = tmp;
}
}
// 选择排序
//每一次从无序区间选出最大（或最小）的一个元素，存放在无序区间的最后（或最前），直到全部待排序的数据元素排完 。
//时间复杂度O(n^2)
//空间复杂度O(1)
//不稳定排序
public static void selectSort(int[] array){
for (int i = 0; i < array.length-1; i++) {
for(int j = i +1; j < array.length; j++){
if(array[i] >array[j]){
int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
}
}
}
//堆排序
//时间复杂度n*logn n个元素 logn的高度调整
//空间复杂度O(1)
//不稳定
//向下调整
public static void shiftDown(int[] array, int parent, int len){
int child = 2*parent+1;
while(child < len){
if(child+1 array[parent]){
int tmp = array[child];
array[child] = array[parent];
array[parent] = tmp;
parent = child;
child = 2*parent+1;
}else {
break;
}
}
}
public static void createHeap(int[] array){
for (int i = (array.length-1-1)/2; i >= 0 ; i--) {
shiftDown(array,i,array.length);
}
}
public static void heapSort(int[] array){
createHeap(array);
int end = array.length-1;
while(end > 0){
int tmp = array[end];
array[end] = array[0];
array[0] = tmp;
shiftDown(array,0,end);
end--;
}
}
//冒泡排序(不优化冒泡排序的情况下)
//时间复杂度O(n^2)
//空间复杂度O(1)
public static void maopaoSort(int[] array){
for (int i = 0; i < array.length-1; i++) {
boolean flg = false;
for (int j = 0; j < array.length-1-i; j++) {
if(array[j] > array[j+1]){
int tmp = array[j];
array[j] = array[j+1];
array[j+1] = tmp;
flg = true;
}
}
if(!flg){
break;
}
}
}
//快速排序(每个基准到最后相当于一个根节点)
//找基准
//时间复杂度O(n*logn)
//最好O(N*logn)每次能够均匀分割待排序的序列
//最坏O(N^2) 数据有序的情况下
//空间复杂度：最好O(logn) 最坏O(n)
//不稳定
public static int partition(int[] array,int start,int end){
int tmp = array[start];
while(start < end){
while(start < end && array[end] >= tmp){
end--;
}
array[start] = array[end];
while (start < end && array[start] <= tmp){
start++;
}
array[end] = array[start];
}
array[start] = tmp; //pivot基准点
return start;
}
public static void quick(int[] array,int low,int high){
if(low >= high){
return;
}
int pivot = partition(array,low,high);
quick(array,low,pivot-1);
quick(array,pivot+1,high);
}
public static void quickSort(int[] array){
quick(array,0,array.length-1);
}
public static void quickSort2(int[] array){
Stack stack = new Stack<>();
int low = 0;
int high = array.length-1;
int pivot = partition(array,low,high);
if(pivot > low+1){
stack.push(low);
stack.push(pivot-1);
}
if(pivot < high-1){
stack.push(pivot+1);
stack.push(high);
}
while(!stack.empty()){
int high2 = stack.pop();
int low2 = stack.pop();
int pivot2 = partition(array,low2,high2);
if(pivot2 > low2+1){
stack.push(low2);
stack.push(pivot2-1);
}
if(pivot2 < high2-1){
stack.push(pivot2+1);
stack.push(high2);
}
}
}
//归并排序
//时间复杂度为O(n*logN)
//空间复杂度为O(N)
//稳定的
public static void merge(int[] array,int low,int mid,int high){
int[] tmprr = new int[high - low+1];
int s1 = low;
int e1 = mid;
int s2 = mid + 1;
int e2 = high;
int k = 0;
while(s1 <= e1 && s2 <= e2){
if(array[s1] < array[s2]){
tmprr[k++] = array[s1++];
}else {
tmprr[k++] = array[s2++];
}
}
while(s1 <= e1){
tmprr[k++] = array[s1++];
}
while(s2 <= e2){
tmprr[k++] = array[s2++];
}
//写回数据到原来的数组
for (int i = 0; i < k; i++) {
array[i+low] = tmprr[i];
}
}
public static void mergeSortIn(int[] array,int low, int high){
if(low >= high){
return;
}
int mid = (low + high)/2;
mergeSortIn(array,low,mid);
mergeSortIn(array,mid+1,high);
merge(array,low,mid,high);
}
public static void mergeSort(int[] array){
mergeSortIn(array,0,array.length-1);
}
//非递归
public static void mergeSortNor(int[] array){
int gap = 1;
while(gap < array.length){
for (int i = 0; i < array.length; i = i + gap*2) {
int low = i;
int mid = low+gap-1;
int high = mid + gap;
if(mid >= array.length){
mid = array.length-1;
}
if(high >= array.length){
high = array.length-1;
}
merge(array,low,mid,high);
}
gap = gap * 2;
}
}
}
