package hill;
 
public class HillSort2 {
	
	public static void main(String[] args) {
		shellSort();
	}
	
	public static void shellSort() {
		int a[] = { 1, 54, 6, 3, 78, 34, 12, 45, 56, 100 };
		double d1 = a.length;
		int temp = 0;
		while (true) {
			//增量
			d1 = Math.ceil(d1 / 2);
			int d = (int) d1;
			//对每个分组进行插入排序
			for (int x = 0; x < d; x++) {
				//第1个位置的增量i
				for (int i = x + d; i < a.length; i += d) {
					//每个小分组进行插入排序
					int j = i - d;
					temp = a[i];
					for (; j >= 0 && temp < a[j]; j -= d) {
						a[j + d] = a[j];
					}
					a[j + d] = temp;
				}
			}
			if (d == 1)
				break;
		}
		for (int i = 0; i < a.length; i++)
			System.out.print(a[i]+"，");
	}
}

package hill;

import java.util.Arrays;

public class HillSort {
	public static int[] a = { 29, 1, 59, 12, 4, 77, 40, 20, 15, 10, 44, 8, 81, 0, 8, 13, 16 };

	public static void main(String[] args) {
		// 设置循环 - 步长 - 间隔
		for (int m = a.length / 2; m > 0; m = m / 2) {
			// 根据步长确定需要排序的数组下标索引
			//根据步长进行分组的
			for (int n = 0; n < a.length; n = n + m) {
				// 对特定数组索引构成的数组进行插入排序
				shellSort(a, n, m);
			}
		}
		System.out.println(Arrays.toString(a));
	}

	/**
	 * 简单的插入排序算法
	 * 
	 * @param a
	 *            需要进行插入排序的数组
	 * @param startIndex
	 *            插入排序的起始索引
	 * @param space
	 *            插入排序的步长
	 */
	public static void shellSort(int[] a, int startIndex, int space) {
		// 循环右边的无序队列 - 从左到右
		for (int i = startIndex + space; i < a.length; i += space) {
			// 循环插入到左边的有序队列中,并且使队列有序 - 从左到右
			for (int j = i - space; j >= startIndex; j -= space) {
				if (a[j + space] < a[j]) {
					// 移动有序交换位置
					int temp = a[j + space];
					a[j + space] = a[j];
					a[j] = temp;
				}
 			}
		}
	}
}

public class SelectSort {
	void sort(int[] A) {
		int small;// 数组中最小值
		for (int i = 0; i < A.length; i++) {
			small = i;			//假设，第一个元素最小
			for (int j = i + 1; j < A.length; j++) {	//与A[1]~A[n]的
				if (A[j] < A[small]) {
					small = j;// j是最小值，赋值给small
				}
			}
			//swap(A[i], A[small]);// 最小值元素与待排序第一个元素交换位置
			int temp = A[i];
			A[i] = A[small];
			A[small] = temp;
		}
	} 
	
	public static void main(String[] args) {
		SelectSort selectSort = new SelectSort();
		int a[] = { 49, 38, 65, 97, 76, 13, 27, 49, 78, 34, 12, 64, 5, 4, 62, 99, 98, 54, 101, 56, 17, 18, 23, 34, 15,
				35, 25, 53, 51 };
		
		selectSort.sort(a);

		for (int i = 0; i < a.length; i++) {
			System.out.print(a[i] + "，");
		}
	}
}

/** 
 * Selection Sorting 
 */  
SELECTION(new Sortable() {  
    public <T extends Comparable<T>> void sort(T[] array, boolean ascend) {  
        int len = array.length;  
        for (int i = 0; i < len; i++) {  
            int selected = i;  
            for (int j = i + 1; j < len; j++) {  
                int compare = array[j].compareTo(array[selected]);  
                if (compare != 0 && compare < 0 == ascend) {  
                    selected = j;  
                }  
            }  
            exchange(array, i, selected);  
        }
    }  
})

