那位大侠，给说一下，选择排序和冒泡排序谁的效率更高一些？求举例。小白谢过了。

public static void maopao(int[] arr)//冒泡排序
{
  for (int x=0; x<arr.length-1; x++)
  {
   for (int y=0; y<arr.length-1-x; y++ )
   {
    if (arr[y]>arr[y+1])
    {
     int temp = arr[y];
     arr[y] = arr[y+1];
     arr[y+1] = temp;
     }
   }
  }
}
public static void xuanze(int[] arr)//选择排序
{
  for (int x=0; x<arr.length; x++)
  {
   for (int y=x; y<arr.length; y++ )
   {
    if (arr[x]>arr[y])
    {
     int temp = arr[x];
     arr[x] = arr[y];
     arr[y] = temp;
     }
   }
  }
}
然后调用Time 的方法getTime()，在冒泡与选择前后调用，差值就可以知道了

通常情况下选择排序效率优于冒泡排序，前面的大侠们已经解释的很清楚了，我就不说这两种的效率问题了，下面说一个效率比这两个都要高的排序方法：快速排序
快速排序的基本思想：
         通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分关键字小，则分别对这两部分继续进行排序，直到整个序列有序。

1. //一个效率较高的排序：快速排序
   
2. class Test {
   
3.         public static void main(String[] args) {
   
4.                 //原始数组
   
5.                 int[] a = { 8, 34, 65, 5, 0, 76, 4, 432, 5 };
   
6.                 System.out.print("未排序数组：");
   
7.                 for (int i : a) {
   
8.                         System.out.print(i+"   ");
   
9.                 }
   
10.                 //快速排序
    
11.                 quickSort(a, 0, a.length - 1);
    
12.                 //打印排序后数组
    
13.                 System.out.println();
    
14.                 System.out.print("排序后数组：");
    
15.                 for (int i : a) {
    
16.                         System.out.print(i + "   ");
    
17.                 }
    
18.         }
    
19. 
    
20. //通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小
    
21.         /*定义用于分隔记录的关键字的第一趟排序后的数组位置的方法：把整个序列看做一个数组，把初始位置看做中轴，
    
22.         和最后一个比，如果比它小交换，比它大不做任何处理；交换了以后再和小的那端比，比它小不交换，比他大交换。
    
23.         这样循环往复，一趟排序完成，左边就是比中轴小的，右边就是比中轴大的*/
    
24.         private static int getMid(int[] a, int low, int high) {
    
25.                 //把初始位置看做中轴
    
26.                 int mid = a[low];
    
27.                 //通过while循环移动元素
    
28.                 while (low < high) {
    
29.                         while (low < high && a[high] >= mid) {
    
30.                                 high--;
    
31.                         }
    
32.                         a[low] = a[high];//比中轴小的记录移动到低端
    
33.                         while (low < high && a[low] <= mid) {
    
34.                                 low++;
    
35.                         }
    
36.                         a[high] = a[low];//比中轴大的记录移动到高端
    
37.                 }
    
38.                 a[low] = mid;//中轴记录到尾
    
39.                 return low;//返回中轴的位置
    
40.         }
    
41. //运用递归的方法，分别对第一趟排序后分隔的两部分记录继续排序，以达到整个序列有序
    
42.         private static void quickSort(int[] a, int low, int high) {
    
43.                 if (low < high) {
    
44.                         int middle = getMid(a, low, high);
    
45.                        
    
46.                         quickSort(a, low, middle - 1);
    
47.                         quickSort(a, middle + 1, high);
    
48.                 }
    
49.         }
    
50. }

复制代码

还有更快的， 快速排序，

就比较次数而言，选择排序的比较次数是要比冒泡排序要少一点的，就一些比较少的数组来排序的话看不出两者的差别，即使是数组很长的排序两者的差别也不是很大。总的来说就是选择比冒泡要稍微快那么一点点，几乎可以忽略

选择...

1. import java.util.Random
   
2. public class Test
   
