排序算法总结

最近开始研读算法导论，刚开始看，对于排序算法在这之前就不叫熟悉冒泡算法，对其他的算法也只是有所耳闻，并未深入研究。看过书后才知道还有这么多算法，先总结一下，留着日后查看，先了解算法原理，对于性能效率等问题先不研究了。

1、插入排序

有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序，这个时候就要用到一种新的排序方法–插入排序法,插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为O(n^2)。是稳定的排序方法。插入算法把要排序的数组分成两部分：第一部分包含了这个数组的所有元素，但将最后一个元素除外，而第二部分就只包含这一个元素。在第一部分排序后，再把这个最后元素插入到此刻已是有序的第一部分里的位置。

简单的说就像是在玩扑克牌的时候，先抓一张牌，抓第二张牌的时候就先跟手上的牌比一下，然后插到一个合适的位置，整个牌就是有序的了。

具体算法描述如下：

⒈ 从第一个元素开始，该元素可以认为已经被排序

⒉ 取出下一个元素，在已经排序的元素序列中从后向前扫描

⒊ 如果该元素（已排序）大于新元素，将该元素移到下一位置

⒋ 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置

⒌ 将新元素插入到下一位置中

⒍ 重复步骤2

算法实现：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
int[] abs=new int[]{5,35,69,38,41,2,11,85};
for(int i=0;i<abs.length;i++){
    int j=i;
    int temp=abs[i];
    while(j>0 && temp<abs[j-1]){
        abs[j]=abs[j-1];
        j--;
    }
    abs[j]=temp;
}
printf(abs);

这样结果打印出来的就是排序好的数列。

2、冒泡排序

这应该是比较常用和简单的算法了。

它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。

冒泡排序算法的运作如下：

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

算法实现：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
int[] abs=new int[]{5,35,69,38,41,2,11,85};
for(int i=0;i<abs.length;i++){
    for(int j=i;j<abs.length;j++){
        if(abs[i]>abs[j]){
            int tmp=abs[i];
            abs[i]=abs[j];
            abs[j]=tmp;
        }
    }
}
printf(abs);

3、鸡尾酒排序

鸡尾酒排序是冒泡排序的一种变形，此算法与冒泡排序的不同处在于排序时是以双向在序列中进行排序。数组中的数字本是无规律的排放，先找到最小的数字，把他放到第一位，然后找到最大的数字放到最后一位。然后再找到第二小的数字放到第二位，再找到第二大的数字放到倒数第二位。以此类推，直到完成排序。

算法实现：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
for(int i = 0 ; i < src.length/2 ; i++){
for(int j = 0 ; j < src.length-i-1 ; j++){
    if(src[j] < src[j+1]){
        int temp = src[j];
        src[j] = src[j+1];
        src[j+1] = temp;
    }
System.out.println("交换小"+Arrays.toString(src));
}
//将最大值排到队头
for(int j = src.length - i -1 ; j > i ; j--){
    if(src[j] > src[j-1]){
        int temp = src[j];
        src[j] = src[j-1];
        src[j-1] = temp;
    }
System.out.println("交换大"+Arrays.toString(src));
}
System.out.println("第"+i+"次排序结果："+Arrays.toString(src));
}   

4、二叉排序树

二叉排序树（Binary Sort Tree）又称二叉查找树。它或者是一棵空树；或者是具有下列性质的二叉树：

（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；

（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；

（3）左、右子树也分别为二叉排序树。

5、其他排序方法

排序方法还包括桶排序、计数排序、合并排序、鸽巢排序、Gnome排序、图书馆排序。

这些排序方法较为少见，就不详细说明了。