public class selectSort {  
    public selectSort(){  
        int a[]={1,54,6,3,78,34,12,45};  
        int position=0;  
        for(int i=0;i<a.length;i++){  
            int j=i+1;  
            //记录最小值下标
            position=i;  
            //记录最小值
            int temp=a[i];  
            for(;j<a.length;j++){  
            //比最小值还要小
            if(a[j]<temp){  
                temp=a[j];  
                position=j;  
             } 
            } 
            a[position]=a[i];  
            //最小值赋值给i的位置
            a[i]=temp;  
        }  
        for(int i=0;i<a.length;i++)  
            System.out.println(a[i]);  
    }
}

public class HeapSort1 {
	
	public static void main(String[] args) {
		HeapSort1 heapSort=new HeapSort1();
		int a[] = { 49, 38, 65, 97, 76, 13, 27, 49, 78, 34, 12, 64, 5, 4, 62, 99, 98, 54, 101, 56, 17, 18, 23, 34, 15, 35,
				25, 53, 51 };
		int n=a.length;
		
		//建最大的堆
		for (int i = (n-2)/2; i >-1; i--) {
				heapSort.creatHeap(a, i, n-1);
		}
		
		for (int i = n-1; i >0; i--) {
			//堆顶元素和堆底元素进行交换
			int tmp=a[i];  
	        a[i]=a[0];  
	        a[0]=tmp;  
			//创建堆
			heapSort.creatHeap(a, 0, i-1);
		}
		

		for (int i = 0; i < a.length; i++) {
			System.out.print(a[i]+"，");
		}
 	}
	
	/**
	 * 
	 * @param data
	 * @param i  
	 * @param j  堆底下标，最后一个数字下标
	 */
	private  void swap(int[] data, int i, int j) {  
        int tmp=data[i];  
        data[i]=data[j];  
        data[j]=tmp;  
    } 

	// 创建最大堆
	void creatHeap(int[] A, int r, int j) {
		// 左节点
		int child = 2 * r + 1;
		// 做比较的节点
		int temp = A[r];

		while (child <= j) {
			// 找到左右子数中较大的节点
			if ((child < j) && (A[child] < A[child + 1])) {
				child++;
			}
			// temp节点>右子节点（大于较大的那个节点）
			//退出循环
			if (temp >= A[child]) {
				break;
			}
			//子节点值赋值给父节点
			A[(child - 1) / 2] = A[child];
			//child的子节点，为了下一次循环
			child = child * 2 + 1;
		}
		//与较大的元素的父节点进行交换
		A[(child - 1) / 2] = temp;
	}
}

package heap;

public class HeapSort2 {

	int a[] = { 49, 38, 65, 97, 76, 13, 27, 49, 78, 34, 12, 64, 5, 4, 62, 99, 98, 54, 56, 17, 18, 23, 34, 15, 35, 25,
			53, 51 };
	
	public static void main(String[] args) {
		new HeapSort2();
	}
	
	public HeapSort2() {
		heapSort(a);

		for (int i = 0; i < a.length; i++) {
			System.out.print(a[i]+"，");
		}
	}

	public void heapSort(int[] a) {
		System.out.println("开始排序");
		int arrayLength = a.length;
		// 循环建堆
		for (int i = 0; i < arrayLength - 1; i++) {
			// 建堆
			buildMaxHeap(a, arrayLength - 1 - i);
			// 交换堆顶和最后一个元素
			swap(a, 0, arrayLength - 1 - i);
			//System.out.println(Arrays.toString(a));
		}
	}

	private void swap(int[] data, int i, int j) {
 		int tmp = data[i];
		data[i] = data[j];
		data[j] = tmp;
	}

	// 对data数组从0到lastIndex建大顶堆
	private void buildMaxHeap(int[] data, int lastIndex) {
		// 从lastIndex处节点（最后一个节点）的父节点开始
		for (int i = (lastIndex - 1) / 2; i >= 0; i--) {
			// k保存正在判断的节点，k作为父节点
			int k = i;
			// 如果当前k节点的子节点存在
			while (k * 2 + 1 <= lastIndex) {
				// k节点的右子节点的索引
				int biggerIndex = 2 * k + 1;
				// 如果biggerIndex小于lastIndex，即biggerIndex+1代表的k节点的右子节点存在
				if (biggerIndex < lastIndex) {
					// 若果右子节点的值较大
					if (data[biggerIndex] < data[biggerIndex + 1]) {
						// biggerIndex总是记录较大子节点的索引
						biggerIndex++;
					}
				}
				// 如果k节点的值小于其较大的子节点的值
				// 或者k节点的值大于其子节点较小的值
				if (data[k] < data[biggerIndex]) {
					// 交换他们
					swap(data, k, biggerIndex);
					// 将biggerIndex赋予k，开始while循环的下一次循环，重新保证k节点的值大于其左右子节点的值（重新保证了，k节点作为父节点，继续下一次比较）
					k = biggerIndex;
				} else {
					break;
				}
			}
		}
	}
}

