package test;
public class first {
/*普通的插入排序*/
public void insertSort(int[] list) {
int i, j;
list[0] = -999;
//相当于设置一个监视哨兵，不用判断是否越界，
//但要求数组从第二个数开始即i=1开始存储
for (i = 1; i < list.length; i++) {
j = i;
while (list[j] < list[j - 1]) {
int temp = list[j];
list[j] = list[j - 1];
list[j - 1] = temp;
j = j - 1;
}
}
}
/*折半插入，在直接插入的基础上，添加二叉查找*/
public void binInsertSort(int[] r, int low, int high) {
for (int i = low + 1; i <= high; i++)
{
int temp = r[i]; // 保存待插入元素
int hi = i - 1;
int lo = low; // 设置初始区间
while (lo <= hi)
{ // 折半确定插入位置
int mid = (lo + hi) / 2;
if (temp < r[mid])
hi = mid - 1;
else
lo = mid + 1;
}
for (int j = i - 1; j > hi; j--)
r[j + 1] = r[j]; // 移动元素
r[hi + 1] = temp; // 插入元素
}
}
/*希尔排序或shell */
public void shellSort(int[] r, int low, int high, int[] delta){
for (int k=0;k<delta.length;k++)
shellInsert(r, low, high, delta[k]);
}
private void shellInsert(int[] r, int low, int high, int deltaK){
for (int i=low+deltaK; i<=high; i++)
if (r[i]<r[i-deltaK]){
int temp = r[i];
int j = i-deltaK;
for(; j>=low&&temp<r[j]; j=j-deltaK)
r[j+deltaK] = r[j];
r[j+deltaK] = temp;
}
}
/*简单的选择交换*/
public void selectSort(int[] r, int low, int high) {
for (int k = low; k < high - 1; k++) { // 作n-1 趟选取
int min = k;
for (int i = min + 1; i <= high; i++)
// 选择关键字最小的元素
if (r[i] < r[min])
min = i;
if (k != min) {
int temp = r[k]; // 关键字最小的元素与元素r[k]交换
r[k] = r[min];
r[min] = temp;
}// end of if
}
}
/*堆排序-大顶堆*/
public void heapSort(int[] r){
int n = r.length - 1;
for (int i=n/2; i>=1; i--)
heapAdjust(r,i,n);
for (int i=n; i>1; i--){
int temp = r[1];
r[1] = r[i];
r[i] = temp;
heapAdjust(r,1,i-1);
}
}
//调整堆
private void heapAdjust(int[] r, int low, int high){
int temp = r[low];
for (int j = 2 * low; j <= high; j = j * 2) {
if (j < high && r[j] < r[j + 1])
j++;
if (temp > r[j])
break;
r[low] = r[j];
low = j;
}
r[low] = temp;
}
public static void main(String[] args) {
first fs = new first();
int[] a = { 100, 9, 8, 9, 9, 7, 7, 0, 0, 99, 55, 7, 6, 5, 4, 3, 2, 1 };
int[] k={5,3,1};
// fs.insertSort(a);
//fs.binInsertSort(a, 0, a.length - 1);
//fs.shellSort(a, 0,a.length-1,k);
//fs.selectSort(a, 0, a.length-1);
fs.heapSort(a);
for (int i = 0; i < a.length; i++) {
System.out.println(a[i]);
}
}
}