基本排序算法<一>

一选择排序

原理：选择排序很简单，他的步骤如下：

从左至右遍历，找到最小(大)的元素，然后与第一个元素交换。
从剩余未排序元素中继续寻找最小（大）元素，然后与第二个元素进行交换。
以此类推，直到所有元素均排序完毕。

　之所以称之为选择排序，是因为每一次遍历未排序的序列我们总是从中选择出最小的元素。下面是选择排序的动画演示：

public class Sort {
　　　　 //选择排序
    public static void SelectionSort(int[] array) {
        int n = array.length;
        for (int i = 0; i < n; i++) {
            int min = i; // 从第i+1个元素开始，找最小值
            for (int j = i + 1; j < n; j++) {
                if (array[min] > array[j])
                    min = j;
            }
            Swap(array, i, min);
        }
    }
　　　　 //插入排序
    public static void insertionSort(int[] array){
        int n = array.length;
        for (int i =1; i < n; i++) {
            for (int j = i; j >0; j--) {
                if (array[j] < array[j-1])
                    Swap(array, j, j-1);
                else
                    break;
            }    
        }
    }
　　　　 //冒泡排序
    public static void bubbleSort(int[] array){
        int n = array.length;
        for (int i =0; i < n; i++) {
            for (int j = n-1; j >i; j--) {
                if (array[j] < array[j-1])
                    Swap(array, j, j-1);
            }    
        }
    }
　　　　 //希尔排序
　　　　 public static void shellSort(int[] arr){
        　　int N=arr.length;
        　　int h=1;
        　　while(h<N/3){
            　　h=3*h+1;
        　　}
       　　 while (h>=1) {
            　　for(int i =h; i <N; i++) {
                　　for (int j =i; j>=h&&(arr[j]<arr[j-h]); j-=h) {
                       　　 swap(arr, j, j-h);    
                　　}
            　　}
           　　 h=h/3;
        　　}
   　　　}
    private static void Swap(int[] array, int i, int min) {
        int temp = array[i];
        array[i] = array[min];
        array[min] = temp;
    }
    private static void printArr(int[] array){
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i]+" ");
        }
        System.out.println("");
    }
    public static void main(String[] args) {
        int[] array = new int[] { 1, 3, 1, 4, 2, 4, 2, 3, 2, 4, 7, 6, 6, 7, 5,5, 7, 7 };
        System.out.println("Before Sort:");
        printArr(array);
        //SelectionSort(array);
        //insertionSort(array);
        bubbleSort(array);
        System.out.println("After Sort:");
        printArr(array);
    }
}

View Code

　　下图分析了选择排序中每一次排序的过程，您可以对照图中右边的柱状图来看。

(array);

　　分析：

　　选择排序的在各种初始条件下的排序效果如下：

选择排序需要花费 (N – 1) + (N – 2) + … + 1 + 0 = N(N- 1) / 2 ~ N²/2次比较和 N-1次交换操作。
对初始数据不敏感，不管初始的数据有没有排好序，都需要经历N²/2次比较，这对于一些原本排好序，或者近似排好序的序列来说并不具有优势。在最好的情况下，即所有的排好序，需要0次交换，最差的情况，倒序，需要N-1次交换。
数据交换的次数较少，如果某个元素位于正确的最终位置上，则它不会被移动。在最差情况下也只需要进行N-1次数据交换，在所有的完全依靠交换去移动元素的排序方法中，选择排序属于比较好的一种。

二插入排序

原理：

　　插入排序也是一种比较直观的排序方式。可以以我们平常打扑克牌为例来说明，假设我们那在手上的牌都是排好序的，那么插入排序可以理解为我们每一次将摸到的牌，和手中的牌从左到右依次进行对比，如果找到合适的位置则直接插入。具体的步骤为：

从第一个元素开始，该元素可以认为已经被排序
取出下一个元素，在已经排序的元素序列中从后向前扫描
如果该元素小于前面的元素，则依次与前面元素进行比较如果小于则交换，直到找到大于该元素的就则停止；
如果该元素大于前面的元素（已排序），则重复步骤2
重复步骤2~4 直到所有元素都排好序。

　　下面是插入排序的动画演示：

分析：

　　插入排序的在各种初始条件下的排序效果如下：

　　1. 插入排序平均需要N²/4次比较和N²/4 次交换。在最坏的情况下需要N²/2 次比较和交换；在最好的情况下只需要N-1次比较和0次交换。

　　先考虑最坏情况，那就是所有的元素逆序排列，那么第i个元素需要与前面的i-1个元素进行i-1次比较和交换，所有的加起来大概等于N(N- 1) / 2 ~ N² / 2，在数组随机排列的情况下，只需要和前面一半的元素进行比较和交换，所以平均需要N²/4次比较和N²/4 次交换。

　　在最好的情况下，所有元素都排好序，只需要从第二个元素开始都和前面的元素比较一次即可，不需要交换，所以为N-1次比较和0次交换。

　　2. 插入排序中，元素交换的次数等于序列中逆序元素的对数。元素比较的次数最少为元素逆序元素的对数，最多为元素逆序的对数加上数组的个数减1。

　　3.总体来说，插入排序对于部分有序序列以及元素个数比较小的序列是一种比较有效的方式。

　　如上图中，序列AEELMOTRXPS，中逆序的对数为T-R，T-P，T-S，R-P，X-S 6对。典型的部分有序队列的特征有：

数组中每个元素离最终排好序后的位置不太远
小的未排序的数组添加到大的已排好序的数组后面
数组中只有个别元素未排好序

