java中的冒泡排序和选择排序

• 前言
• 一、冒泡排序
• • 1.原理
  • 2.排序算法
  • 2.缺点
• 二、选择排序
• • 1.原理
  • 2.排序算法
  • 2.优化方案
• 总结

排序的方法有很多种，一些耳熟能详的诸如选择排序、冒泡排序、插入排序、快速排序等等，以及一些对于像我这样的新手的稍显陌生的像是希尔排序、归并排序、基数排序等等，这里不多做赘述。
此文主要归纳个人学习java历程中的一些所获，本人才疏学浅，如有谬误，敬请指正。

冒泡排序是一种较为简单的排序算法，它的思路也比较简单，就是从前往后依次比较相邻的两个元素，如果前一个元素比后一个元素大的话，就将前一个元素与后一个元素交换，这样一轮下来，数组中最大的元素就会到最后一个去。如此往复，最终就能完成排序。

冒泡排序的方法如下：

static void bubbleSort(int[] arr) {
        for( int c = 1; c  arr[index + 1] ) {//判断相邻的数的大小
                    swap(arr,index,index + 1);//交换元素
                }
            }
        }
    }

交换元素所调用的方法：

static void swap(int[] arr,int index1,int index2) {
        int temp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = temp;
    }

冒泡排序的效率是极低的，最笨的方式是每个轮次都与后面的元素一一比较，但我们要知道，毎比较一轮，每轮相对的最大值就会换到最后去，这样剩余的元素继续往后比较，就会极大的降低效率。
这里有一个小小的优化方案，每轮比较只与尚未排完序的元素比较：

static void bubbleSort(int[] arr) {
        for( int c = 1; c  arr[index + 1] ) {//判断相邻的数的大小
                    swap(arr,index,index + 1);
                }
            }
        }
    }

但这依旧改变不了冒泡排序效率低下的事实。

选择排序就是第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。（源自百度）
简而言之，就是在没有排序的元素中，找出最小（大）的元素放在开头（末尾），每趟排序只需要在更少的元素中找寻一个最小（大）值，如此往复，既能完成排序。

选择排序算法如下：

    static void selectionSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        for( int sel = 0; sel < arr.length - 1; sel ++ ) {
            int minIndex = sel;
            for( int index = sel + 1; index < arr.length; index ++ ) {
                if( arr[minIndex] > arr[index] ) {
                    minIndex = index;
                }
            }
            swap(arr,sel,minIndex);
        }
    }

每次遍历的时候都找出其中最小值和最大值，并排定最小值和最大值，这样需要遍历的次数就会减少一半，优化后的算法如下：

    static void selectionSort( int[] arr ) {
        int minIndex;
        int maxIndex;
        for( int i = 0; i < arr.length; i ++ ) {
            minIndex = i;
            maxIndex = arr.length - i - 1;
            for( int k = i; k < arr.length - i; k ++ ) {
                if (arr[minIndex] > arr[k]) {
                    minIndex = k;
                }
            }
            swap(arr, minIndex, i);
            for( int k = i; k < arr.length - i; k ++ ) {
                if (arr[maxIndex] < arr[k]) {
                    maxIndex = k;
                }
            }
            swap(arr, maxIndex, arr.length - i - 1);
        }
    }

排序算法虽然在实际开发的过程中几乎不会需要我们自己去编写（因为jdk内部为我们提供的排序算法更为高效），但细细去体会排序过程中的那种思路，对于我们的算法思维的提升还是很有帮助的。