数组的几种排序方式

数组的几种排序方式由于面试几次均遇到过数组排序,自己只擅长选择排序,所以写篇博客对排序做一个总结,加深记忆和理解(排序的复杂度涉及到算法等问题,本人菜鸟就不深入了,等掌握一些算法知识后,再回头把这些知识点补上)。主要总结三种方式:(1)冒泡排序(2)选择排序(3)快速排序(一)冒泡排序:原理:是相邻的两个数进行比

大家好,欢迎来到IT知识分享网。

  由于面试几次均遇到过数组排序,自己只擅长选择排序,所以写篇博客对排序做一个总结,加深记忆和理解(排序的复杂度涉及到算法等问题,本人菜鸟就不深入了,等掌握一些算法知识后,再回头把这些知识点补上)。主要总结三种方式:(1)冒泡排序(2)选择排序(3)快速排序

(一)冒泡排序:

      原理:是相邻的两个数进行比较,符合条件的进行交换位置;

      举例解析:比如数组  int[] arr = {22,36,18,43,14,19,6};

      我们升序来排第一遍:最大数第一遍排完会放在最后一位

      arr[0]与arr[1]比较之后的顺序:{22,36,18,43,14,19,6}(22<36,不交换)

      arr[1]与arr[2]比较之后的顺序:{22,18,36,43,14,19,6}(18<36,交换)

      arr[2]与arr[3]比较之后的顺序:{22,18,36,43,14,19,6}(36<43,不交换)

      arr[3]与arr[4]比较之后的顺序:{22,18,36,14,43,19,6}(14<43,交换)

      arr[4]与arr[5]比较之后的顺序:{22,18,36,14,19,43,6}(19<43,交换)

      arr[5]与arr[6]比较之后的顺序:{22,18,36,14,19,6,43}(6<43,交换)

     第一遍排完43是最大数,放在了最后,这就像水泡往上升一样,慢慢升到了水平面上;第一遍比较了6次,数组长度为7;接着{22,18,36,14,19,6,43}进行第二遍遍历比较:

     arr[0]与arr[1]比较之后的顺序:{18,22,36,14,19,6,43}(18<22,交换)

       arr[1]与arr[2]比较之后的顺序:{18,22,36,14,19,6,43}(22<36,不交换)

     arr[2]与arr[3]比较之后的顺序:{18,22,14,36,19,6,43}(14<36,不交换)

     arr[3]与arr[4]比较之后的顺序:{18,22,14,19,36,6,43}(19<36,交换)

     arr[4]与arr[5]比较之后的顺序:{18,22,14,19,6,36,43}(6<36,交换)

      第二遍走完,36排到了正确的位置,比较了5次(下面交不交换就不写了),接着{18,22,14,19,6,36,43}进行第三遍比较:

       arr[0]与arr[1]比较之后的顺序:{18,22,14,19,6,36,43}

       arr[1]与arr[2]比较之后的顺序:{18,14,22,19,6,36,43}

     arr[2]与arr[3]比较之后的顺序:{18,14,19,22,6,36,43}

     arr[3]与arr[4]比较之后的顺序:{18,14,19,6,22,36,43}

      第三遍走完,22排到了正确的位置,比较了4次,接着{18,14,19,6,22,36,43}进行第四遍比较:

      arr[0]与arr[1]比较之后的顺序:{14,18,19,6,22,36,43}

      arr[1]与arr[2]比较之后的顺序:{14,18,19,6,22,36,43}

      arr[2]与arr[3]比较之后的顺序:{14,18,6,19,22,36,43}

      第四遍走完,19排到了正确的位置,比较了3次,接着{14,18,6,19,22,36,43}进行第五遍比较:

      arr[0]与arr[1]比较之后的顺序:{14,18,6,19,22,36,43}

        arr[1]与arr[2]比较之后的顺序:{14,6,18,19,22,36,43}

      第五遍走完,18排到了正确的位置,比较了2次,接着{14,6,18,19,22,36,43}进行第六遍比较:

      arr[0]与arr[1]比较之后的顺序:{6,14,18,19,22,36,43}

             第六遍终于排完了(汗!!!(⊙﹏⊙))。数组长度为7,排了6遍,第一遍比较6次,第二遍5次….第六遍1次;下面看代码:

数组的几种排序方式
数组的几种排序方式

 1 public class ArraySortDemo {
 2     
 3     public static void main(String[] args) {
 4         
 5         int[] arr = {22,36,18,43,14,19,6};
 6         MaoPaoSort(arr);
 7         printArray(arr);
 8         
 9     }
10     
11     //冒泡排序的方法
12     public static void MaoPaoSort(int[] arr){
13         //排了六遍,所以外层循环六次
14         for(int i=0;i<arr.length-1;i++){
15             //内层循环,每次比较的次数都在递减,所以可以得出如下的条件
16             for (int j = 0; j < arr.length-1-i; j++) {
17                 if(arr[j]>arr[j+1]){
18                     int temp = arr[j];
19                     arr[j] = arr[j+1];
20                     arr[j+1] = temp;
21                 }
22             }
23         }
24     }
25     
26     //打印数组的方法
27     public static void printArray(int[] arr){
28         System.out.print("[");
29         for (int i = 0; i < arr.length; i++) {
30             if(i<arr.length-1) 
31                 System.out.print(arr[i]+",");
32             else
33                 System.out.print(arr[i]+"]");
34         }
35     }
36     
37 }

View Code

     结果如下:

数组的几种排序方式

(二)选择排序:原理是arr[0],与余下的所有数比较,符合条件的进行交换,这样,第一遍就把最小(或最大)的数固定在了第一个位置;然后第二遍是从arr[1],与arr[2],arr[3]…..进行比较,然后把第二小的(或次大的)数固定在第二个位置了;然后第三遍,第四遍….依次这样排下去;

  举例解析:比如数组  int[] arr = {22,36,18,43,14,19,6};

  第1遍:arr[0]与arr[1]比较之后顺序:{22,36,18,43,14,19,6};

      arr[0]与arr[2]比较之后顺序:{18,36,22,43,14,19,6};

      arr[0]与arr[3]比较之后顺序:{18,36,22,43,14,19,6};

        arr[0]与arr[4]比较之后顺序:{14,36,22,43,18,19,6};

      arr[0]与arr[5]比较之后顺序:{14,36,22,43,18,19,6};

      arr[0]与arr[6]比较之后顺序:{6,36,22,43,18,19,14};

  第1遍结束,比较6次,6到了第一位,接着{6,36,22,43,18,19,14}从arr[1]开始比较第1遍:

      arr[1]与arr[2]比较之后顺序:{6,22,36,43,18,19,14};

      arr[1]与arr[3]比较之后顺序:{6,22,36,43,18,19,14};

      arr[1]与arr[4]比较之后顺序:{6,18,36,43,22,19,14};

      arr[1]与arr[5]比较之后顺序:{6,18,36,43,22,19,14};

      arr[1]与arr[6]比较之后顺序:{6,14,36,43,22,19,18};

  第2遍结束,比较5次,14到了第2位,接着{6,14,36,43,22,19,18}从arr[2]开始比较第3遍:

             arr[2]与arr[3]比较之后顺序:{6,14,36,43,22,19,18};

      arr[2]与arr[4]比较之后顺序:{6,14,22,43,36,19,18};

      arr[2]与arr[5]比较之后顺序:{6,14,19,43,36,22,18};

      arr[2]与arr[6]比较之后顺序:{6,14,18,43,36,22,19};

  第3遍结束,比较4次,18到了第3位,接着{6,14,18,43,36,22,19}从arr[3]开始比较第4遍:

      arr[3]与arr[4]比较之后顺序:{6,14,18,36,43,22,19};

      arr[3]与arr[5]比较之后顺序:{6,14,18,22,43,36,19};

      arr[3]与arr[6]比较之后顺序:{6,14,18,19,43,36,22};

  第4遍结束,比较3次,19到了第4位,接着{6,14,18,19,43,36,22}从arr[4]开始比较第5遍:

      arr[4]与arr[5]比较之后顺序:{6,14,18,19,36,43,22};

      arr[4]与arr[6]比较之后顺序:{6,14,18,19,22,43,36};

  第5遍结束,比较2次,22到了第5位,接着{6,14,18,19,22,43,36}从arr[5]开始比较第6遍:

      arr[5]与arr[6]比较之后顺序:{6,14,18,19,22,36,43}

  第6遍结束,总共比排序排了6遍,第一遍比较6次,第二遍5次….第六遍1次,每一遍的比较次数,依次比上一遍少一次,代码方法如下

数组的几种排序方式
数组的几种排序方式

 1 //选择排序的方法
 2     public static void selectSort(int[] arr){
 3         //外层循环依旧是排六次
 4         for (int i = 0; i < arr.length-1; i++) {
 5             //内层循环,每次开始的角标在增加,注意i+1,后i=6,i+1等于7,角标会越界,所以外层i < arr.length-1
 6             for (int j = i+1; j < arr.length; j++) {
 7                 if(arr[i]>arr[j]){
 8                     int temp = arr[i];
 9                     arr[i] = arr[j];
10                     arr[j] = temp;
11                 }
12             }
13         }
14     }

