黑马程序员技术交流社区

标题: 选择和冒泡谁的效率高？ [打印本页]

作者: 范国征 时间: 2014-4-17 09:04
标题: 选择和冒泡谁的效率高？
那位大侠，给说一下，选择排序和冒泡排序谁的效率更高一些？求举例。小白谢过了。

作者: ⒈心只霸占沵 时间: 2014-4-17 09:54
应该是选择效率高，看一下比较的次数就知道了，比较次数越多，效率就越低

作者: 陈妙俊 时间: 2014-4-17 09:56
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");
}
}
}

作者: kuroro自走核炮 时间: 2014-4-17 10:07
同样一个数组进行从小到大排为例：
简单选择排序是每次都遍历一遍未排序部分，直接记录最小值的角标值，然后和第一个位置交换。
选择排：
第一轮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

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

作者: 杨庆雷 时间: 2014-4-17 10:15
本帖最后由杨庆雷于 2014-4-17 10:17 编辑

先上代码  冒泡排序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）
结论：选择排序优于冒泡排序  （其实冒泡排序是所有的排序里面效率最低的）

作者: 赵小豪 时间: 2014-4-17 10:29
本帖最后由赵小豪于 2014-4-17 10:33 编辑

public class Sorts {
public static void main(String[] args) {
int arr1[] = { 3, 1, 7, 5, 9, 6 };
int arr2[] = { 6, 2, 8, 3, 9, 5};
long staytime = System.currentTimeMillis();//开始时间
for (int i = 0; i < arr1.length - 1; i++)
for (int j = i + 1; j < arr1.length; j++)
if (arr1[i] > arr1[j])
//调用方法进行交换位置
swap(arr1, i, j);
long endtime = System.currentTimeMillis();//结束时间
System.out.print("\n选择排序：");
//循环输出打印
for (int i : arr1) {
System.out.print(i);
}
System.out.println("选择排序总用\n"+(endtime-staytime)+"毫秒");
long staytime1 = System.currentTimeMillis();//开始时间
for (int i = 0, k; i < arr2.length - 1; i++) {
k = i;
for (int j = i + 1; j < arr2.length; j++)
if (arr2[j] < arr2[k])
k = j;
//调用方法进行交换位置
swap(arr2, i, k);
}
long endtime1 = System.currentTimeMillis();//结束时间
System.out.print("\n冒泡排序：");
//循环输出打印
for (int p : arr2) {
System.out.print(p);
}
System.out.println("\n冒泡排序总用"+(endtime1-staytime1)+"毫秒");
}
/**
* 交换二元素的位置
* @param arr 数组
* @param i 坐标i
* @param j 坐标j
*/
private static void swap(int arr[], int i, int j) {
int temp;
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}

复制代码

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

20140417103204042.jpg (45.68 KB, 下载次数: 44)

作者: 范国征 时间: 2014-4-17 10:31

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

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

作者: 范国征 时间: 2014-4-17 10:34

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

好的，谢谢你。

作者: 范国征 时间: 2014-4-17 10:35

杨庆雷发表于 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:36

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

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

作者: lzhuas 时间: 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:40

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

好的。谢谢啦。

作者: 杨庆雷 时间: 2014-4-17 10:49

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

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

这就是赋值啊
作者: 杨庆雷 时间: 2014-4-17 10:51

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

汗  数据结构挂科了
作者: z1342802487 时间: 2014-4-17 12:16

import java.util.Random

public class Test

{

      public static void main(String[] args)

        {

           Random rdm = new Random();

           int[] arr  = new int[500];

           for (int i = 0; i < arr.length; i++)

{

arr[i]=rdm.nextInt(1000);/生成0到1000的随机数

}

           long starttime1=System.currentTimeMillis();

           bubblesort(arr);

           long endtime1=System.currentTimeMillis();

           System.out.println("冒泡排序时间"+(endtime1-starttime1));

           long starttime2=System.currentTimeMillis();

           selectsort(arr);

           long endtime2=System.currentTimeMillis();

           System.out.println("选择排序时间"+(endtime2-starttime2));

         }

