排序算法

冒泡排序：从数组尾端开始，依次比较两个相邻元素，如果前一个元素大于后一个元素，则交换，否则继续比较下一相邻元素，一次下来，最小的元素排到shou’duan较大的元素排在后端，下次排序继续从尾端开始，若数组长度为N，经过N-1次冒泡可将数组按从小到大的顺序排列。
缺点：无论原数据是否有序，都要经过N-1次排序

public class P4_1 {
    private static final int SIZE = 10;
    public static void bubbleSort(int[] a){
        final int SIZE=10;
        int temp;
        for(int i=1;i<a.length;i++){
            for(int j=a.length-1;j>0;j--){
                if(a[j]<a[j-1]){
                    temp=a[j-1];
                    a[j-1]=a[j];
                    a[j]=temp;
                }
            }
            System.out.print("第"+i+"步排序结果");
            for(int k=0;k<a.length;k++){
                System.out.print(" "+a[k]);
            }
            System.out.print("\n");
        }
    }
    public static void main(String[] args){
        int[] shuzu=new int[SIZE];
        int i;
        for(i=0;i<SIZE;i++){
            shuzu[i]=(int)(100+Math.random()*(100+1));
        }
        for(i=0;i<SIZE;i++ ){
            System.out.print(shuzu[i]+" ");
        }
        System.out.print("\n");
        bubbleSort(shuzu);
        for(i=0;i<SIZE;i++ ){
            System.out.print(```
huzu[i]+" ");
        }
    }


}
结果
132 166 156 151 173 185 188 150 130 138 
第1步排序结果 130 132 166 156 151 173 185 188 150 138
第2步排序结果 130 132 138 166 156 151 173 185 188 150
第3步排序结果 130 132 138 150 166 156 151 173 185 188
第4步排序结果 130 132 138 150 151 166 156 173 185 188
第5步排序结果 130 132 138 150 151 156 166 173 185 188
第6步排序结果 130 132 138 150 151 156 166 173 185 188
第7步排序结果 130 132 138 150 151 156 166 173 185 188
第8步排序结果 130 132 138 150 151 156 166 173 185 188
第9步排序结果 130 132 138 150 151 156 166 173 185 188
130 132 138 150 151 156 166 173 185 188 
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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

选择排序：在每一步中选取最小的值来重新排列
（1）从原始数组中选取最小的1个数据，与第一个位置的数据交换
（2）从剩下的N-1个数据中选择次小的1个数据，与第二个位置的数据交换
（3）不断重复，直到最后两个数据完成交换
无论原数据是否有序，都要进行N-1次操作

public class P4_2 {
    final static int SIZE=10;
    public static void selectSort(int[] a){
        //记录一次排序中，当前最小数索引
        int index;
        int temp;
        for(int i=0;i<a.length-1;i++){
            index=i;
            for(int j=i+1;j<a.length;j++){
            if(a[j]<a[index]){
                index=j;
            }
            }
            if(index!=i){
                temp=a[i];
                a[i]=a[index];
                a[index]=temp;
            }
            System.out.print("第"+i+"步排序结果");
            for(int k=0;k<a.length;k++){
                System.out.print(" "+a[k]);
            }
            System.out.print("\n");
        }
    }
    public static void main(String[] args){
        int[] shuzu=new int[SIZE];
        int i;
        for(i=0;i<SIZE;i++){
            shuzu[i]=(int)(100+Math.random()*(100+1));
        }
        for(i=0;i<SIZE;i++ ){
            System.out.print(shuzu[i]+" ");
        }
        System.out.print("\n");
        selectSort(shuzu);
        for(i=0;i<SIZE;i++ ){
            System.out.print(shuzu[i]+" ");
        }
    }
}
107 146 198 120 175 129 191 175 127 123 
第0步排序结果 107 146 198 120 175 129 191 175 127 123
第1步排序结果 107 120 198 146 175 129 191 175 127 123
第2步排序结果 107 120 123 146 175 129 191 175 127 198
第3步排序结果 107 120 123 127 175 129 191 175 146 198
第4步排序结果 107 120 123 127 129 175 191 175 146 198
第5步排序结果 107 120 123 127 129 146 191 175 175 198
第6步排序结果 107 120 123 127 129 146 175 191 175 198
第7步排序结果 107 120 123 127 129 146 175 175 191 198
第8步排序结果 107 120 123 127 129 146 175 175 191 198
107 120 123 127 129 146 175 175 191 198 
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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

插入排序：
（1）首先对数组的前两个数据进行排序
（2）将第3个数据与排好的数据进行比较，将第三个数据插入到合适位置
（3）将第四个数据插入到已排好的前三个数据中
（4）不断重复，直至将最后一个数据插入到合适的位置

public static void insertSort(int[] a){
        int i,j,t;
        //i表示待插入元素
         for(i=1;i<a.length;i++){
             j=i-1;
             t=a[i];
             while(j>=0&&t<a[j]){
                 a[j+1]=a[j];
                 j--;
             }
             a[j+1]=t;
             System.out.print("第"+i+"步排序结果");
                for(int k=0;k<a.length;k++){
                    System.out.print(" "+a[k]);
                }
                System.out.print("\n")}

         }


    }123 143 178 184 180 175 134 166 140 115 
第1步排序结果 123 143 178 184 180 175 134 166 140 115
第2步排序结果 123 143 178 184 180 175 134 166 140 115
第3步排序结果 123 143 178 184 180 175 134 166 140 115
第4步排序结果 123 143 178 180 184 175 134 166 140 115
第5步排序结果 123 143 175 178 180 184 134 166 140 115
第6步排序结果 123 134 143 175 178 180 184 166 140 115
第7步排序结果 123 134 143 166 175 178 180 184 140 115
第8步排序结果 123 134 140 143 166 175 178 180 184 115
第9步排序结果 115 123 134 140 143 166 175 178 180 184
115 123 134 140 143 166 175 178 180 184 
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

Shell排序：

http://blog.csdn.net/morewindows/article/details/6668714

以n=10的一个数组49, 38, 65, 97, 26, 13, 27, 49, 55, 4为例
第一次 gap = 10 / 2 = 5
49 38 65 97 26 13 27 49 55 4
1A 1B
2A 2B
3A 3B
4A 4B
5A 5B
1A,1B，2A,2B等为分组标记，数字相同的表示在同一组，大写字母表示是该组的第几个元素， 每次对同一组的数据进行直接插入排序。即分成了五组(49, 13) (38, 27) (65, 49) (97, 55) (26, 4)这样每组排序后就变成了(13, 49) (27, 38) (49, 65) (55, 97) (4, 26)，下同。
第二次 gap = 5 / 2 = 2
排序后
13 27 49 55 4 49 38 65 97 26
1A 1B 1C 1D 1E
2A 2B 2C 2D 2E
第三次 gap = 2 / 2 = 1
4 26 13 27 38 49 49 55 97 65
1A 1B 1C 1D 1E 1F 1G 1H 1I 1J
第四次 gap = 1 / 2 = 0 排序完成得到数组：
4 13 26 27 38 49 49 55 65 97

public static void shellSort(int[] a){
        int n=a.length;
        int i,j ,gap,h=0;
        int temp;
        for(gap=n/2;gap>0;gap/=2){
            for(i=0;i<gap;i++){
                for(j=i+gap;j<n;j+=gap){
                    //每一个序列内采用插入排序
                    if(a[j]<a[j-gap]){
                        temp=a[j];
                        int k=j-gap;
                        while(k>=0&&a[k]>temp){
                            a[k+gap]=a[k];
                            k-=gap;
                        }
                        a[k+gap]=temp;

                    }
            }
            }
            h++;
             System.out.print("第"+h+"步排序结果");
                for(int k=0;k<a.length;k++){
                    System.out.print(" "+a[k]);
                }
                System}
    out.print("\n");

    }
    }
    143 168 102 183 160 195 125 179 142 117 
第1步排序结果 143 125 102 142 117 195 168 179 183 160
第2步排序结果 102 125 117 142 143 160 168 179 183 195
第3步排序结果 102 117 125 142 143 160 168 179 183 195
102 117 125 142 143 160 168 179 183 195 
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

快速排序：
（1）设定一个分界值，通过分界值将数组分为两部分；
（2）将大于等于分界值得数据集中到数组右侧，小于分界值的数据集中到数组左侧，分界值左边各元素都小于分界值，分解值右边各元素都大于分界值；
（3）对分界值左右两侧分别递归调用步骤（2）

实际操作理解：

http://blog.csdn.net/morewindows/article/details/6684558

/**
     * 快速排序
     * @param a
     * @param l
     * @param r
     * 
     */
    public static void quickSort(int[] a,int l,int r){
        if(l<r){
        int i=l,j=r;
        //第一个元素作为分界值挖出来，从后往前找到比分界值小的元素，放到a[i]处，此时a[j]空缺，在从前往后，找到第一个比分界值大的元素放到a[j]处，此时a[i]又处于空缺位，又从后往前，从前往后，直到i=j，最后把分界值放到a[i]处，对分界值左右两个数组递归调用上述过程
        int base=a[l];
        while(i<j&&a[j]>=base){
            j--;
        }
        if(i<j){
        a[i]=a[j];
        i++;
        }
        while(i<j&&a[i]>=base){
            i++;
        }
        if(i<j){
        a[j]=a[i];
        j--;
        }
        a[i]=base;
        quickSort(a,l,i-1);
        quickSort(a,i+1,r);
        }

    }
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