3.         {
   
4.         public static void main(String[] args)
   
5.                 {
   
6.                          Random rdm = new Random();
   
7.                          int[] arr  = new int[500];
   
8.                          for (int i = 0; i < arr.length; i++)
   
9.                                         {
   
10.                                                 arr[i]=rdm.nextInt(1000);/生成0到1000的随机数
    
11.                                         }
    
12.                          long starttime1=System.currentTimeMillis();
    
13.                          bubblesort(arr);
    
14.                          long endtime1=System.currentTimeMillis();
    
15.                          System.out.println("冒泡排序时间"+(endtime1-starttime1));
    
16.                          long starttime2=System.currentTimeMillis();
    
17.                          selectsort(arr);
    
18.                          long endtime2=System.currentTimeMillis();
    
19.                          System.out.println("选择排序时间"+(endtime2-starttime2));
    
20.             }
    
21. 
    
22.         public static void bubblesort(int[] Arr)
    
23.                 {
    
24.                         for(int i = 0;i<Arr.length-1;i++)
    
25.                                 {
    
26.                                         for(int j = i+1;j<Arr.length;j++)
    
27.                                                 {
    
28.                                                         if(Arr[i]>Arr[j])
    
29.                                                                 {
    
30.                                                                         Arr[i]=Arr[i]^Arr[j];
    
31.                                                                         Arr[j]=Arr[i]^Arr[j];
    
32.                                                                         Arr[i]=Arr[i]^Arr[j];
    
33.                                                                 }
    
34.                                                 }
    
35.                                 }
    
36.                         for (int i = 0; i < Arr.length; i++)
    
37.                                         {
    
38.                                                 System.out.print(Arr[i]+" ");
    
39.                                                 if ((i+1)%10==0)
    
40.                                                         {
    
41.                                                                 System.out.print("\n");
    
42.                                                         }
    
43.                                         }
    
44.                 }
    
45.         public static void selectsort(int Arr[])
    
46.                 {
    
47.                         int minIndex = 0;
    
48.                         for(int i=0; i<Arr.length; i++)
    
49.                                 {
    
50.                                         minIndex = i;
    
51.                                         for(int j=i+1; j<Arr.length; j++)
    
52.                                                 {
    
53.                                                         if(Arr[j]<Arr[minIndex])
    
54.                                                                 {
    
55.                                                                         minIndex = j;
    
56.                                                                 }
    
57.                                                 }
    
58.                                           if(minIndex!=i)
    
59.                                                 {
    
60.                                                          Arr[i]= Arr[i]^ Arr[minIndex];
    
61.                                                          Arr[minIndex]= Arr[i]^ Arr[minIndex];
    
62.                                                          Arr[i]= Arr[i]^ Arr[minIndex];
    
63.                                                 }
    
64.                                   }
    
65.                         for (int i = 0; i < Arr.length; i++)
    
66.                                         {
    
67.                                                 System.out.print(Arr[i]+" ");
    
68.                                                 if ((i+1)%10==0)
    
69.                                                         {
    
70.                                                                 System.out.print("\n");
    
71.                                                         }
    
72.                                         }
    
73.                 }
    
74.    }

复制代码

不难发现，冒泡和选择排序在比较次数上都是固定的n*(n-1)/2。 冒泡排序是每一次都可能要交换，而选择排序是在比较时记下a的位置 最后来交换，所以他们的交换次数是不一样的，而比较的过程是一样的 选择排序效率不会比冒泡的低。下面是我对长度为500的数组排序代码

lzhuas 发表于 2014-4-17 10:36
哥们是学过数据结构的呀

汗  数据结构挂科了

范国征 发表于 2014-4-17 10:35
大侠，什么是赋值的次数？

temp = arr;
arr = arr[j];
arr[j] = temp;

这就是赋值啊

赵小豪 发表于 2014-4-17 10:36
你再多添加元素，用毫秒去计算，如果毫秒不成改用微秒试试
一般都是选择，因为选择它是确定位置再进行交 ...

好的。谢谢啦。

