排序(一)冒泡排序，选择排序

一、冒泡排序

1.1 原理

比较两个相邻的元素，将值大或值小的一方交换到右侧，这样一轮下去最右边的值就会是最大或最小的值。第二次的时候就不需要比较到最后一位置。多次之后即完成排序

1.2 优点

每进行一趟排序，就会少比较一次，因为每进行一趟排序都会找出一个较大值。如上例：第一趟比较之后，排在最后的一个数一定是最大的一个数，第二趟排序的时候，只需要比较除了最后一个数以外的其他的数，同样也能找出一个最大的数排在参与第二趟比较的数后面，第三趟比较的时候，只需要比较除了最后两个数以外的其他的数，以此类推……也就是说，没进行一趟比较，每一趟少比较一次，一定程度上减少了算法的量。

1.3 时间复杂度

  • 1.如果我们的数据正序，只需要走一趟即可完成排序。所需的比较次数C和记录移动次数M均达到最小值，即：Cmin=n-1;Mmin=0;所以，冒泡排序最好的时间复杂度为O(n)。
  • 2.如果很不幸我们的数据是反序的，则需要进行n-1趟排序。每趟排序要进行n-i次比较(1≤i≤n-1)，且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下，比较和移动次数均达到最大值：

img

综上所述：冒泡排序总的平均时间复杂度为：O(n2) ,时间复杂度和数据状况无关。

1.4 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * 置换
 * @param a
 * @param i
 * @param j
 */
public void swap(int[] a , int i , int j){
    int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
}

/**
 * 冒泡排序
 */
void bubbleSort(int[] a){
    for (int i = 0; i < a.length; i++) {
        for (int j = 0 ; j< a.length - i -1 ; j++){
            if (a[j] < a[j+1]){
                swap(a,j,j+1);
            }
        }
    }
}

1.5 改进

对冒泡排序常见的改进方法是加入一标志性变量exchange，用于标志某一趟排序过程中是否有数据交换，如果进行某一趟排序时并没有进行数据交换，则说明数据已经按要求排列好，可立即结束排序，避免不必要的比较过程。本文再提供以下两种改进算法：

  1. 设置一标志性变量pos,用于记录每趟排序中最后一次进行交换的位置。由于pos位置之后的记录均已交换到位,故在进行下一趟排序时只要扫描到pos位置即可。改进后算法如下:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    void Bubble_1 ( int r[], int n) {  
            int i= n -1;  //初始时,最后位置保持不变  
            while ( i> 0) {   
                int pos= 0; //每趟开始时,无记录交换  
                for (int j= 0; j< i; j++)  
                    if (r[j]> r[j+1]) {  
                        pos= j; //记录交换的位置   
                        int tmp = r[j]; r[j]=r[j+1];r[j+1]=tmp;  
                    }   
                i= pos; //为下一趟排序作准备  
             }   
        }

  2. 传统冒泡排序中每一趟排序操作只能找到一个最大值或最小值,我们考虑利用在每趟排序中进行正向和反向两遍冒泡的方法一次可以得到两个最终值(最大者和最小者) , 从而使排序趟数几乎减少了一半。

    改进后的算法实现为

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    void Bubble_2 ( int r[], int n){  
            int low = 0;   
            int high= n -1; //设置变量的初始值  
            int tmp,j;  
            while (low < high) {  
                for (j= low; j< high; ++j) //正向冒泡,找到最大者  
                    if (r[j]> r[j+1]) {  
                        tmp = r[j]; r[j]=r[j+1];r[j+1]=tmp;  
                    }   
                --high;                 //修改high值, 前移一位  
                for ( j=high; j>low; --j) //反向冒泡,找到最小者  
                    if (r[j]<r[j-1]) {  
                        tmp = r[j]; r[j]=r[j-1];r[j-1]=tmp;  
                    }  
                ++low;                  //修改low值,后移一位  
            }

二、选择排序

2.1 原理

第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法。 来源-百度百科

2.2 时间复杂度

选择排序的交换操作介于 0 和 (n - 1） 次之间。选择排序的比较操作为 n (n - 1） / 2 次之间。选择排序的赋值操作介于 0 和 3 (n - 1） 次之间。

比较次数O(n^2），比较次数与关键字的初始状态无关，总的比较次数N=(n-1）+(n-2）+…+1=n*(n-1）/2。交换次数O(n），最好情况是，已经有序，交换0次；最坏情况交换n-1次，逆序交换n/2次。交换次数比冒泡排序少多了，由于交换所需CPU时间比比较所需的CPU时间多，n值较小时，选择排序比冒泡排序快。 [1]

2.3 稳定性

选择排序是给每个位置选择当前元素最小的，比如给第一个位置选择最小的，在剩余元素里面给第二个元素选择第二小的，依次类推，直到第n-1个元素，第n个元素不用选择了，因为只剩下它一个最大的元素了。那么，在一趟选择，如果一个元素比当前元素小，而该小的元素又出现在一个和当前元素相等的元素后面，那么交换后稳定性就被破坏了。比较拗口，举个例子，序列5 8 5 2 9，我们知道第一遍选择第1个元素5会和2交换，那么原序列中两个5的相对前后顺序就被破坏了，所以选择排序是一个不稳定的排序算法。 [1] –百度百科

2.4 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
 * 选择排序
 * @param a
 */
public void choseSort(int[] a){
    int i,j ;
    for (i = 0; i < a.length; i++) {
        for (j = i + 1 ; j<a.length ;j++){
            if (a[i] > a[j]){
                swap(a,i,j);
            }
        }
    }
}