package com.tts;
import java.util.Random;
public class Sort { //直接插入法就是将一个待排序的子字符串中进行插入，是这个排序还是有序这样的话就可以抱着插入的位置是真确的。
public void sort(int[]a,int n){
int i,j ;
int temp;
for(i=0;i<n-1;i++){
temp=a[i+1];
j=i;
while(j>-1&&temp<a[j]){
a[j+1]=a[j];
j--;
}
a[j+1]=temp;
}
}
public void xsort(int []a,int n,int []d,int dofnum){ //这里使用的是希尔排序，通过学习我们发现使用直接排序法当这个数组比较有序的时候排序速度就比较快。
int i,j,k,m,span; //使用这个特性时我们就可以发现当我们使用希尔排序就是将他先进行大致的排序然后每次降低组数进行
//详细的排序这样的话速度就会很快
int temp;
for(m=0;m<dofnum;m++){
span=d[m];
for(k=0;k<span;k++){
for(i=k;k<n-span;k=k+span){ //希尔排序就是将要进行的数字之间进行有距离的排序
temp=a[i+span];
j=i;
while(j>-1&&temp<a[j]){
a[j+span]=a[j];
j=j-span;
}
a[j+span]=temp;
}
}
}
}
public static void main(String[]args){
Random r= new Random();
int a[]=new int[10000]; //动态初始化
int b[]= new int [10000];
int c[]= new int[]{1000,500,100,10,1};
for(int i=0;i<10000;i++){
a[i]=r.nextInt()/100000000;
}
for(int j=0;j<10000;j++){
b[j]=r.nextInt()/100000000;
}
long began=System.currentTimeMillis();
sort(a,10000);
for(int s:a)
System.out.println(s);
long end = System.currentTimeMillis();
long time =end -began;
System.out.println("使用直接插入法的时间为"+time);
long start= System.currentTimeMillis();
xsort(b,10000,c,5);
for(int s:a)
System.out.println(s);
long xend = System.currentTimeMillis();
long times = xend -start;
System.out.println("使用希尔排序的时间为"+times);
}
}
**********************还可以使用这种方式来实现***********************
package com.tts;
import java.util.Random;
public class Sort {
public void sort(int[]a,int n){
int i,j ;
int temp;
for(i=0;i<n-1;i++){
temp=a[i+1];
j=i;
while(j>-1&&temp<a[j]){
a[j+1]=a[j];
j--;
}
a[j+1]=temp;
}
}
public void xsort(int []a,int n,int []d,int dofnum){
int i,j,k,m,span;
int temp;
for(m=0;m<dofnum;m++){
span=d[m];
for(k=0;k<span;k++){
for(i=k;k<n-span;k=k+span){
temp=a[i+span];
j=i;
while(j>-1&&temp<a[j]){
a[j+span]=a[j];
j=j-span;
}
a[j+span]=temp;
}
}
}
}
public static void main(String[]args){
Sort s= new Sort();
Random r= new Random();
int a[]=new int[10000]; //动态初始化
int b[]= new int [10000];
int c[]= new int[]{1000,500,100,10,1};
for(int i=0;i<10000;i++){
a[i]=r.nextInt()/100000000;
}
for(int j=0;j<10000;j++){
b[j]=r.nextInt()/100000000;
}
long began=System.currentTimeMillis();
s.sort(a,10000);
for(int e:a)
System.out.println(e);
long end = System.currentTimeMillis();
long time =end -began;
System.out.println("使用直接插入法的时间为"+time);
long start= System.currentTimeMillis();
s.xsort(b,10000,c,5);
for(int e:a)
System.out.println(e);
long xend = System.currentTimeMillis();
long times = xend -start;
System.out.println("使用希尔排序的时间为"+times);
}
}
***************************************各种排序时间的比较**************************************
package com.tts;
import java.util.Random;
public class Sort {
public void sort(int[]a,int n){
int i,j ;
int temp;
for(i=0;i<n-1;i++){
temp=a[i+1];
j=i;
while(j>-1&&temp<a[j]){
a[j+1]=a[j];
j--;
}
a[j+1]=temp;
}
}
public void xsort(int []a,int n,int []d,int dofnum){
int i,j,k,m,span;
int temp;
for(m=0;m<dofnum;m++){
span=d[m];
for(k=0;k<span;k++){
for(i=k;k<n-span;k=k+span){
temp=a[i+span];
j=i;
while(j>-1&&temp<a[j]){
a[j+span]=a[j];
j=j-span;
}
a[j+span]=temp;
}
}
}
}
//使用直接选择
public void zjsort(int []a,int n){
int i,j ,small;
int temp; //直接选择的方式就是将每一个数设置为最小然后在其后面的数中进行比较如果有比这个 还小的就进行记录。
for(i=0;i<n;i++){
small=i;
for(j=i+1;j<n;j++)
if(a[j]<a[small]) small=j;
if(small!=i){
temp=a[small];
a[small]= a[i];
a[i]=temp;
}
}
}
//使用冒泡法排序
public void mpsort(int []a, int n){ //就是将现有的数组的两个相邻的数组进行排序只有这样排一次就会把最大的一个排到最后这样之后每次都减一一个排序
int i,j ;
int temp;
for(i=1;i<n;i++){
for(j=0;j<n-i;j++){
if(a[j]>a[j+1]){
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}
}
}
//使用快速排序法
public void kssort(int []a,int low ,int high){
int i=low; //快速排序法也是一种交叉法中的一种，他的思想 就是从现有的数组中找到一个作为一个标准的数据然后进行两边的排序只有这样的话才能进行排序
int j=high; //结束条件就是i<j 只要是小于这边的话就会进行相互的转化然后进行一些比较就是在两边进行一个比较只有这样的速度很快的，
//但是如果只进行一次的比较的话就没有办法所以我们要进行
int temp =a[i];
while(i<j){
while(i<j&&temp<a[j])j--;
if(i<j)
{
a[i]=a[j];
i++;
}
while (i<j&&temp>a[i])i++;
if(i<j)
{
a[j]=a[i];
j--;
}
}
a[i]=temp;
if(low <i) kssort(a,low,i-1);
if(j<high) kssort(a,j+1,high);
}
public static void main(String[]args){
Sort s= new Sort();
Random r= new Random();
int a[]=new int[10000]; //动态初始化
int b[]= new int [10000];
int c[]= new int[]{1000,500,100,10,1};
int d[]=new int[10000];
int e[]=new int[10000];
int f[]=new int[10000];
for(int i=0;i<10000;i++){
a[i]=r.nextInt()/100000000;
}
for(int j=0;j<10000;j++){
b[j]=r.nextInt()/100000000;
}
for(int k=0;k<10000;k++){
d[k]=r.nextInt()/100000000;
}
for(int k1=0;k1<10000;k1++){
e[k1]=r.nextInt()/100000000;
}
for(int k2=0;k2<10000;k2++){
f[k2]=r.nextInt()/100000000;
}
long began=System.currentTimeMillis();
s.sort(a,10000);
/* for(int e:a)
System.out.println(e);
*/
long end = System.currentTimeMillis();
long time =end -began;
System.out.println("使用直接插入法的时间为"+time);
long start= System.currentTimeMillis();
s.xsort(b,10000,c,5);
for(int s1:a)
System.out.println(s1);
long xend = System.currentTimeMillis();
long times = xend -start;
System.out.println("使用希尔排序的时间为"+times);
long start1=System.currentTimeMillis();
s.zjsort(d,10000);
/*for(int e1:d)
System.out.println(e1);
*/
long end1=System.currentTimeMillis();
long times1=end1-start1;
System.out.println("使用直接排序法的时间为"+times1);
long start2=System.currentTimeMillis();
s.mpsort(e, 10000);
long end2= System.currentTimeMillis();
long time2= end2-start2;
System.out.println("使用冒泡法的时间为:"+time2);
/*
*
*/
long start3=System.currentTimeMillis();
s.mpsort(e, 10000);
long end3= System.currentTimeMillis();
long time3= end3-start3;
System.out.println("使用 快速排序法的时间为:"+time3);
}
}