View Code

 (三)快速排序:这个理解的不是很透彻,思路是,要定一个中间值,第一遍排序,要将这个数组分成左右两部分,左半部分全部小于这个中间值,右半部分全部大于这个中间值,

    举例解析:比如数组  int[] arr = {22,36,18,43,14,19,6},这个数组以第一个22为中间值,那么左半部分就是6,14,18,19(当然顺序不是这样排好的,顺序依旧是散乱的),右半部分应该是36,43,这样第一遍分了两部分之后,再分别对这两部分递归调用该函数;

    第一遍排序:

          从左往右比较:arr[0]=22与arr[6]=6比较,arr[0]>arr[6],交换{6,36,18,43,14,19,22},接着进行,

          从右往左比较:arr[0]与arr[6]已比较过,所以,arr[6]=22与arr[1]=36比较,arr[6]<arr[1],交换{6,22,18,43,14,19,36},接着进行

          从左往右比较:arr[1]与arr[6]已比较过,所以,arr[1]=22与arr[5]=19比较,arr[1]>arr[5],交换{6,19,18,43,14,22,36},接着进行

          从右往左比较:arr[1]与arr[5]已比较过,所以,arr[5]=22与arr[2]=18比较,arr[5]>arr[2],不交换{6,19,18,43,14,22,36},接着进行

          因为没交换,所以还是从从右往左比较:即还是arr[5]=22与arr[3]=43比较,arr[3]>arr[5],交换{6,19,18,22,14,43,36},接着进行

          从左往右比较:arr[3]与arr[5]已比较过,所以,arr[3]=22与arr[4]=14比较,arr[2]>arr[4],交换{6,19,18,14,22,43,36},接着进行

    第一遍比较结束:这时候数组以22这个中间值就分层了左右两个部分{6,19,18,14} 与{43,36};然后分别对这两部分采用第一遍的方式进行排序,即是递归调用了;显然右半部分来一次就完成了,左半部分进行排序{6,19,18,14},arr[0]=6显然以这个为中间值排完后左半部分没有,右半部分为{19,18,14},然后再以arr[0]=19这个中间值开始排:

            从左往右比较:arr[0]=19与arr[2]=14比较,arr[0]>arr[2],交换{14,18,19},接着进行,

          从右往左比较:arr[2]=19与arr[1]=18比较,显然,不用交换,结果{14,18,19},排序结束;

整个排序到此就算结束,这样排下来整合就是想要的结果:{6,14,18,19,22,36,43};关键点:定arr[0]为中间值,先从左往右比较,arr[0]与arr[6],交换了(比较之后,arr[0]就不参与比较了,下次比较arr[0]的下一个索引,即arr[1]),就换成从右往左比较了,就依然是拿中间值(这时候arr[6]=中间值了)与左边的刚比较过的下一个索引的值比较(即arr[1]),若是交换了(arr[6]就不参与了,arr[6]的前一个索引值arr[5],参与比较)依次这样进行下去,当碰到索引在中间的时候就算结束了(即是left++>=right–)所以,需要定义左右两个角标;

终于要上代码了:

数组的几种排序方式
数组的几种排序方式

 1        //快速排序
 2     public static void quickSort(int[] arr,int start,int end){
 3         //首先判断,start>=end,就不用比较,即所数组里就一个元素的情况
 4         if(start>=end) return;
 5         //定义一个boolen值,确定是从左往右还是从右往左比较
 6         boolean flag = true;
 7         //然后start<end
 8         while(start<end){
 9             //从左往右比较
10             if(flag){
11                 if(arr[start]>=arr[end]){
12                     int temp = arr[start];
13                     arr[start]=arr[end];
14                     arr[end] = temp;
15                     start++;
16                     flag=false;
17                 }else{
18                     //不交换,那么与倒数第二个比较
19                     end--;
20                 }
21             }else{
22                 //从右往左开始比较
23                 if(arr[start]>=arr[end]){
24                     int temp = arr[start];
25                     arr[start]=arr[end];
26                     arr[end] = temp;
27                     end--;
28                     flag=true;
29                 }else{
30                     //不交换,与索引加1
31                     start++;
32                 }
33             }
34             quickSort(arr,0,start-1);
35             quickSort(arr,start+1,end);
36         }
37     }    

View Code

我靠,竟然写出来了,看来慢慢分析还是有用的,代码有可待优化的地方,暂时这样,更好理解,写的有点啰嗦!

          

 

免责声明:本站所有文章内容,图片,视频等均是来源于用户投稿和互联网及文摘转载整编而成,不代表本站观点,不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益,请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权,请联系删除,如若转载,请注明出处:https://yundeesoft.com/31281.html

(0)

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注

关注微信