杨庆雷 发表于 2014-4-17 10:15
先上代码  冒泡排序for (int i = 0; i < size; i++) {
for (int j = 0; j < size - i - 1; j++) {
if (num[ ...

哥们是学过数据结构的呀:handshake

范国征 发表于 2014-4-17 10:31
谢谢你，不过我知道代码，就是不知道那一个效率高一些。

你再多添加元素，用毫秒去计算，如果毫秒不成改用微秒试试
一般都是选择，因为选择它是确定位置再进行交换。相对来说效率要高

杨庆雷 发表于 2014-4-17 10:15
先上代码  冒泡排序for (int i = 0; i < size; i++) {
for (int j = 0; j < size - i - 1; j++) {
if (num[ ...

大侠，什么是赋值的次数？

赵小豪 发表于 2014-4-17 10:29
总的来说，两种排序比较的次数是相同的
但交换的次数，选择排序是更少的
虽然两者的时间复杂度都是 O（n ...

好的，谢谢你。

陈妙俊 发表于 2014-4-17 09:56
public class ArraysTest2 {
        public static void main (String[] args){
                int[] arr={5,1,4,2,6,8,9,3};

谢谢你，不过我知道代码，就是不知道那一个效率高一些。

1. public class Sorts {
   
2.         public static void main(String[] args) {
   
3.                 int arr1[] = { 3, 1, 7, 5, 9, 6 };
   
4.                 int arr2[] = { 6, 2, 8, 3, 9, 5};
   
5.                 long staytime = System.currentTimeMillis();//开始时间
   
6.                 for (int i = 0; i < arr1.length - 1; i++)
   
7.                         for (int j = i + 1; j < arr1.length; j++)
   
8.                                 if (arr1[i] > arr1[j])
   
9.                                         //调用方法进行交换位置
   
10.                                         swap(arr1, i, j);
    
11.                 long endtime = System.currentTimeMillis();//结束时间
    
12.                 System.out.print("\n选择排序：");
    
13.                 //循环输出打印
    
14.                 for (int i : arr1) {
    
15.                         System.out.print(i);
    
16.                 }
    
17. System.out.println("选择排序总用\n"+(endtime-staytime)+"毫秒");
    
18. 
    
19. long staytime1 = System.currentTimeMillis();//开始时间
    
20.                 for (int i = 0, k; i < arr2.length - 1; i++) {
    
21.                         k = i;
    
22.                         for (int j = i + 1; j < arr2.length; j++)
    
23.                                 if (arr2[j] < arr2[k])
    
24.                                         k = j;
    
25.                         //调用方法进行交换位置
    
26.                         swap(arr2, i, k);
    
27. 
    
28.                 }
    
29.                 long endtime1 = System.currentTimeMillis();//结束时间
    
30.                 System.out.print("\n冒泡排序：");
    
31.                 //循环输出打印
    
32.                 for (int p : arr2) {
    
33.                         System.out.print(p);
    
34.                 }
    
35.                 System.out.println("\n冒泡排序总用"+(endtime1-staytime1)+"毫秒");
    
36.         }
    
37. /**
    
38. * 交换二元素的位置
    
39. * @param arr  数组
    
40. * @param i  坐标i
    
41. * @param j 坐标j
    
42. */
    
43.         private static void swap(int arr[], int i, int j) {
    
44.                 int temp;
    
45.                 temp = arr[i];
    
46.                 arr[i] = arr[j];
    
47.                 arr[j] = temp;
    
48.         }
    
49. }

复制代码

总的来说，两种排序比较的次数是相同的
但交换的次数，选择排序是更少的
虽然两者的时间复杂度都是 O（n^2)
但通常，选择排序更快一点
在这本想通过毫秒计算谁要快，但是元素太少计算都是0毫秒
你可以试试在元素很多的情况下谁快

先上代码  冒泡排序for (int i = 0; i < size; i++) {
for (int j = 0; j < size - i - 1; j++) {
if (num[j < num[j + 1]) {
int temp = num[j];
num[j = num[j + 1];
num[j + 1 = temp;
}
}
}选择排序for (int j = i + 1; j < size; j++) {
    if (num[j] < num[min]) {
     min = j;
    }
   }


   num = num[min];
   num[min] = temp;
  }
两种方法的比较次数 上来说 都是 1 + 2 + 3 + ...+ (n -1) = n * (n - 1)/2  他们的复杂度都是 O(n^2)但是赋值的次数是不一样的  冒泡排序：3n*(n-1)/2  选择排序：n*(n-1)/2+2n  在赋值方面选择排序更优（至于为什么都除以2  是因为每组数我们都看成是随机的  那么每次比较就会有1/2率大，1/2几率小，所以要除以2）
结论：选择排序优于冒泡排序  （其实冒泡排序是所有的排序里面效率最低的）

同样一个数组进行从小到大排为例：
简单选择排序是每次都遍历一遍未排序部分，直接记录最小值的角标值，然后和第一个位置交换。
选择排：
第一轮1,[6,8,5,7,2,9,4,3]
第二轮1,2,[6,8,5,7,9,4,3]
第三轮1,2,3,[6,8,5,7,9,4,]
第四轮1,2,3,4,[6,8,5,7,9,]
……
然后到1,2,3,4,5,6,7,8,9

冒泡模式则是第一个和第二个比较，如果前一个比后面大，交换。这样操作下去。
两个相比的话会发现，从比较的次数来说，两种排序方法是一样的。但是交换次数来说，选择比冒泡的交换次数一般来说是要少的。所以我觉得选择排序一般效率应该稍微高一点。

public class ArraysTest2 {
        public static void main (String[] args){
                int[] arr={5,1,4,2,6,8,9,3};
                 selectSort(arr);
                 System.out.println();
                 bubbleSort(arr);
        }
        //选择排序：让一个数和后面的每个数比较，这样第一次比较就可以找出最小值
        public static void selectSort(int[] arr){
                for(int x=0;x<arr.length -1;x++){
                        for(int y=x+1;y<arr.length;y++){
                                if(arr[x]>arr[y]){
                                        int temp=arr[x];
                                        arr[x]=arr[y];
                                        arr[y]=temp;
                                }
                        }
                        System.out.print(arr[x]+"\t");
                }
        }


        //冒泡排序，相邻两个元素比较，符合条件换位：
        public static void bubbleSort(int[] arr){
                for(int x=0;x<arr.length -1;x++){
                        for(int y=x+1;y<arr.length-x-1;y++){
                                if(arr[y]>arr[y+1]){
                                        int temp=arr[y];
                                        arr[y]=arr[y+1];
                                        arr[y+1]=temp;
                                }
                        }
                        System.out.print(arr[x]+"\t");
                }
        }
}       
       
       
       

应该是选择效率高，看一下比较的次数就知道了，比较次数越多，效率就越低