package com.soke.demo7;
import java.util.Date;
//创建一个排序的类,把各种排序共有的属性和方法抽象出来作为其成员属性和方法封装成排序的类
public class Sort {
/**
  * 作者：麦子
  * 功能：实现各种排序算法：插入排序、希尔排序、快速排序
  * 本文中所采用的数据结构和算法都是个人思路,可能您有更好的数据结构和算法
  * 如有疑问和指教，请E-mail：89104774@qq.com
  * ***********************************************************************************************
  */
public static void main(String[] args) {
  int len=100000;
  int[] arrc=new int[len];int[] arrd=new int[len];
  int[] arre=new int[len];
  for(int i=0;i<len;i++){
   int t=(int)(Math.random()*100);
   arrc=t;arrd=t;arre=t;
  }
/* for(int i=0;i<arr.length;i++){
   System.out.print(arr+" ");
  }
  System.out.println();     */
  
  //多态的体现,都可以用一个sort对象的sort方法来处理,jvm可自行解析是哪一个对象的sort方法
/*  Sort sort = new Insertion();
  sort.sort(arra);   */
/*  Sort sort = new Shell();
  sort.sort(arra);   */
/*  Sort sort = new QuickSort();
  sort.sort(arra,arra.length-1);   */
  
  Sort sort3 = new Insertion();
  Date date4 = new Date();
  long a4 = date4.getTime();
  sort3.sort(arrc);
  Date date5 = new Date();
  long a5 = date5.getTime();
  System.out.println("插入排序用时:"+(a5-a4)+"毫秒");
  
  Sort sort4 = new Shell();
  Date date6 = new Date();
  long a6 = date6.getTime();
  sort4.sort(arrd);
  Date date7 = new Date();
  long a7 = date7.getTime();
  System.out.println("希尔排序用时:"+(a7-a6)+"毫秒");
  
  Sort sort5 = new QuickSort();
  Date date8 = new Date();
  long a8 = date8.getTime();
  sort5.sort(arre,0,arre.length-1);
  Date date9 = new Date();
  long a9 = date9.getTime();
  System.out.println("快速排序用时:"+(a9-a8)+"毫秒");
  
/* 本程序中如果子类中没有重载或重写打印方法时，便都可采用下面的for循环来打印，
  *  由于采用的是引用传递，故arr中元素的顺序已然发生变化
  *  特别注意当上面的 len 较大时，就不要打印了，这个相当耗时，而且
  *  有可能会造成死机现象
  *  sort.show();
     sort.traverseBinaryTree();
  for(int i=0;i<arr.length;i++){
   System.out.print(arr+" ");
  }   */
}

//下面的空方法，是为了实现java语言三大特征之一的多态，多态与继承联系甚为紧密
public void sort(int arr[]){
public void traverseBinaryTree(){}
public void sort(int arr[],int low,int high){}
public void show(){}
}
//******************************************************************************
/*直接插入排序的思路教前面的冒泡排序和选择排序稍好点.若存储结构还是采用数组.它的思想是:
* 将一个数组中元素看成一个有序表和一个无序表.开始时有序表中只包含一个元素,无序表中包含
* n-1个元素,排序过程中每次从无序表中取出第一个元素，将它依次和有序表中元素比较,直到找到
* 合适的位置,便将它插入有序表中的这个位置，而将有序表中这个位置之后的所有元素全部后移一位.
* 这样也是为了节省内存空间,不需要单独开辟一个内存空间给有序表.
*/
//创建一个直接插入排序的类,让其继承父类sort
class Insertion extends Sort{
public void sort(int arr[]){  
  for(int i=1;i<arr.length;i++){//控制外层循环次数
   int temp = arr;
   for(int j=0;j<i;){
    if(arr>arr[j]){
     j++;
    }else{
     for(int k=i;k>j;k--){
      arr[k]=arr[k-1];
     }
     arr[j]=temp;
     j = i+1;
    }
   }
  }
}
}
//******************************************************************************
/*希尔排序又称”缩小增量排序“,是对直接插入法的改进,充分利用利用了分支策略.通俗解释下：即之前
* 的直接插入排序,每次只从无序表中选取一个元素,让它去找自己的位置.而希尔排序则是将数组按某个
* 约定的规则先划分成n个子数组,而对这n个子数组同时进行直接插入排序,(多线程)就好像同时让n个人在自己
* 的子数组去找寻自己的位置.由此可见,这种算法思想是比较好的.
* 本算法思想：先按某种规则得到所需的增量d,按这个增量将数组划分成n个子数组,然后把这个n个子数组相对
* 位置相同元素有看成一个数组，形成m个子数组,对这m个子数组依次分别进行直接插入排序,这样一趟就跑完了.
* 然后将增量按之前的方法处理得到一个新的增量,继续重复上面的操作.直至最后增量等于1时,整个数组已然
* 相对初始时部分有序了,将整个数组进行一次直接插入排序.
*/
//创建一个希尔排序的类,让其继承父类sort
class Shell extends Sort{
public void sort(int arr[]){
  int n = arr.length;
  for(int d=(int)((n+1)/2);d>1;d=(int)((d+1)/2)){//控制外层循环次数,即取了几次增量,d为某次增量的大小
   for(int i=0;i<d;i++){//控制某个增量值对应的哪一列进行直接插入排序
    int j = 0;//控制某个d值下的某个列的行数
    if(n%d==0){j=n/d;}
    else{
     if((n%d-1)>=i){j=n/d+1;}
     else{j=n/d;}
    }
    for(int k=1;k<j;k++){//控制行
     int temp = arr[k*d+i];
     for(int m=0;m<k;){
      if(arr[k*d+i]>arr[m*d+i]){
       m++;
      }else{
       for(int x=k;x>m;x--){
        arr[x*d+i]=arr[(x-1)*d+i];
       }
       arr[m*d+i]=temp;
       m=k+1;
      }
     }
    }
   }
  }
}
}
//******************************************************************************
/*快速排序充分利用了递归策略,故思想比较先进,它是按某种规则从数组中取出一个元素,将其作为轴关键字,
* 将轴关键字之前元素中所有大于轴关键字的元素都扔到轴关键字后面,然后又将轴关键字之后元素中所有
* 小于轴关键字的元素扔到轴关键字前面.之后又对轴关键字之前和之后元素个子组成的数组进行相同处理.
* 但是数据较为庞大时,需开辟较多的内存空间,当然数据海量时,我们就不会采用这个内部排序(在内存中完成排序)
* 方法了,就会采用外部排序法(比如在硬盘中完成排序,充分利用分治策略,当然还是会用内存啦)
* 本算法思想：先用变量记录数组的第一个元素,将其作为轴关键字.并设两个指针变量low、high,
* 一个指向数组的第一个元素,一个指向 数组的最后一个元素.先从high指针开始依次向前找到第一个
* 小于轴关键字的元素,并一直让high指针指向这个元素,将其值赋给low指针指向的元素.
* 然后又从low指针开始依次向后找到第一个大于轴关键字的元素,并一直让low指针指向这个元素,
* 将其值赋给high指针指向的元素交换.如此反复直至low、high相等时,最后将轴关键字赋给low指针指向的元素,
* 这样一趟就跑完了.然后将轴关键字之前和之后元素各看成一个数组,重复上面的操作,
* 直至需要处理的数组中只有一个元素是跳出
* 演示：演示一趟
* (3 5 2 6 8 4) => 3(2 5 2 6 8 4) => (2 5 5 6 8 4) => (2)3(5 6 8 4)
*/
//创建一个快速排序的类,让其继承父类sort
class QuickSort extends Sort{
public void sort(int arr[],int low,int high){
  if(low<high){
   int pivotloc =partition(arr,low,high);//存放轴关键字的位置
   sort(arr,low,pivotloc-1);//递归
   sort(arr,pivotloc+1,high);//递归
  }
}
//将一个数组分割成两个数组的方法
public int partition(int arr[],int low,int high){
  int pivotkey = arr[low];
  while(low<high)
  {
    while(low<high&&arr[high]>=pivotkey){ --high;}
    arr[low] = arr[high];
    while(low<high&&arr[low]<=pivotkey){ ++low;}
    arr[high] = arr[low];
  }
  arr[low] = pivotkey;
  return low;
}
}

//****************************附上某次测试时的结果******************************

//插入排序用时:9985毫秒

//希尔排序用时:20971毫秒

//快速排序用时:79毫秒

//******************************************************************************

值得学习ing!