黑马程序员技术交流社区

标题: 数组排序的时候，选择排序，内循环中的条件表达式，控制不好？ [打印本页]
作者: xiao4236    时间: 2015-1-20 08:34
标题: 数组排序的时候，选择排序，内循环中的条件表达式，控制不好？
请问有什么规律吗？
作者: Lscreat    时间: 2015-1-20 10:15
排序你会用选择和，冒泡就行了，2个格式都蛮固定的，自己多打几次理解就容易了，面试就只针对这2个排序。
作者: 天堂雨    时间: 2015-1-20 10:15
      首先你要先理解选择排序的过程，就是他是什么原理：比如升序（即从小到大），就是从数组的第一个元素开始，分别和后面的元素比较，谁比我小就和我换一下，这样下来，第一个元素就变成了数组中最小的那个了；然后从第二个元素开始继续同第二个元素后面的元素比较，这样找出第二小的值；如此当所有的元素都和其后面的元素比较后，就得到了一个升序数组。
循环写法在后面。。。
作者: 天堂雨    时间: 2015-1-20 10:30
      接下来就是循环该怎么写：外层就从第一个元素开始即x=0，到数组的最后一个值，和里层的比较。（其实不用到最后一个值，因为你前面都把小的挑走了，最后一个一定是最大的，所以x的条件写成x<arr.length或x<arr.length-1都可以，自己写个短的数组模拟下就明白了）
那么里层呢，就是arr[x]以后的值都拿出来和arr[x]比较一遍，谁比他小就和他换一下，就是从x+1一直到最后<arr.length。(这里必须比到<arr.length，因为你得把数组的元素比完了你猜知道谁最大谁最小)
      所以选择循环就是：
for(x=0;x<arr.length-1;x++)  //外面从0到<arr.length-1  (建议这么写，因为可以少循环一次，节约运行资源)
    {
        for(y=x+1;y<arr.length;y++)  //里面从x+1开始到<arr.length即比到最后一个元素
           {
               if(arr[x]>arr[y])
                     交换arr[x]与arr[y]的值；
           }
    }

作者: 老外    时间: 2015-1-20 12:22
for (int x = 0;x<arr.length-1 ;x++ )//x=0 定义x为数组的角标，x<arr.length-1：
                                                  //因为，arr[x]要与arr[y]进行比较，y=x+1，
                                                  //所以x不需要遍历到数组的最后一个元素。x++不需要解释吧！
                {
for (int y =x+1 ;y<arr.length ;y++ )//y=x+1：是要进行x角标与y角标比较，当然，x角标不用于x角标比较，
                                                  //所以y要加1，避免相同的角标相比较。外循环x遍历到了数组的倒数第二
                                                  //     位，那么内循环，y就应该送数组的第二个一直到最后一个！
                        {
                                if (arr[x]>arr[y])//如果想从大到小排序，将>号改为<即可，意思是如果比你小，
我们就换位置
                                {
                                /*
                                int temp = arr[x];
                                arr[x] = arr[y];
                                arr[y] = temp;
                                */
                                swap(arr,x,y);
                                }
                        }
                }
作者: 小棽    时间: 2015-1-21 18:46
本帖最后由 小棽 于 2015-1-21 18:48 编辑

冒泡排序是从第一个开始跟后面比较，如果后面一个比第一个大就交换，接着第二个继续和第三个比较，如果第三个比第二个大，继续交换，以此类推。每一次排序的结果都会把最大的往后面排，直到排序结束。
选择排序是将第一个与后面的每一个值比较，比如第一次与第二个比较，如果大就交换两个数值的位置，然后继续用第一个与三个继续比较，第三个比第一个大就交换位置，反之，就不交换；继续用第一个与后面的比较，以此类推，
下次循环的时候就用第二个与后面的比较，反复前面的比较步骤，直到所有排序结束
不同：冒泡排序每一次的结果是把大的往后面移，选择排序是把小的往前移。
最后我附上代码，你比较一下吧（置换位置的代码还能提取出来重构成单独的方法，减少代码量）
  1. public class Sort {

  3.         public static void main(String[] args) {
  4.                 bubbleSort();
  5.                 System.out.println("--------------------");
  6.                 selectSort();
  7.                
  8.         }
  9.         //冒泡排序
  10.         public static void bubbleSort(){
  11.                 int[] arr = {49,56,12,87,30,25,14};  //定义一个未排序的数组
  12.                 System.out.print("进行未排序前的遍历：");
  13.                 printArray(arr); //遍历数组
  14.                 System.out.println();
  15.                 for(int i = 0; i < arr.length; i++){
  16.                         for(int j = 0; j < arr.length - 1 - i; j++){//没排序完一次，最大的就在最后面，所以不需要再比较，每次就少比较i次
  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.                         System.out.print("第"+(i+1)+"次的结果为：");
  24.                         printArray(arr); //遍历每一次排序的结果
  25.                         System.out.println();
  26.                 }
  27.                
  28.         }
  29.         //选择排序
  30.         public static void selectSort(){
  31.                 int[] arr = {49,56,12,87,30,25,14};
  32.                 System.out.print("进行未排序前的遍历：");
  33.                 printArray(arr); //遍历数组
  34.                 System.out.println();
  35.                 for(int i = 0; i < arr.length; i++){
  36.                         for(int j = i+1; j < arr.length; j++){
  37.                                 if(arr[i] > arr[j]){  
  38.                                         int temp = arr[i];
  39.                                         arr[i] = arr[j];
  40.                                         arr[j] = temp;
  41.                                 }
  42.                         }
  43.                         System.out.print("第"+(i+1)+"次的结果为：");
  44.                         printArray(arr); //遍历每一次排序的结果
  45.                         System.out.println();
  46.                 }
  47.         }
  48.         //打印数组
  49.         public static void printArray(int[] arr){
  50.                 System.out.print("["+arr[0]+",");
  51.                 for(int i = 1; i < arr.length; i++){
  52.                         if( i != arr.length - 1){
  53.                                 System.out.print(arr[i]+",");
  54.                         }else{
  55.                                 System.out.print(arr[i]+"]");
  56.                         }
  57.                 }
  58.         }

  60. }
复制代码




欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2