大话数据结构13-排序1

发表于 更新于 分类于 ， Valine：

通常，我们将一组一组的数据称为记录，排序，则是将这些记录按照一定的顺序进行排列。通常，我们选取记录中的某一关键字（主、次关键字皆可）作为排序的依据，按照关键字之间的大小关系对记录进行排序。

0. 排序的基本概念与分类

在排序的过程中，由于关键字可能相等，因而排序结果可能出现不唯一的情况。因此，我们定义 排序的稳定性 的概念：

假设关键字 $k_i = k_j, (1\leq i\leq n, 1\leq j \leq n, i\neq j)$,且在排序前的序列中 $r_i$ 领先于 $r_j$ （i.e. $i<j$）,如果排序后 $r_i$ 仍然领先于 $r_j$，则称所用的排序方法是稳定的；反之，若可能使得排序后的序列中 $r_j$ 领先于 $r_i$, 则称所用的排序方法是不稳定的。

对于在实际的计算机系统中运行的算法，我们根据排序过程中的记录是否全部放置在内存中将排序分为：内排序和外排序。外排序是由于排序的记录个数太多，不能将数据完全放置在内存中，在排序过程中，还需要与外存进行数次的数据交换。简单起见，我们这里主要关注内排序-即所有的排序对象都存储在内存之中。

那么，排序的性能具体受哪些因素的影响，这里分析主要的影响因素如下：

  • 时间性能。排序操作的核心是数据间的比较和数据的移动，高效的排序算法要求尽可能少的比较次数和记录移动次数。
  • 辅助空间的使用。

根据排序中借助的主要操作，我们将内排序分为：插入排序，交换排序，选择排序 和 归并排序。

下文，具体介绍了7中排序方法， 其中 冒泡排序，简单选择排序 和直接插入排序属于简单方法；希尔排序，堆排序，归并排序，快速排序则属于改进算法。我们分别对之进行介绍。

在介绍之之前，为了减少重复代码，我们首先写一个 swap 函数，如下：

1
2
3
4
5
public static void swap(int[] array, int i, int j){
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp; 
}

I. 冒泡排序

最经典的一个排序算法，下面提供了两种实现，我们直接看代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
public static int[] bubble_sort0(int[] array){
    int CompareTimes = 0;
    if(array.length == 0)
        return array;
    for (int i = 0; i < array.length; i++){                                      
        for(int j = 0; j < array.length - i - 1; j++){      
            CompareTimes++;
            if(array[j] > array[j+1]){
                swap(array, j, j+1);
            }                    
        }
    }
    System.out.println("初级冒泡排序的比较次数：" + CompareTimes);
    return array;
}
//改进版冒泡
public static int[] bubble_sort1(int[] array){
    boolean flag = true;        
    //如果一次外循环结束，没有进行任何 swap，说明已经排序完毕，即退出循环
    int CompareTimes = 0;
    if(array.length == 0)
        return array;
    for (int i = 0; i < array.length && flag; i++){
        flag = false;                                       
        for(int j = 0; j < array.length - i - 1; j++){    
            CompareTimes++;
            if(array[j] > array[j+1]){
                swap(array, j, j+1);
                flag = true;
            }      
        }
    }
    System.out.println("改进版冒泡排序的比较次数：" + CompareTimes);
    return array;
}

以上两种实现，bubble_sort1 在 bubble_sort0 的基础上添加了一个排序完成的判定符，使得当系统一旦已经完成排序，再最后多进一次循环，即可提前结束程序。

时间复杂度：最佳 $O(n)$, 最差$O(n^2)$, 平均 $O(n^2)$。

II. 简单选择排序

冒泡排序法通过非常多的交换最终完成排序，因此，不仅有较高的比较开销，交换操作也带来很大的额外开销。是否有办法减少交换次数，快速的完成关键位序的定位？简单选择排序（simple selection sort）提供了一种思路。

简单选择算法首先寻找整个数组中最小的数，放在数组第一个，然后寻找次小的，放在第二个，… 直到外循环遍历完整个数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public static int[] selectsort(int[] array){
    if(array.length == 0)
        return array;
    int min = 0;
    int compareTimes = 0;
    int swapTimes = 0;
    for(int i = 0; i < array.length; i++){
        min = i;
        for(int j = i+1; j < array.length; j++){    //找到array[i]后面最小的值
            compareTimes++;
            if(array[min] > array[j])
                min = j;
        }
        if(min != i){
            swap(array, i, min);        
            // 将 array[i] 后面最小的值的元素与 array[i]交换位置
            swapTimes++;
        }
    }
    System.out.println("Select sort 的比较次数为：" + compareTimes);
    System.out.println("Select sort 的交换次数为：" + swapTimes);
    return array;
}

总的来说，选择排序的时间复杂度为 $O(n^2)$。但相比冒泡排序，他们的比较次数相同，而交换次数 选择排序 最好情况为$O(0)$，最差情况为 $O(n-1)$，优于冒泡排序法。

III. 直接插入排序

直接插入法（straight inserton sort）的核心思想是向一个已经排好序的队列中插入一个新的数字。从第一个数字开始处理，认为第一个数字是排序好的，判断第二个数字应该插在第一个数字的前面还是后面。然后判断第3个数字应该插在 第1-2个数字组成的有序数列的什么位置（需要注意的是，由于有了前面分析第二个数字插入的位置的步骤，所以这里的第1-2个数字是已经有序的）。最后依次向后进行判断。具体代码入下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class InsertSort {    
    public static int[] insert_sort(int[] array){
        if(array.length == 0)
            return array;        
        for(int i = 0; i < array.length - 1; i++){
            int temp = array[i+1];
            int index = i;
            while(index >= 0 && temp < array[index]){     
                //从最大的开始比，寻找插入 temp 的合适位置。
                array[index+1] = array[index];
                index --;
            }
            array[index+1] = temp;
        }
        return array;
    }
}

Note: 需要小心的是，while 中的判定条件 index >= 0 && temp < array[index] 不能写成 temp < array[index] && index >= 0 ， 否则的话会报数组越界的错误。Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index -1 out of bounds for length 6.

该种算法在最好的情况下时间复杂度为 $O(n)$, 而最坏的情况的时间复杂度则为 $O(n^2)$（平均次数为 $n^2/4$ 次）。但整体上，效率要优于冒泡排序法。

部分代码参考: 郭耀华’s Blog. thx~