冒泡排序的原理-已解决

张_涛

本帖最后由黑马王冬冬于 2012-8-15 10:41 编辑

//建立双层for循环，循环取值
private void Bubble(List<Integer> list){
for(int i = 0;i < (list.size());i++){
for(int j = 0;j < (list.size());j++){
//内存循环取值与外层值进行对比，true则交换两个元素的值
if(list.get(j) > list.get(i)){
Integer in = list.get(j);
list.set(j, list.get(i));
list.set(i, in);
}
}
}
}

复制代码

这是我写的冒泡排序，运转正常，但神奇的是我自己的不明白该程序的原理，哪位同学帮忙分析一下。我很怀疑这是不是冒泡排序，但如果不是的话，它又是如何成功运转的呢？

pphdsny3 · pphdsny3

冒泡排序，形象点说就是像冒泡一样，把大的数或则小的数，像气泡一样慢慢的向上移动，这就把这样的排序叫做冒泡排序
它的原理：
依次比较相邻的两个数，将小数放在前面，大数放在后面
1，在第一趟：首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。至此第一趟结束，将最大的数放到了最后。
2，在第二趟：仍从第一对数开始比较（因为可能由于第2个数和第3个数的交换，使得第1个数不再小于第2个数），将小数放前，大数放后，一直比较到倒数第二个数（倒数第一的位置上已经是最大的），第二趟结束，在倒数第二的位置上得到一个新的最大数（其实在整个数列中是第二大的数）。
3，如此下去，重复以上过程，直至最终完成排序。
由于在排序过程中总是小数往前放，大数往后放，相当于气泡往上升，所以称作冒泡排序

于启会 · 于启会

1、排序方法
　将被排序的记录数组R[1..n]垂直排列，每个记录R[i]看作是重量为R[i].key的气泡。根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R：凡扫描到违反本原则的轻气泡，就使其向上"飘浮"。如此反复进行，直到最后任何两个气泡都是轻者在上，重者在下为止。
（1）初始
　 R[1..n]为无序区。

（2）第一趟扫描
　从无序区底部向上依次比较相邻的两个气泡的重量，若发现轻者在下、重者在上，则交换二者的位置。即依次比较(R[n]，R[n-1])，(R[n-1]，R[n-2])，…，(R[2]，R[1])；对于每对气泡(R[j+1]，R[j])，若R[j+1].key<R[j].key，则交换R[j+1]和R[j]的内容。
　第一趟扫描完毕时，"最轻"的气泡就飘浮到该区间的顶部，即关键字最小的记录被放在最高位置R[1]上。

（3）第二趟扫描
　扫描R[2..n]。扫描完毕时，"次轻"的气泡飘浮到R[2]的位置上……
　最后，经过n-1 趟扫描可得到有序区R[1..n]

　第i趟扫描时，R[1..i-1]和R[i..n]分别为当前的有序区和无序区。扫描仍是从无序区底部向上直至该区顶部。扫描完毕时，该区中最轻气泡飘浮到顶部位置R[i]上，结果是R[1..i]变为新的有序区。

官文昌 · 官文昌

你这好像不是冒泡排序哦，好像是选择排序哦~~
冒泡排序是：相邻的两个元素进行比较，较大的往后移；（a1，a2，a3，a4，a5）它是a1和a2比较，然后a2和呵a3比较，....
选择排序是：前面的元素依次和后面的元素比较，较大的往前面移动，；（a1，a2，a3，a4，a5）,a1和a2比较，a1和呵a3比较，a1和a4比较.....

宫明星 · 宫明星

显然不是冒泡，应该是正常排序

黎健东 · 黎健东

我把冒泡和选择，折半都写了，你对比着看一下

