基本排序算法

算法总是学学忘忘，不过在遇到一些深入点的问题不理解其背后的原理就比较尴尬了。所以打算重新拾起这一部分，从基础的开始去了解一些其他的算法。从第一堂课开始就是学的排序，因此也将排序作为一个开始吧。

几个基本的排序算法

选择排序

选择排序的思想是从列表中不断的找出最小（大）的值，来依次排列到列表左侧，当移动到最右端的时候排序就完成了。对于一个长度为N的数组，选择排序大约需要进行N²/2次比较合N次交换。

在最坏的情况下，每一个数都不再其应该在的位置上，则每个数都会发生交换。对于比较次数，比如恰好是一个逆序数组，则每次都需要比较到末尾才能找到最大（小）值，因此比较次数为(N-1)+(N-2)+…+2+1 = N(N-1)/2 约为N²/2

简单实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
    * 选择排序
    * @param a
    */
   public static void selectionSort(int[] a){      
       int length = a.length;
       for(int i=0;i<length;i++){
           int min = i;
           //内层循环负责找出后续元素最小的
           for(int j=i;j<length;j++){
               if(a[j]<a[min]){
                   min = j;
               }
           }
           int temp = a[i];
           a[i] = a[min];
           a[min] = temp;
       }
   }

选择排序的特点：输入与其排序时间无关。内层每一次循环仅对当前一次有效，即使对于一个有序、随机或者元素都相同的数组它使用的时间可能一样长。另外它对元素的移动次数是最少的。每一次交换将改变两个元素的位置，改变的次数与元素个数呈线性关系，这是很多其他算法所不具有的。

插入排序

插入排序就是针对下标的左侧进行操作，每向前移动一位，就和前面的元素进行比较并把它放在合适的位置，和选择排序一样，插入排序的左侧始终保持有序。但在排序完成之前，将不会扫描到右侧的数据，当下标移动到右侧的时候，排序就完成了。对于长度为N的数组，平均一次排序需要N²/4次比较和N²/4次交换，最坏的情况下需要N²/2次比较和N²/2次交换，最好的情况下需要N-1次比较和0次交换。

最坏的情况下每一个元素都将会和前面所有元素发生比较和交换（如逆序）因此交换比较的次数都为(N-1)+(N-2)+…+2+1 = N(N-1)/2 ~=N²/2, 一般情况下，每个元素都有可能向后移动半个数组，花费大约为最坏的一半，最好的情况下，数组已经有序，因此只需要N-1次比较就能发现数组已经有序且不发生交换。

简单实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
     * 插入排序
     * @param a
     */
    public static void insertionSort(int[] a){
        int length = a.length;
        for(int i=0;i<length;i++){
            for(int j=i;j>0;j--){
                //内层的每一次循环保证了数组左端始终是有序的   
                if(a[j] < a[j-1]){
                    int temp = a[j-1];
                    a[j-1] = a[j];
                    a[j] = temp;
                }else {
                    break;
                }
            }
        }
    }

插入排序的特点：插入排序对于那些部分有序（需要交换的元素较少）的数组效率最高，如果一个数组只有几个元素位置不正确，或每个元素离它正确位置都不远时，插入排序速度可能是最优秀的。插入算法还可以进一步改进。

改进的思想：插入排序时，每一次和前一位的比较在满足条件的情况下都发生了一次交换，但要直到循环条件结束才能确定元素的位置，因此可以在内层循环完成后再改变元素位置，在此之前，只需要将大的元素（从小到大排列的情况）往后移动即可。改进后的算法如下:

1
2
3
4
5
6
7
8
9
10
11
public static void insertionSortNew(int[] a){    
        int length = a.length;
        for(int i=0;i<length;i++){
            int t = a[i];
            int j = i;
            for(;j>0&&a[j-1]>t;j--){
                a[j] = a[j-1];
            }
            a[j] = t;
        }
    }

这样访问数组的次数将会减半。

希尔排序

希尔排序是基于插入排序演变而来，并且速度相较于插入排序要快很多。由于插入排序对于大规模的乱序数组来说速度比较慢，因为它只会交换相邻的两个元素，如果一个元素距离其正确的位置比较远，则它需要的交换次数将会非常多。希尔排序针对此进行了改进，不交换相邻的元素来对数组进行局部排序，最终将局部有序数组整理为有序数组。

希尔排序的思想在于让数组中任意间隔为h的数组都是有序的，每次按照不同的步长将整个数组划分为多个数组，在步长为1的时候，此时的操作变成了普通的插入排序，但此时的数组已经是基本有序的，因此插入排序在这时候比较高效。

希尔排序的简单实现：

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
/**
     * 希尔排序，按升序排列
     * @param a
     */
    public static void shellSort(int[] a){
        int length = a.length;
        int h = 1;
        //计算初始步长
        while (h < length/3){
            h = 3*h + 1;
        }

        while (h>=1){
            for (int i = h; i < length; i++){
                for(int j = i; j>=h && a[j]<a[j-h]; j -= h){     
                    int temp = a[j];
                    a[j] = a[j-h];
                    a[j-h] = temp;
                }
            }

            h = h/3;
        }

    }

其中步长h并非完全需要按照这个大小来设定，目前并没有一种真正有力的说法来支持到底怎样的步长是最高效的。但由于这个步长，让希尔排序的速度远大于选择排序的插入排序，并且数组越大的时候优势越明显。