package ts;
public class QuickSoft {
public static void main(String[] args) {
int[] nums = new int[100000];
for (int i = 0; i < nums.length; i++) {
nums[i] = (int) (100 * Math.random());
}
long a = System.currentTimeMillis();
quickSoft(nums, 0, nums.length - 1);
System.out.println("quick time :"
+ ((long) System.currentTimeMillis() - a));
// for(int i=0;i<nums.length;i++)
// {
// System.out.print(nums[i]+" ");
// }
// System.out.println();
for (int i = 0; i < nums.length; i++) {
nums[i] = (int) (100 * Math.random());
}
a = System.currentTimeMillis();
maopao(nums);
System.out.println("maopao time :"
+ ((long) System.currentTimeMillis() - a));
// for(int i=0;i<nums.length;i++)
// {
// System.out.print(nums[i]+" ");
// }
// System.out.println();
for (int i = 0; i < nums.length; i++) {
nums[i] = (int) (100 * Math.random());
}
long ab = System.currentTimeMillis();
HeapSort(nums);
System.out.println("duipaixu time :"
+ ((long) System.currentTimeMillis() - ab));
// System.out.println(System.currentTimeMillis());
// for(int i=0;i<nums.length;i++)
// {
// System.out.print(nums[i]+" ");
// }
// System.out.println();
for (int i = 0; i < nums.length; i++) {
nums[i] = (int) (100 * Math.random());
}
a = System.currentTimeMillis();
// SelectSort(nums);
System.out.println("xuanze time :"
+ ((long) System.currentTimeMillis() - a));
// for(int i=0;i<nums.length;i++)
// {
// System.out.print(nums[i]+" ");
// }
// System.out.println();
for (int i = 0; i < nums.length; i++) {
nums[i] = (int) (100 * Math.random());
}
a = System.currentTimeMillis();
shell(nums);
System.out.println("xier time :"
+ ((long) System.currentTimeMillis() - a));
// for(int i=0;i<nums.length;i++)
// {
// System.out.print(nums[i]+" ");
// }
// System.out.println();
for (int i = 0; i < nums.length; i++) {
nums[i] = (int) (100 * Math.random());
}
a = System.currentTimeMillis();
insertionSort(nums);
System.out.println("charu time :"
+ ((long) System.currentTimeMillis() - a));
// for(int i=0;i<nums.length;i++)
// {
// System.out.print(nums[i]+" ");
// }
// System.out.println();
}
public static void SelectSort(int[] a) {
int Index=a.length;
int i=0, j=0, k=0;
int MinValue=0;
int IndexMin=0;
int Temp=0;
for (i = 0; i<Index - 1; i++){MinValue = 32767;
IndexMin = 0;
for (j = i; j < Index; j++){
if (a[j] < MinValue)
{
MinValue = a[j];
IndexMin =j;
}
}
a[IndexMin]=a[i];
a[i]=MinValue; }
}
public static void maopao(int[] a) {
boolean flag = true;
int index=a.length-1;
for (int i = 0; i < index; i++) {
flag = true;
int j=index;
for (; j >i; j--) {
if (a[j] < a[j - 1]) {
int temp = a[j];
a[j] = a[j - 1];
a[j -1] = temp;
flag = false;
}
}
if (flag)
return;
}
}
public static void quickSoft(int[] a, int I, int J) {
if (I >= J)
return;
int i = I, j = J;
boolean right = true;
while (i < j) {
if (a[i] > a[j]) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
right = (right == true) ? false : true;
}
if (right)
j--;
else
i++;
}
quickSoft(a, I, i - 1);
quickSoft(a, j + 1, J);
}
public static void creatHeap(int[] a,int n,int h)
{
int i=h;
int j=2*i+1;
boolean flag=false;
while(j<n&&flag!=true)
{
int temp=a[i];
if(j<n-1&&a[j]<a[j+1]) j++;
if(temp>a[j]) flag=true;
else{
a[i]=a[j];
i=j;
j=2*i+1;
a[i]=temp;
}
}
}
public static void initHeap(int[] a)
{
int n=a.length;
for(int i=(n-1)/2;i>=0;i--)
creatHeap(a,n,i);
}
public static void HeapSort(int[] a)
{
int n=a.length;
int temp;
initHeap(a);
for(int i=n-1;i>0;i--)
{
temp=a[0];
a[0]=a[i];
a[i]=temp;
creatHeap(a,i,0);
}
}
public static void shell(int[] x) {
// 分组
for (int increment = x.length / 2; increment > 0; increment /= 2) {
// 每个组内排序
for (int i = increment; i < x.length; i++) {
int temp = x[i];
int j = 0;
for (j = i; j >= increment; j -= increment) {
if (temp < x[j - increment]) {
x[j] = x[j - increment];
} else {
break;
}
}
x[j] = temp;
}
}
}
public static void insertionSort(int[] a){
int in,out;
int nElems=a.length;
for(out=1;out<nElems;out++){
int temp=a[out];
in=out;
while(in>0 && a[in-1]>=temp){
a[in]=a[in-1];
in--;
}
a[in]=temp;
}
}
}