import java.util.Arrays;
import java.util.Random;
public class Sort {
//写冒泡排序的时候，想到还有其他的排序方法，就顺道写了选择排序，折半查找
public static void main(String [] args){
Sort s = new Sort();
int [] arr = s.randomArray();
// //冒泡排序，降序打印
// s.bubbleSortASC(arr);
// //冒泡排序，升序打印
// s.bubbleSortDESC(arr);
//选择排序，升序打印
// s.selectSortAEC(arr);
//优化后的选择排序，降序打印
// s.selectSortOptDESC(arr);
// int [] arr2 = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
// int key = 12;
//自己写的折半查找
// int find = s.halfOfSearch(arr2, key);
//调用API的折半查找
// int find2 = Arrays.binarySearch(arr2, key);
// System.out.println("find: " + find);
// System.out.println("find: " + find2);
}
//打印排序后
public static void sortPrint(int []arr){
System.out.println("sortPrint:");
for(int i : arr){
System.out.print( " " + i + " ");
}
System.out.println("");
}
//打印排序前
public static void beforePrint(int []arr){
System.out.println("beforePrint:");
for(int i : arr){
System.out.print( " " + i + " ");
}
System.out.println("");
}
//随机取值
public int[] randomArray(){
Random r = new Random();
int arrayLength = 10;
int [] arr = new int[arrayLength];
for(int i = 0; i < arrayLength; i++){
arr[i] = r.nextInt(100);
}
beforePrint(arr);
return arr;
}
//交换位置
public static void swap(int a, int b, int []arr){
arr[a] ^= arr[b];
arr[b] ^= arr[a];
arr[a] ^= arr[b];
}
//冒泡排序，升序打印
public void bubbleSortASC(int []arr){
for(int i = 0, len = arr.length; i < len - 1; i++){
for(int j = 0; j < len - i - 1; j++){
if(arr[j] < arr[j + 1]){
swap(j, j + 1, arr);
}
}
}
sortPrint(arr);
}
//冒泡排序，降序打印
public void bubbleSortDESC(int []arr){
for(int i = 0, len = arr.length; i < len - 1; i++){
for(int j = 0; j < len - i - 1; j++){
if(arr[j] > arr[j + 1]){
swap(j, j + 1, arr);
}
}
}
sortPrint(arr);
}
//选择排序，升序打印
public void selectSortAEC(int []arr){
for(int i = 0; i < arr.length - 1; i++){
for(int j = i; j < arr.length - 1; j++){
if(arr[i] > arr[j + 1]){
swap(i, j + 1, arr);
}
}
}
sortPrint(arr);
}
//选择排序，降序打印
public void selectSortDESC(int []arr){
for(int i = 0; i < arr.length - 1; i++){
for(int j = i; j < arr.length - 1; j++){
if(arr[i] < arr[j + 1]){
swap(i, j + 1, arr);
}
}
}
sortPrint(arr);
}
//优化后的选择排序，降序打印
public void selectSortOptDESC(int []arr){
for(int i = 0; i < arr.length - 1; i++){
int num = arr[i];
int index = i;
for(int j = i + 1; j < arr.length; j++){
if(num < arr[j]){
num = arr[j];
index = j;
}
}
if(index != i){
swap(i, index, arr);
}
}
sortPrint(arr);
}
//折半查找
public int halfOfSearch(int [] arr2,int key){
int min = 0;
int max = arr2.length - 1;
int mid;
while(min <= max){
mid = (min + max) >> 1;
if(arr2[mid] < key){
min = mid + 1;
}else if(arr2[mid] > key){
max = mid - 1;
}else{
return arr2[mid];
}
}
return - min - 1;
}
}

复制代码

黑马王冬冬 · 黑马王冬冬

黑马王鹏发表于 2012-8-13 20:32
冒泡排序，形象点说就是像冒泡一样，把大的数或则小的数，像气泡一样慢慢的向上移动，这就把这样的排序叫做 ...

从冒泡排序的定义上来说，这个程序确实不是冒泡排序，但该程序运转正常，我不明白的是该程序是怎样运转的，他是根据什么原理来进行排序的？

黎健东 · 黎健东

黑马王冬冬发表于 2012-8-14 13:39
从冒泡排序的定义上来说，这个程序确实不是冒泡排序，但该程序运转正常，我不明白的是该程序是怎样运转的 ...

你是要明白你的程序是怎么运转的，还是冒泡原理及应用是怎么样的

黑马_许芸 · 黑马_许芸

冒泡排序算法原理
（1）分析
因为每一趟排序都使有序区增加了一个气泡，在经过n-1趟排序之后，有序区中就有n-1个气泡，而无序区中气泡的重量总是大于等于有序区中气泡的重量，所以整个冒泡排序过程至多需要进行n-1趟排序。
若在某一趟排序中未发现气泡位置的交换，则说明待排序的无序区中所有气泡均满足轻者在上，重者在下的原则，因此，冒泡排序过程可在此趟排序后终止。为此，在下面给出的算法中，引入一个布尔量exchange，在每趟排序开始前，先将其置为FALSE。若排序过程中发生了交换，则将其置为TRUE。各趟排序结束时检查exchange，若未曾发生过交换则终止算法，不再进行下一趟排序。

（2）具体算法

  void bubbleSort(int * R, int n)
   { //R[0 .. n-1]是待排序的文件，采用自下向上扫描，对R做冒泡排序
      int i，j；
      Boolean exchange； //交换标志

      for(i=0; i<n-1; i++) //最多做n-1趟排序
      {
            exchange=FALSE； //本趟排序开始前，交换标志应为假

            for(j=n-1; j>i；j--) //对当前无序区R[i .. n-1]自下向上扫描
            {
               if(R[j] < R[j-1]) //交换记录
               {
                  int tmp=R[j-1]； // 暂存单元
                  R[j-1]=R[j]；
                  R[j]=tmp；

                  exchange=TRUE； //发生了交换，故将交换标志置为真
               }
            }
if(!exchange) //本趟排序未发生交换，提前终止算法
               return;

      } //endfor(外循环)
   } //bubbleSort

帐号		自动登录	找回密码
密码			加入黑马

冒泡排序的原理-已解决

评分

8 个回复

评分

评分

评分

评分

黑马骑士勋章