package corejava05;
import java.util.Arrays;
publicclass Corejava05 {
      //今天主要讲3种排序方法

      //main方法用了测试写的代码写的对不对

      //对了 有一点要说下

      //加static和没加static有什么区别

      //main函数一定是static的 如果我下面的方法不加static 我在main函数里就可以直接调用

      //如果我不加，那么就要实例化这个方法所在的类，就是Corejava05,然后再通过这个类的实例去访问这个方法

      publicstaticvoid main(String[] args) {
            //测试选择排序

            //怎么叫选择排序呢，以下面为例

            //21 和32比较 21小 不变，然后21和12比较 21大 21和12交换位置

            //然后12和342比较 12小 不变 然后12 和23比较 12 小 不变

            //当然你以从大到小的方式 也可以，也叫选择排序，

            //选择排序指的是你的比较方式，跟你从大到小或者从小到大无关

            //总结下 选择排序就是 拿数组的第一个元素 和下面所有的元素逐一进行比较 比他小就交换位置，比他大就不变，这样 第一个元素就是最小值了

            //然后开始第二个元素依次和下面的元素比。。。这样就叫选择排序

      int[] ary={21,32,12,342,23};//静态初始化，创建测试数组

            selectSort(ary);
            System.out.println(Arrays.toString(ary));//[12, 21, 23, 32, 342] 正确了

            //测试冒泡排序

            //���泡就是

            //第一个跟第二比 第一个比第二个大 就交换位置，然后第二个跟第三个比 比他大就交换位置 小就不变

            //这样 一轮过后  最后一个元素 就是数组中最大的元素，然后 第二轮循环再找数组中第二大的元素

      int[] ary1={21,32,12,342,23};
            bubbleSort(ary1);
            System.out.println(Arrays.toString(ary1));//[12, 21, 23, 32, 342] 正确了

            //测试插入排序

            //插入排序是3种排序里相对比较难的

            //我一时间也有点忘了 看了下资料才知道，尴尬

            // 21,32,12,342,23
            //      ^  刚开始相当于有个指针指这  （java没指针 ，我这么说比较形象点） 

            //把指针所指的 值赋给临时变量 t 

            //然后 t 与 指针的前一个元素比较  也就是21 如果比21小 那么 21就到他这个位置的+1位置 如果比21大那么他就在原位置不变 

            // 这样 第一轮循环结束 

            //然后指针+1 指向12 

            // 12 赋给临时变量t 

            // t和指针前一个元素 也就是32比 比32小 那么32 移到自己位置的+1的位置，然后t再跟21比，21比12大 21移到自己的位置+1的位置

            // 21前面没了 所以12只能放在21前面了

            //插入相对来说比较复杂，但是 想懂了 之后 发现 其实 也没什么

      int[] ary2={21,32,12,342,23};
            insertSort(ary2);
            System.out.println(Arrays.toString(ary2));//[12, 21, 23, 32, 342] 正确了

            //还有一种排序 是java api 提供的  （当然比我们写的好咯）

      int[] ary3={21,32,12,342,23};
            Arrays.sort(ary3);
            System.out.println(Arrays.toString(ary3));//[12, 21, 23, 32, 342] 正确了

            //有没人想知道哪个排序比较快 哪个比较慢？我们来测试下吧

            int[] ary4={2321,432,123,13,12312,31,321,312,3123,1231,3,
                  123,12,3,123,1,31,23,12,31,242,41,41241,41,41,24,124
            };//写多点有可比性是吧

            //本来是想测试下的，结果显示都是0，哎 怪他性能太好啊，，，那我就不测试了，把这个任务留给大家吧，别怪我偷懒哈。。。

            long now=System.currentTimeMillis();
            selectSort(ary4);
            long end=System.currentTimeMillis();
            System.out.println("选择排序："+(end-now));//输出运行的毫秒数

            int[] ary5={2321,432,123,13,12312,31,321,312,3123,1231,3,
            123,12,3,123,1,31,23,12,31,242,41,41241,41,41,24,124};
            now=System.currentTimeMillis();
            bubbleSort(ary5);
            end=System.currentTimeMillis();
            System.out.println("冒泡排序："+(end-now));
            int[] ary6={2321,432,123,13,12312,31,321,312,3123,1231,3,
            123,12,3,123,1,31,23,12,31,242,41,41241,41,41,24,124};
            now=System.currentTimeMillis();
            insertSort(ary6);
            end=System.currentTimeMillis();
            System.out.println("插入排序："+(end-now));
            int[] ary7={2321,432,123,13,12312,31,321,312,3123,1231,3,
            123,12,3,123,1,31,23,12,31,242,41,41241,41,41,24,124};
            now=System.currentTimeMillis();
            Arrays.sort(ary7);
            end=System.currentTimeMillis();
            System.out.println("系统排序："+(end-now));
      }
      //选择排序

      publicstaticvoid selectSort(int[] ary){
            for(int i=0;i<ary.length-1;i++){
                  for(int j=i+1;j<ary.length;j++){
                        if(ary[i]>ary[j]){
                              //下面3句的意思就是交换

ary[i] ary[j]的值，c是中间变量

                              //比较经典的例子就是

                              //有3个杯子 2杯装满水一个杯子空的 怎么把2个杯子中的水交换下呢

                              //是不是跟我下面的代码顺序差不多

                              int c=ary[i];
                              ary[i]=ary[j];
                              ary[j]=c;
                        }
                  }
            }
      }
      //冒泡排序

      publicstaticvoid bubbleSort(int[] ary){
            for(int i=0;i<ary.length-1;i++){
                  for(int j=0;j<ary.length-1-i;j++){
                        if(ary[j]>ary[j+1]){
                              int c=ary[j];
                              ary[j]=ary[j+1];
                              ary[j+1]=c;
                        }
                  }
            }
      }
      //插入排序

      publicstaticvoid insertSort(int[] ary){
            for(int i=1;i<ary.length;i++){
                  int t=ary[i];
                  int j;
                  //for(j=i-1;ary[j]>t&&j>=0;j--){ //这里报了个错，说数组越界，为什么呢? 

                  //当你最后的时候 j=0，满足条件，循环后，j--，在判断条件

ary[-1],,所以数组越界，

                  //我们可以把条件改下，把j>=0放前面，这样，当j>=0不满足时，

jvm就不会再去执行ary[j]>t这条语句了

                  for(j=i-1;j>=0&&ary[j]>t;j--){//再執行下就對了

                        ary[j+1]=ary[j];
                  }
                  ary[j+1]=t;
            }
      }
}