public class maopaoSort {

	void sort(int[] A) {
		// last：值最大元素的下标位置
		int i, j, last;
		i = A.length - 1;
		while (i > 0) {
			last = 0;
			for (j = 0; j < i; j++) {
				if (A[j] > A[j + 1]) {
					//swap(A[j], A[j + 1]);
					int temp = A[j];
					A[j] = A[j + 1];
					A[j + 1] = temp;
					last = j;// last存，值最大元素的下标
				}
			}
			i = last;// last值赋值i，表示last已经在数组最末尾了，每一次比较i的值逐渐变小，直到while循环结束
		}
	}

	void swap(int a, int b) {
		int temp = a;
		a = b;
		b = temp;
	}

	public static void main(String[] args) {
		maopaoSort maopaoSort = new maopaoSort();
		int a[] = { 49, 38, 65, 97, 76, 13, 27, 49, 78, 34, 12, 64, 5, 4, 62, 99, 98, 54, 101, 56, 17, 18, 23, 34, 15,
				35, 25, 53, 51 };
		maopaoSort.sort(a);
		for (int i = 0; i < a.length; i++) {
			System.out.print(a[i] + "，");
		}
	}
}

public class bubbleSort {  
    public  bubbleSort(){  
        int a[]={49,38,65,97,76,13,27,49,78,34,12,64,5,4,62,99,98,54,56,17,18,23,34,15,35,25,53,51};  
        int temp=0;  
        for(int i=0;i<a.length-1;i++){  
            for(int j=0;j<a.length-1-i;j++){  
            if(a[j]>a[j+1]){  
                temp=a[j];  
                a[j]=a[j+1];  
                a[j+1]=temp;  
            }  
            }  
        }  
        for(int i=0;i<a.length;i++)  
        System.out.println(a[i]);     
    }
}

public class quickSort {  
  int a[]={49,38,65,97,76,13,27,49,78,34,12,64,5,4,62,99,98,54,56,17,18,23,34,15,35,25,53,51};  
public  quickSort(){  
    quick(a);  
    for(int i=0;i<a.length;i++)  
        System.out.println(a[i]);  
}  
public int getMiddle(int[] list, int low, int high) {     
            int tmp = list[low];    //数组的第一个作为中轴     
            while (low < high) {     
                while (low < high && list[high] >= tmp) {     
  
      high--;     
                }     
                list[low] = list[high];   //比中轴小的记录移到低端     
                while (low < high && list[low] <= tmp) {     
                    low++;     
                }     
                list[high] = list[low];   //比中轴大的记录移到高端     
            }     
           list[low] = tmp;              //中轴记录到尾     
            return low;                   //返回中轴的位置     
        }    
public void _quickSort(int[] list, int low, int high) {     
            if (low < high) {     
               int middle = getMiddle(list, low, high);  //将list数组进行一分为二     
                _quickSort(list, low, middle - 1);        //对低字表进行递归排序     
               _quickSort(list, middle + 1, high);       //对高字表进行递归排序     
            }     
        }   
public void quick(int[] a2) {     
            if (a2.length > 0) {    //查看数组是否为空     
                _quickSort(a2, 0, a2.length - 1);     
        }     
       }   
}

/** 
 * Quick Sorting 
 */  