　　对于部分有序数组，插入排序是比较有效的。当数组中逆元素的对数越低，插入排序要比其他排序方法要高效的多。

　　选择排序和插入排序的比较：

　　上图展示了插入排序和选择排序的动画效果。图中灰色的柱子是不用动的，黑色的是需要参与到比较中的，红色的是参与交换的。图中可以看出：插入排序不会动右边的元素，选择排序不会动左边的元素；由于插入排序涉及到的未触及的元素要比插入的元素要少，涉及到的比较操作平均要比选择排序少一半。

3.冒泡排序

　　冒泡排序也被称为下沉排序，是一个简单的排序算法，通过多次重复比较每对相邻的元素，并按规定的顺序交换他们，最终把数列进行排好序。一直重复下去，直到结束。该算法得名于较小元素“气泡”会“浮到”列表顶部。由于只使用了比较操作，所以这是一个比较排序。冒泡排序算法的运作如下：

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

　　时间复杂度

　　若文件的初始状态是正序的，一趟扫描即可完成排序。所需的关键字比较次数

C和记录移动次数

M均达到最小值：

Cmin=n-1，Mmin=0。所以，冒泡排序最好的时间复杂度为

O(n)。

　　若初始文件是反序的，需要进行

n-1趟排序。每趟排序要进行

n-i次关键字的比较(1≤i≤n-1)，且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下，比较和移动次数均达到最大值：

　　冒泡排序的最坏时间复杂度为O(n*n)综上，因此冒泡排序总的平均时间复杂度为O(n*n)。

　　算法稳定性

　　冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较，交换也发生在这两个元素之间。所以，如果两个元素相等，我想你是不会再无聊地把他们俩交换一下的；如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个相邻起来，这时候也不会交换，所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。

希尔排序

　　原理：希尔排序也称之为递减增量排序，它是对插入排序的改进。在插入排序中，我们知道，插入排序对于近似已排好序的序列来说，效率很高，可以达到线性排序的效率。但是插入排序效率也是比较低的，他一次只能将数据向前移一位。比如如果一个长度为N的序列，最小的元素如果恰巧在末尾，那么使用插入排序仍需一步一步的向前移动和比较，要N-1次比较和交换。希尔排序通过将待比较的元素划分为几个区域来提升插入排序的效率。这样可以让元素可以一次性的朝最终位置迈进一大步，然后算法再取越来越小的步长进行排序，最后一步就是步长为1的普通的插入排序的，但是这个时候，整个序列已经是近似排好序的，所以效率高。

　　如下图，我们对下面数组进行排序的时候，首先以4为步长，这是元素分为了LMPT，EHSS，ELOX，AELR几个序列，我们对这几个独立的序列进行插入排序，排序完成之后，我们减小步长继续排序，最后直到步长为1，步长为1即为一般的插入排序，他保证了元素一定会被排序。

　　希尔排序的增量递减算法可以随意指定，可以以N/2递减，只要保证最后的步长为1即可。

实现：

public static void shellSort(int[] arr){
	int N=arr.length;
	int h=1;
	while(h<N/3){
		h=3*h+1;
	}
	while (h>=1) {
		for(int i =h; i <N; i++) {
			for (int j =i; j>=h; j-=h) {
				if(arr[j]<arr[j-h]){
					swap(arr, j, j-h);
				}else{
					break;
				}
			}
		}
		h=h/3;
	}
}

　　可以看到，希尔排序的实现是在插入排序的基础上改进的，插入排序的步长为1，每一次递减1，希尔排序的步长为我们定义的h，然后每一次和前面的-h位置上的元素进行比较。算法中，我们首先获取小于N/3 的最大的步长，然后逐步长递减至步长为1的一般的插入排序。

　　下面是希尔排序在各种情况下的排序动画：

分析：

1. 希尔排序的关键在于步长递减序列的确定，任何递减至1步长的序列都可以，目前已知的比较好的序列有：

Shell’s 序列: N/2 , N/4 , …, 1 (重复除以2);
Hibbard’s 序列: 1, 3, 7, …, 2^k – 1 ;
Knuth’s 序列: 1, 4, 13, …, (3^k – 1) / 2 ;该序列是本文代码中使用的序列。
已知最好的序列是 Sedgewick’s (Knuth的学生，Algorithems的作者)的序列: 1, 5, 19, 41, 109, ….

该序列由下面两个表达式交互获得:

1, 19, 109, 505, 2161,….., 9(4^k – 2^k) + 1, k = 0, 1, 2, 3,…
5, 41, 209, 929, 3905,…..2^k+2 (2^k+2 – 3 ) + 1, k = 0, 1, 2, 3, …

　　“比较在希尔排序中是最主要的操作，而不是交换。”用这样步长的希尔排序比插入排序和堆排序都要快，甚至在小数组中比快速排序还快，但是在涉及大量数据时希尔排序还是比快速排序慢。

　　2. 希尔排序的分析比较复杂，使用Hibbard’s 递减步长序列的时间复杂度为O(N^3/2)，平均时间复杂度大约为O(N^5/4) ,具体的复杂度目前仍存在争议。

　　3. 实验表明，对于中型的序列( 万)，希尔排序的时间复杂度接近最快的排序算法的时间复杂度nlogn。

　　最后总结一下本文介绍的三种排序算法的最好最坏和平均时间复杂度。

名称	最好	平均	最坏	内存占用	稳定排序
插入排序	n	n²	n²	1	是
选择排序	n²	n²	n²	1	否
希尔排序	n	nlog²n 或 n^3/2	依赖于增量递减序列目前最好的是 nlog²n	1	否