排序算法之冒泡排序及Java实现

一时失言乱红尘 2022-05-27 14:16 143阅读 0赞

## 一、排序算法的分类 ##

1.  选择排序（[直接选择排序][Link 1]，[堆排序][Link 2]）
2.  交换排序（[冒泡排序][Link 3]，[快速排序][Link 4]）
3.  插入排序（[直接插入排序][Link 5]，[希尔排序][Link 6]）
4.  [归并排序][Link 7]
5.  桶式排序
6.  基数排序

## 二、冒泡排序的原理 ##

冒泡排序需要重复地走访要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，该数列就已经排序完成。

步骤如下所示：

1.  比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2.  对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
3.  针对所有的元素重复以上的步骤，除了最后一个。
4.  持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

## 三、冒泡排序的实现 ##

public class BubbleSort {
        
    
        /**
         * 冒泡排序
         * 每次选择两个相邻的值进行比较，较小的放在前面
         * 第一轮比较时，第一个和第二个比较，第二个和第三个比较，一直到最后一个
         * 第一轮结束，最后一个值为最大值
         * 再进行第二轮比较，比较时，无需再比较最后一个值
         * ...
         * 依次类推，保证每一轮的最后一个值都是最大值，直到没有值再与第一个值比较时，循环结束
         * @param a
         */
        public static void bubSort(int a[]){
    
            for(int i=0; i<a.length; i++){
                //第一轮比较完后，最后一个位置的值为最大值
                //每遍历一轮，最后的位置就能多确定一个
                for(int j=0; j<a.length-i-1; j++){
    
                    int tmp = a[j];//保存a[j]的值，如果比下一个值大，则交换位置
                    if(a[j]>a[j+1]){
                        a[j] = a[j+1];
                        a[j+1] = tmp;
                    }
                }
            }
        }
    
        /**
         * @param args
         */
        public static void main(String[] args) {
            // TODO Auto-generated method stub
            int[] test = {
       5,2,9,4,7,3,1};
            bubSort(test);
            for(int i=0; i<test.length; i++){
                System.out.print(test[i] + " ");
            }
    
        }
    
    }

测试结果：

1 2 3 4 5 7 9

[Link 1]: https://blog.csdn.net/xdzhouxin/article/details/80017538
[Link 2]: https://blog.csdn.net/xdzhouxin/article/details/80079195
[Link 3]: https://blog.csdn.net/xdzhouxin/article/details/80017719
[Link 4]: https://blog.csdn.net/xdzhouxin/article/details/80031668
[Link 5]: https://blog.csdn.net/xdzhouxin/article/details/80024190
[Link 6]: https://blog.csdn.net/xdzhouxin/article/details/80070031
[Link 7]: https://blog.csdn.net/xdzhouxin/article/details/80070839