QUICK(new Sortable() {  
    public <T extends Comparable<T>> void sort(T[] array, boolean ascend) {  
        this.sort(array, 0, array.length - 1, ascend);  
    }  
  
    private <T extends Comparable<T>> void sort(T[] array, int lo, int hi, boolean ascend) {  
        if (lo >= hi) {  
            return;  
        }  
        T toFinal = array[lo];  
        int leftIdx = lo;  
        int rightIdx = hi;  
        int i = lo + 1;  
        while (i <= rightIdx) {  
            int compare = array[i].compareTo(toFinal);  
            if (compare == 0) {  
                i++;  
            } else if (compare < 0 == ascend) {  
                exchange(array, leftIdx++, i++);  
            } else {  
                exchange(array, rightIdx--, i);  
            }  
        }  
        // partially sort left array and right array  
        // no need to include the leftIdx-th to rightIdx-th elements  
        // since they are already in its final position  
        sort(array, lo, leftIdx - 1, ascend);  
        sort(array, rightIdx + 1, hi, ascend);  
    }  
})

package merge;
 
public class MergeSort {

	/**
	 *  子序列1的上界：i1；下界：j1
     *  子序列1的上界：i2，下界：j2
     *  2个子序列是相邻的，所以：i2=j1+1
	 * @param A
	 * @param i1 子序列1上界
	 * @param j1 子序列1下界
	 * @param i2 子序列2上界
	 * @param j2 子序列2下界
	 */
	void merge(int[] A, int i1, int j1, int i2, int j2) {
		// 创建一个临时数组，来存取子序列
		int[] temp = new int[A.length];
		// i，j是子序列的游动指针，k是临时数组游动指针
		int i = i1, j = i2, k = 0;
		// 将2个子序列中最小值，存入临时数组
		while (i <= j1 && j <= j2) {
			if (A[i] <= A[j]) {
				temp[k++] = A[i++];
			} else {
				temp[k++] = A[j++];
			}
		}
		//第一个序列还有剩余元素，再存入temp
		while (i <= j1) {
			temp[k++] = A[i++];
		}
		//第二个序列还有剩余元素，再存入temp
		while (j <= j2) {
			temp[k++] = A[j++];
		}
		// 将临时数组值赋值给原数组A
		for (int k2 = 0; k2 < k; k2++) {
			A[i1++] = temp[k2];
		}
	}
	
	public void sort(int[] A, int left, int right) {
		if(left<right){
			// 找出中间索引
			int center = (left + right) / 2;
			// 对左边数组进行递归
			 sort(A, left, center);
			// 对右边数组进行递归
			sort(A, center + 1, right); 
			merge(A, left, center, center + 1, right);
		}
	}
	
	public static void main(String[] args) {
		MergeSort mergeSort = new MergeSort();
		int a[] = { 49, 38, 65, 97, 76, 13, 27, 49, 78, 34, 12, 64, 5, 4, 62, 99, 98, 54, 101, 56, 17, 18, 23, 34, 15,
				35, 25, 53, 51 };
		mergeSort.sort(a, 0, a.length-1);
		for (int i = 0; i < a.length; i++) {
			System.out.print(a[i] + "，");
		}
	}
}

import java.util.Arrays;  
  
public class mergingSort {  
    int a[]={49,38,65,97,76,13,27,49,78,34,12,64,5,4,62,99,98,54,56,17,18,23,34,15,35,25,53,51};  
    
    public  mergingSort(){  
        sort(a,0,a.length-1);  
        for(int i=0;i<a.length;i++)  
            System.out.println(a[i]);  
    }  

    public void sort(int[] data, int left, int right) {    
        if(left<right){  
            //找出中间索引  
            int center=(left+right)/2;  
            //对左边数组进行递归  
            sort(data,left,center);  
            //对右边数组进行递归  
            sort(data,center+1,right);  
            //合并  
            merge(data,left,center,right);  
            
        }  
    }  
    public void merge(int[] data, int left, int center, int right) {  
        int [] tmpArr=new int[data.length];  
        int mid=center+1;  
        //third记录中间数组的索引  
        int third=left;  
        int tmp=left;  
        while(left<=center&&mid<=right){  
            //从两个数组中取出最小的放入中间数组  
            if(data[left]<=data[mid]){  
                tmpArr[third++]=data[left++];  
            }else{  
                tmpArr[third++]=data[mid++];  
            }  
        }  
        //剩余部分依次放入中间数组  
        while(mid<=right){  
            tmpArr[third++]=data[mid++];  
        }  
        while(left<=center){  
            tmpArr[third++]=data[left++];  
        }  
        //将中间数组中的内容复制回原数组  
        while(tmp<=right){  
            data[tmp]=tmpArr[tmp++];  
        }  
        System.out.println(Arrays.toString(data));  
    } 
}