      public static void bubblesort(int[] Arr)

        {

        for(int i = 0;i<Arr.length-1;i++)

        {

        for(int j = i+1;j<Arr.length;j++)

        {

        if(Arr[i]>Arr[j])

        {

        Arr[i]=Arr[i]^Arr[j];

        Arr[j]=Arr[i]^Arr[j];

        Arr[i]=Arr[i]^Arr[j];

        }

        }

        }

        for (int i = 0; i < Arr.length; i++)

{

System.out.print(Arr[i]+" ");

if ((i+1)%10==0)

{

System.out.print("\n");

}

}

        }

      public static void selectsort(int Arr[])

        {

        int minIndex = 0;

        for(int i=0; i<Arr.length; i++)

        {

        minIndex = i;

        for(int j=i+1; j<Arr.length; j++)

        {

        if(Arr[j]<Arr[minIndex])

        {

        minIndex = j;

        }

        }

           if(minIndex!=i)

        {

           Arr[i]= Arr[i]^ Arr[minIndex];

           Arr[minIndex]= Arr[i]^ Arr[minIndex];

           Arr[i]= Arr[i]^ Arr[minIndex];

        }

           }

        for (int i = 0; i < Arr.length; i++)

{

System.out.print(Arr[i]+" ");

if ((i+1)%10==0)

{

System.out.print("\n");

}

}

        }

}
复制代码

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

作者: igi9009 时间: 2014-4-17 15:39
就比较次数而言，选择排序的比较次数是要比冒泡排序要少一点的，就一些比较少的数组来排序的话看不出两者的差别，即使是数组很长的排序两者的差别也不是很大。总的来说就是选择比冒泡要稍微快那么一点点，几乎可以忽略
作者: 天山 时间: 2014-4-17 16:17
还有更快的，快速排序，
作者: 天涯追梦 时间: 2014-4-18 22:43
通常情况下选择排序效率优于冒泡排序，前面的大侠们已经解释的很清楚了，我就不说这两种的效率问题了，下面说一个效率比这两个都要高的排序方法：快速排序
快速排序的基本思想：
      通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分关键字小，则分别对这两部分继续进行排序，直到整个序列有序。

//一个效率较高的排序：快速排序

class Test {

public static void main(String[] args) {

//原始数组

int[] a = { 8, 34, 65, 5, 0, 76, 4, 432, 5 };

System.out.print("未排序数组：");

for (int i : a) {

System.out.print(i+" ");

}

//快速排序

quickSort(a, 0, a.length - 1);

//打印排序后数组

System.out.println();

System.out.print("排序后数组：");

for (int i : a) {

System.out.print(i + " ");

}

}

//通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小

/*定义用于分隔记录的关键字的第一趟排序后的数组位置的方法：把整个序列看做一个数组，把初始位置看做中轴，

和最后一个比，如果比它小交换，比它大不做任何处理；交换了以后再和小的那端比，比它小不交换，比他大交换。

这样循环往复，一趟排序完成，左边就是比中轴小的，右边就是比中轴大的*/

private static int getMid(int[] a, int low, int high) {

//把初始位置看做中轴

int mid = a[low];

//通过while循环移动元素

while (low < high) {

while (low < high && a[high] >= mid) {

high--;

}

a[low] = a[high];//比中轴小的记录移动到低端

while (low < high && a[low] <= mid) {

low++;

}

a[high] = a[low];//比中轴大的记录移动到高端

}

a[low] = mid;//中轴记录到尾

return low;//返回中轴的位置

}

//运用递归的方法，分别对第一趟排序后分隔的两部分记录继续排序，以达到整个序列有序

private static void quickSort(int[] a, int low, int high) {

if (low < high) {

int middle = getMid(a, low, high);

quickSort(a, low, middle - 1);

quickSort(a, middle + 1, high);

}

}

}
复制代码
作者: 四川男人 时间: 2014-4-18 23:53
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()，在冒泡与选择前后调用，差值就可以知道了

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