黑马程序员技术交流社区

标题: 选择和冒泡 [打印本页]

作者: 晴天_雨天 时间: 2014-3-6 13:08
标题: 选择和冒泡
在选择排序和冒泡排序中，哪个效率要高点？

作者: Aimer_WJY 时间: 2014-3-6 13:34
基本上差不多，因为都要进行数据位置的互换，在数据很多的时候，觉得效率都比较低。

作者: My_work 时间: 2014-3-6 13:59
选择排序

1. 基本思想：
　　每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。
2. 排序过程：
【示例】：
初始关键字 [49 38 65 97 76 13 27 49]
第一趟排序后 13 ［38 65 97 76 49 27 49]
第二趟排序后 13 27 ［65 97 76 49 38 49]
第三趟排序后 13 27 38 [97 76 49 65 49]
第四趟排序后 13 27 38 49 [49 97 65 76]
第五趟排序后 13 27 38 49 49 [97 97 76]
第六趟排序后 13 27 38 49 49 76 [76 97]
第七趟排序后 13 27 38 49 49 76 76 [ 97]
最后排序结果 13 27 38 49 49 76 76 97

Procedure SelectSort(Var R : FileType); //对R[1..N]进行直接选择排序 //
Begin
   for I := 1 To N - 1 Do //做N - 1趟选择排序//
   begin
   K := I;
   For J := I + 1 To N Do //在当前无序区R[I..N]中选最小的元素R[K]//
      begin
      If R[J] < R[K] Then K := J
      end;
   If K <> I Then //交换R[I]和R[K] //
      begin Temp := R[I]; R[I] := R[K]; R[K] := Temp; end;
   end
End; //SelectSort //

冒泡排序(BubbleSort)

1. 基本思想：
　　两两比较待排序数据元素的大小，发现两个数据元素的次序相反时即进行交换，直到没有反序的数据元素为止。
2. 排序过程：
　　设想被排序的数组R［1..N］垂直竖立，将每个数据元素看作有重量的气泡，根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R，凡扫描到违反本原则的轻气泡，就使其向上"漂浮"，如此反复进行，直至最后任何两个气泡都是轻者在上，重者在下为止。
【示例】：
49 13 13 13 13 13 13 13
38 49 27 27 27 27 27 27
65 38 49 38 38 38 38 38
97 65 38 49 49 49 49 49
76 97 65 49 49 49 49 49
13 76 97 65 65 65 65 65
27 27 76 97 76 76 76 76
49 49 49 76 97 97 97 97
Procedure BubbleSort(Var R : FileType) //从下往上扫描的起泡排序//
Begin
For I := 1 To N-1 Do //做N-1趟排序//
begin
   NoSwap := True; //置未排序的标志//
   For J := N - 1 DownTo 1 Do //从底部往上扫描//
   begin
      If R[J+1]< R[J] Then //交换元素//
      begin
      Temp := R[J+1]; R[J+1 := R[J]; R[J] := Temp;
      NoSwap := False
      end;
   end;
   If NoSwap Then Return//本趟排序中未发生交换，则终止算法//
   end
End; //BubbleSort//

(1) 若n较小(n <= 50)，则可以采用直接插入排序或直接选择排序。由于直接插入排序所需的记录移动操作较直接选择排序多，因而当记录本身信息量较大时，用直接选择排序较好。
(2) 若文件的初始状态已按关键字基本有序，则选用直接插入或冒泡排序为宜。

快速排序是目前基于比较的内部排序法中被认为是最好的方法。
基本思想：
　　在当前无序区R[1..H]中任取一个数据元素作为比较的"基准"(不妨记为X)，用此基准将当前无序区划分为左右两个较小的无序区：R[1..I-1]和R[I+1..H]，且左边的无序子区中数据元素均小于等于基准元素，右边的无序子区中数据元素均大于等于基准元素，而基准X则位于最终排序的位置上，即R[1..I-1]≤X.Key≤R[I+1..H](1≤I≤H)，当R[1..I-1]和R[I+1..H]均非空时，分别对它们进行上述的划分过程，直至所有无序子区中的数据元素均已排序为止。

作者: chen_x 时间: 2014-3-6 14:12
效率没有本质差别，平均时间复杂度都是n的平方数量级的
一般的选择排序和冒泡排序都是要比较(n*(n-1))/2次，算法效率要看执行的交换次数多少，这应该与数组的数据分布状况有关，没深入研究过
其实也不必纠结于这种算法的效率吧~，效率都不高，大数据量情况直接使用java提供Array.sort()方法。

作者: xiaochen33520 时间: 2014-3-6 16:19
选择排序和冒泡排序，根据我所学的知识认为选择排序效率要高一点，因为选择排序经过优化以后每轮比完可以只交换一次。而冒泡排序优化后是什么样我不知道，所以根据我所学的知识认为选择排序效率要略高。

作者: syw02014 时间: 2014-3-6 19:23

冒泡排序：它的时间复杂度为O（n^2），虽然不及堆排序、快速排序的O（nlogn，底数为2），但是有两个优点：

1.“编程复杂度”很低，很容易写出代码；
2.具有稳定性，这里的稳定性是指原序列中相同元素的相对顺序仍然保持到排序后的序列，而堆排序、快速排序均不具有稳定性。不过，一路、二路归并排序、平衡二叉树排序的速度均比冒泡排序快，且具有稳定性，但速度不及堆排序、快速排序。
基本概念是：依次比较相邻的两个数，将小数放在前面，大数放在后面。即在第一趟：首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。至此第一趟结束，将最大的数放到了最后。在第二趟：仍从第一对数开始比较（因为可能由于第2个数和第3个数的交换，使得第1个数不再小于第2个数），将小数放前，大数放后，一直比较到倒数第二个数（倒数第一的位置上已经是最大的），第二趟结束，在倒数第二的位置上得到一个新的最大数（其实在整个数列中是第二大的数）。如此下去，重复以上过程，直至最终完成排序。

public static int[] 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])
{
int temp;
temp=arr[j];
arr[j]=arr[i];
arr[i]=temp;
}
}
}
return arr;
}

复制代码

简单选择排序：
在简单选择排序过程中，所需移动记录的次数比较少。最好情况下，即待排序记录初始状态就已经是正序排列了，则不需要移动记录。最坏情况下，即待排序记录初始状态是按逆序排列的，则需要移动记录的次数最多为3（n-1）。简单选择过程中需要进行的比较次数与初始状态下待排序的记录序列的排列情况无关。当i=1时，需进行n-1次比较；当i=2时，需进行n-2次比较；依次类推，共需要进行的比较次数是∑ =(n-1)+(n-2)+…+2+1=n(n-1)/2，即进行比较操作的时间复杂度为O(n2)。这种方法其实是对冒泡排序的深入。

public static int[] selectSort(int[] arr)
{
for(int i=0;i<arr.length-1;i++)
{
int min = i;
for (int j=i+1;j<arr.length;j++)
{
if(arr[min]>arr[j])
min = j;
}
if(min!=i)
{
int temp = arr[i];
arr[i] = arr[min];
arr[min] = temp;
}
}
return arr;
}

复制代码

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

黑马程序员IT技术论坛 X3.2