package base;

import java.util.ArrayList;
import java.util.List;

/**
 * 基准排序
 *
 */
public class BaseSort {
	int a[] = { 49, 38, 65, 97, 76, 13, 27, 49, 78, 34, 12, 64, 5, 4, 62, 99, 98, 54, 101, 56, 17, 18, 23, 34, 15, 35,
			25, 53, 51 };
	
	public static void main(String[] args) {
		 new BaseSort();
	}

	public BaseSort() {
		sort(a);
		for (int i = 0; i < a.length; i++) {
			System.out.print(a[i]+"， ");
		}
	}

	public void sort(int[] array) {
		// 首先确定排序的趟数;
		// 最大值
		int max = array[0];
		for (int i = 1; i < array.length; i++) {
			if (array[i] > max) {
				max = array[i];
			}
		}

		int time = 0;
		// 判断位数;
		while (max > 0) {
			max /= 10;
			time++;
		}

		// 建立10个队列;
		List<ArrayList> queue = new ArrayList<ArrayList>();
		for (int i = 0; i < 10; i++) {
			ArrayList<Integer> queue1 = new ArrayList<Integer>();
			queue.add(queue1);
		}

		// 进行time次分配和收集;
		for (int i = 0; i < time; i++) {
			// 分配数组元素;
			for (int j = 0; j < array.length; j++) {
				// 得到数字的第time+1位数;
				int x = array[j] % (int) Math.pow(10, i + 1) / (int) Math.pow(10, i);
				// 位数队列
				ArrayList<Integer> queue2 = queue.get(x);
				queue2.add(array[j]);
				queue.set(x, queue2);
			}
			int count = 0;// 元素计数器;
			// 收集队列元素;
			// 重新给array排序
			for (int k = 0; k < 10; k++) {
				while (queue.get(k).size() > 0) {
					ArrayList<Integer> queue3 = queue.get(k);
					array[count] = queue3.get(0);
					queue3.remove(0);
					count++;
				}
			}
		}
	}
}

import java.util.ArrayList;  
import java.util.List;  
  
public class radixSort {  
    int a[]={49,38,65,97,76,13,27,49,78,34,12,64,5,4,62,99,98,54,101,56,17,18,23,34,15,35,25,53,51};  
public radixSort(){  
    sort(a);  
    for(int i=0;i<a.length;i++)  
        System.out.println(a[i]);  
}  
public  void sort(int[] array){     
                 
            //首先确定排序的趟数;  
        //最大值   
        int max=array[0];     
        for(int i=1;i<array.length;i++){     
               if(array[i]>max){     
               max=array[i];     
               }     
            }     
  
            int time=0;     
           //判断位数;     
            while(max>0){     
               max/=10;     
                time++;     
            }     
                 
        //建立10个队列;     
            List<ArrayList> queue=new ArrayList<ArrayList>();     
            for(int i=0;i<10;i++){     
                ArrayList<Integer> queue1=new ArrayList<Integer>();   
                queue.add(queue1);     
        }     
                
            //进行time次分配和收集;     
            for(int i=0;i<time;i++){     
                     
                //分配数组元素;     
               for(int j=0;j<array.length;j++){     
                    //得到数字的第time+1位数;   
                   int x=array[j]%(int)Math.pow(10, i+1)/(int)Math.pow(10, i);  
                   //位数队列
                   ArrayList<Integer> queue2=queue.get(x);  
                   queue2.add(array[j]);  
                   queue.set(x, queue2);  
            }     
                int count=0;//元素计数器;     
            //收集队列元素;     
                for(int k=0;k<10;k++){   
                while(queue.get(k).size()>0){  
                    ArrayList<Integer> queue3=queue.get(k);  
                        array[count]=queue3.get(0);     
                        queue3.remove(0);  
                    count++;  
              }     
            }     
    }               
   }    
  
}