Vgbhfive's Blog

排序算法

Posted on Edited on

1. 冒泡排序

1. 原理

临近的数字两两进行比较，按照从小到大或者从大到小的顺序进行交换，这样一趟过去后，最大或最小的数字被交换到了最后一位，然后再从头开始进行两两比较交换，直到倒数第二位时结束，其余类似看例子例子为从小到大排序。

2. 代码

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
package com.vgbh;

public class BubbleSorting {

    private static int n = 10;//数组长度
    private static int[] arr = new int[n];//数组

    private static int count = 0;//执行次数

    static PublicOut pc= null;//定义外部对象

    public static void main(String[] args){
        pc = new PublicOut();
        pc.data(arr, n);

        BubbleSorting bs = new BubbleSorting();
        bs.bubble(arr);
    }

    /*
     * 原理是临近的数字两两进行比较,按照从小到大或者从大到小的顺序进行交换,
     * 这样一趟过去后,最大或最小的数字被交换到了最后一位,
     * 然后再从头开始进行两两比较交换,直到倒数第二位时结束,
     * 其余类似看例子例子为从小到大排序,
     */

    public void bubble(int[] arr){
        System.out.println("冒泡排序之后:");
        for(int x=0;x<n;++x){
            for (int y=0;y<n;++y) {
                if(y+1 == arr.length) break;
                if(arr[y] > arr[y+1]) {
                    pc.change(arr,y,y+1);//数据转换
                    count++;
                    //pc.prin(arr,n);
                    //System.out.println("zzzzzzz"+arr[x] +"     " +arr[x+1]); 测试代码
                }
            }
        }
        pc.prin(arr,n);
        System.out.println("共执行"+ count +"次");
    }
}

3. 后记

哇，现在看见纪念写的代码，我不知道那时候咋写的。。。。。。。

2. 快速排序

1. 原理

快速排序是一种划分交换排序。它采用了一种分治的策略，通常称其为分治法(Divide-and-ConquerMethod)。

分治法的基本思想是：将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题，然后将这些子问题的解组合为原问题的解。

利用分治法可将快速排序的分为三步：

  1. 在数据集之中，选择一个元素作为”基准”（pivot）。
  2. 所有小于”基准”的元素，都移到”基准”的左边；所有大于”基准”的元素，都移到”基准”的右边。 这个操作称为分区 (partition)操作，分区操作结束后，基准元素所处的位置就是最终排序后它的位置。
  3. 对”基准”左边和右边的两个子集，不断重复第一步和第二步，直到所有子集只剩下一个元素为止。

2. 代码

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
package com.vgbh;

public class QuickSorting {

    /* 
     * 快速排序是一种划分交换排序。它采用了一种分治的策略，通常称其为分治法(Divide-and-ConquerMethod)。
     * 
     * 分治法的基本思想是：将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题，然后将这些子问题的解组合为原问题的解。
     * 
     * 利用分治法可将快速排序的分为三步： 在数据集之中，选择一个元素作为”基准”（pivot）。
     * 所有小于”基准”的元素，都移到”基准”的左边；所有大于”基准”的元素，都移到”基准”的右边。 这个操作称为分区 (partition)
     * 操作，分区操作结束后，基准元素所处的位置就是最终排序后它的位置。
     * 对”基准”左边和右边的两个子集，不断重复第一步和第二步，直到所有子集只剩下一个元素为止。
     */

    private static int n = 10;//数组长度
    private static int[] arr = new int[10];//数组

    static PublicOut pc = null;//外部对象

    public static void main(String[] args) {
        pc = new PublicOut();

        System.out.println("排序前：");
        pc.data(arr, n);
        pc.prin(arr, n);

        QuickSorting qs = new QuickSorting();
        qs.quick(arr, 0,9);

        System.out.println("排序后：");
        pc.prin(arr, n);

    }

    public void quick (int[] arr,int left,int right) {
        if (arr.length > 0) {
            if (left < right) {
                int pivotpos = partition(arr,left,right);
                quick(arr,left,pivotpos-1);
                quick(arr,pivotpos+1,right);
            }
        }

    }

    public int partition (int[] arr,int left,int right) {
        //返回最后定位基准的下标

        int temp = arr[left];
        while (left < right) {
            while (left<right && arr[right]>=temp) {
                --right;
                //System.out.println("右移一次");
            }
            arr[left] = arr[right];
            //System.out.println("右边的支付给左边");
            while (left<right && arr[left]<=temp) {
                ++left;
                //System.out.println("左移一次");
            }
            arr[right] = arr[left];
            //System.out.println("左边的值赋给右边");
        }
        arr[left] = temp;
        //System.out.println(left);
        //pc.prin(arr, n);

        return left;

        /* 一次错误的示范
        int pivot = arr[l];
        while (l < r) {
            while (l<r && arr[l]<=pivot) {
                r--;
                if (l<r) {
                    arr[l] = arr[r];
                }
            }
            while (l<r && arr[r]>=pivot) {
                l++;
                if (l<r) {
                    arr[r] = arr[l];
                }
            }
        }
        arr[l] = pivot;
        return l;
         */
    }

    /*
    对于1~10的有规律排序，快速排序可以进行排序。
    但对于不规则排序会死循环，会一直在赋值之间来回赋值，从而进入死循环。
     */

3. 后记

这又发现了一个原来的坑，还没有填。。。。。

3. 选择排序

1. 原理

  1. 从n个元素中找出关键字最小的元素与第一个元素交换;
  2. 在从第二个元素开始的n-1个元素中再选出关键字最小的元素与第二个元素交换;
  3. 第k趟,则从第k个元素开始的n-k+1个元素中选出关键字最小的元素与第k个元素交换,直到整个序列按关键字有序｡选择排序是不稳定的排序方法。

2. 代码

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
package com.vgbh;

public class SelectSorting {

    private static int n = 10 ;//数组长度
    private static int[] arr = new int[n] ;//数组

    static PublicOut pc = null ;//定义外部对象

    public static void main(String args[]) {
        pc = new PublicOut();
        pc.data(arr,n);
        pc.prin(arr,n);

        SelectSorting ss = new SelectSorting();
        ss.selectOrder(arr);
        pc.prin(arr, n);
    }

    public void selectOrder (int arr[]) {
        int min ;
        for (int x=0;x<arr.length-1;x++) {
            min = x;
            for (int y=x+1;y<arr.length;y++) {
                if (arr[y] < arr[min])  min = y ;
                if (min != x) pc.change(arr, min, x);
            }
        }
    }
}

4. 希尔排序

1. 原理

  1. 将无序数组分割为若干个子序列，子序列不是逐段分割的，而是相隔特定的增量的子序列，对各个子序列进行插入排序；
  2. 然后再选择一个更小的增量，再将数组分割为多个子序列进行排序……最后选择增量为1，即使用直接插入排序，使最终数组成为有序。

增量的选择：选用Knuth间隔序列

2. 代码

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
53
54
55
56
57
58
59
package com.vgbh;

public class ShellSorting {
    private static int n = 10 ;//数组长度
    private static int[] arr = new int[n] ;//数组
    static PublicOut pc = null ;//定义外部对象
    static ShellSorting ss = null ;//定义内部对象

    public static void main(String[] args) {
        pc = new PublicOut();
        ss = new ShellSorting();

        ss.data(arr,n);//创建数据
        System.out.println("希尔排序前：");
        pc.prin(arr, n);//打印数据
        ss.shell(arr,n);//希尔排序
        System.out.println("希尔排序后：");
        pc.prin(arr, n);//打印数据
    }

    //希尔排序
    public void shell (int[] arr,int n) {
        int inner , outer ;
        int temp ;
        int h = 1 ;
        while (h < n) h = h*3 + 1;//(Knuth间隔序列：1,4,13,40,121,...)

        //System.out.println("\nstart shell sorting:");
        while (h > 0) {
            //System.out.println("\n\n\n当前的h值为：" + h);
            for (outer=h;outer<n;outer++) {
                //System.out.println("\n第" + outer + "次循环。");
                temp = arr[outer];
                inner = outer ;
                //System.out.println("--------temp:" + temp + "---------inner:" + inner);

                while (inner>h-1 && arr[inner-h]>=temp) {
                    arr[inner] = arr[inner-h];
                    inner -= h;
                    //System.out.println("     arr[inner] :" + arr[inner] + "       inner:" + inner);
                }
                arr[inner] = temp;

                //System.out.println("++++++arr[inner]:" + arr[inner]);
            }
            h = (h-1) / 3;
            //pc.prin(arr, n);
        }

        //System.out.println("end shell sorting:\n");
    }

    public void data (int[] arr,int n) {//排序的数据
        for (int i=0;i<n;i++) {
            arr[i] = 10 - i;//按照一定顺序产生数据：10~0
            //arr[i] = (int)(Math.random()*10);//随机产生数据：0~10随机
        }
    }
}

3. 运行过程

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
/*    
此为数据为{10，9，8，7，6，5，4，3，2，1}时的排序结果，可按照程序的运行结果理解程序的步骤。

希尔排序前：
  10  9  8  7  6  5  4  3  2  1
  ---------------

start shell sorting:

当前的h值为：13

  10  9  8  7  6  5  4  3  2  1
  ---------------


当前的h值为：4

第4次循环。
--------temp:6---------inner:4
     arr[inner] :10       inner:0
++++++arr[inner]:6

第5次循环。
--------temp:5---------inner:5
     arr[inner] :9       inner:1
++++++arr[inner]:5

第6次循环。
--------temp:4---------inner:6
     arr[inner] :8       inner:2
++++++arr[inner]:4

第7次循环。
--------temp:3---------inner:7
     arr[inner] :7       inner:3
++++++arr[inner]:3

第8次循环。
--------temp:2---------inner:8
     arr[inner] :10       inner:4
     arr[inner] :6       inner:0
++++++arr[inner]:2

第9次循环。
--------temp:1---------inner:9
     arr[inner] :9       inner:5
     arr[inner] :5       inner:1
++++++arr[inner]:1

  2  1  4  3  6  5  8  7  10  9
  ---------------

当前的h值为：1

第1次循环。
--------temp:1---------inner:1
     arr[inner] :2       inner:0
++++++arr[inner]:1

第2次循环。
--------temp:4---------inner:2
++++++arr[inner]:4

第3次循环。
--------temp:3---------inner:3
     arr[inner] :4       inner:2
++++++arr[inner]:3

第4次循环。
--------temp:6---------inner:4
++++++arr[inner]:6

第5次循环。
--------temp:5---------inner:5
     arr[inner] :6       inner:4
++++++arr[inner]:5

第6次循环。
--------temp:8---------inner:6
++++++arr[inner]:8

第7次循环。
--------temp:7---------inner:7
     arr[inner] :8       inner:6
++++++arr[inner]:7

第8次循环。
--------temp:10---------inner:8
++++++arr[inner]:10

第9次循环。
--------temp:9---------inner:9
     arr[inner] :10       inner:8
++++++arr[inner]:9

  1  2  3  4  5  6  7  8  9  10
  ---------------


end shell sorting:

希尔排序后：
  1  2  3  4  5  6  7  8  9  10
  ---------------

*/

4. 后记

对于希尔排序，我还是建议动手在纸上演算，其实会出现很多错误，但也会更深刻的理解希尔排序，动手丰衣足食。

5. 堆排序

1. 原理

堆排序算法思想: 堆排序，顾名思义，就是基于堆。

因此先来介绍一下堆的概念：
堆分为最大堆和最小堆，其实就是：完全二叉树或近似完全二叉树。

二叉树的特点：

  1. 最大堆要求节点的元素都要大于其孩子。
  2. 最小堆要求节点元素都小于其左右孩子。

有了上面的定义，我们可以得知，处于最大堆的根节点的元素一定是这个堆中的最大值。其实我们的堆排序算法就是抓住了堆的这一特点，每次都取堆顶的元素，将其放在序列最后面，然后将剩余的元素重新调整为最大堆，依次类推，最终得到排序的序列。

本质上讲，堆排序是一种选择排序，每次都选择堆中最大的元素进行排序。只不过堆排序选择元素的方法更为先进，时间复杂度更低，效率更高。

步骤：

  1. 首先从第一个非叶子节点开始，比较当前节点和其孩子节点，将最大的元素放在当前节点，交换当前节点和最大节点元素。
  2. 将当前元素前面所有的元素都进行1的过程，这样就生成了最大堆
  3. 将堆顶元素和最后一个元素交换，列表长度减1。由此无序区减1，有序区加1
  4. 剩余元素重新调整建堆
  5. 继续3和4，直到所有元素都完成排序

时间复杂度：
堆排序的平均时间复杂度为O(nlogn),接近于最坏的时间复杂度。在最好情况下，时间复杂度为O(1).

算法总结:
堆排序时间复杂度：O(nlogn)。堆排序对原始记录的排序状态并不敏感，其在性能上要远远好过于冒泡、简单选择、直接插入排序。

2. 代码

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
package com.vgbh;

/*
 * 堆排序
 */
public class heapSorting {

    private static int n = 10 ;//数组长度
    private static int[] arr = new int[n] ;//数组

    static PublicOut pc = null ;//定义外部对象

    public static int count = 0;//运行次数

    public static void main(String[] args) {

        pc = new PublicOut();
        pc.data(arr, n);
        pc.prin(arr, n);

        heapSorting hs = new heapSorting();
        hs.heap(arr);

        pc.prin(arr, n);

        //System.out.println("最后共运行" + count + "次。");

    }

    //数据结构的p281有详细的运算过程     详解：http://www.ixywy.com/zsjz/2564.html

    //堆排序
    public void heap (int[] arr) {
        //将数组转化为大堆
        for (int i=arr.length / 2; i>=0; i--) {
            buildHeap(arr,i,arr.length);
        }

        //将最小值与最大值交换，并调整二叉树
        for (int i=arr.length - 1; i>0; i--) {
            swap(arr, 0, i);//将父元素和当前未经排序子序列的最后一个记录交换
            buildHeap(arr, 0, i);//交换之后，重新比对二叉树，不符合则要调整。
        }

    }

    /*
     * 创建堆
     * arr:数组
     * x:需要构建堆的根节点的序号
     * y:数组长度
     */
    public void buildHeap (int[] arr,int x,int y) {
        count++;
        int child ;
        int father ;
        for (father = arr[x]; leftChild(x) < y; x = child) {
            child = leftChild(x);

            //如果左子树小于右子树，则需要比较右子树和父节点
            if (child != y-1 && arr[child] < arr[child+1]) {
                child++;//自增可以指向父节点
            }

            //如果父节点小于孩子节点，则需要交换
            if (father < arr[child]) {
                arr[x] = arr[child];
            } else {
                break;//大堆未被破坏，不需要调整
            }
        }
        arr[x] = father;
    }

    //交换元素
    public void swap (int[] arr,int x,int y) {
        int tmp = arr[x];
        arr[x] = arr[y];
        arr[y] = tmp;
    }

    //获取左孩子结点
    public int leftChild (int i) {
        return 2 * i + 1;
    }
}

3. 后记

堆排序，我想了好几天，最后还是参考了一下别人的博客，看了许多的解释，不过还是下面这些最好理解：
http://www.ixywy.com/zsjz/2564.html
http://blog.csdn.net/zdp072/article/details/44227317

6. 归并排序

1. 原理

两路归并排序算法思路：

  1. 把 n个记录看成 n个长度为1的有序子表；
  2. 进行两两归并使记录关键字有序，得到 n/2 个长度为 2 的有序子表；
  3. 重复第2步直到所有记录归并成一个长度为 n的有序表为止。

归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

算法步骤：

  1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
  2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置
  3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
  4. 重复步骤3直到某一指针达到序列尾
  5. 将另一序列剩下的所有元素直接复制到合并序列尾

2. 代码

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
package com.vgbh;

/*
 * 归并排序
 */
public class MergeSorting {

    private static int n = 10 ;//数组长度
    private static int[] arr = new int[n] ;//数组

    static PublicOut pc = null ;//定义外部对象
    public static int count = 0;//运行次数

    public static void main(String[] args) {
        pc = new PublicOut();
        pc.data(arr, n);
        System.out.println("排序前：");
        pc.prin(arr, n);

        MergeSorting ms = new MergeSorting();
        ms.merge(arr, n);

        System.out.println("排序后：");
        pc.prin(arr, n);

        System.out.println("最后共运行" + count + "次。");

    }

    public void merge (int arr[],int n) {
        int[] temp = new int[n];
        mergeSort(arr,0,n-1,temp);
    }

    /*
     * 归并排序，使用递归
     */
    public void mergeSort (int arr[],int first,int last,int temp[]) {
        if (first < last) {
            int bin = (first + last) / 2;
            mergeSort(arr,first,bin,temp);//左边
            mergeSort(arr,bin+1,last,temp);//右边
            mergeArray(arr,first,bin,last,temp);//数组排序
        }
    }

    /*
     * 合并数组
     * 首先考虑下如何将将二个有序数列合并。这个非常简单，只要从比较二个数列的第一个数，谁小就先取谁，取了后就在对应数列中删除这个数。
     *  然后再进行比较，如果有数列为空，那直接将另一个数列的数据依次取出即可
     */
    public void mergeArray (int arr[],int first,int bin,int last,int temp[]) {
        int i = first;//第一个数组的开始位
        int m = bin;//第一个数组的末尾值
        int j = bin + 1;//第二个数组的开始位
        int n = last;//第二个数组的末尾值
        int k = 0;//替补数组长度值

        //System.out.println("开始合并数组： i ，m  ，j , n , k " + i + m + j + n + k);

        //将数组分割为两部分，两部分进行比较，进行排序，排序后放在替补数组中，最终将排序好的数组返回到原数组。
        //再比对过程中，会首先将某个分数组中的值比对完后，在进行全部赋值操作。(注意观察赋值完成后i和j的值)
        while (i<=m && j<=n) {
            if (arr[i] <= arr[j]) {
                //temp[k] = arr[i]; k++; i++;
                temp[k++] = arr[i++];
                //System.out.println("temp[k]  " + temp[k-1] + "    k " + (k-1) + "   i " + i + "这里是i");
                count++;
            } else {
                //temp[k] = arr[j]; k++; j++;
                temp[k++] = arr[j++];
                //System.out.println("temp[k]  " + temp[k-1] + "    k " + (k-1) + "   j " + j + "这里是j");
                count++;
            }
        }

        while (j <= n) {//补偿未排序进数组的数
            //temp[k] = arr[j]; k++; j++;
            temp[k++] = arr[j++];
            //System.out.println("temp[k]" + temp[k-1] + "    k" + (k-1) + "   j" + j);
            count++;
        }

        while (i <= m) {//补偿未排序进数组的数
            //temp[k] = arr[i]; k++; i++;
            temp[k++] = arr[i++];
            //System.out.println("temp[k]  " + temp[k-1] + "    k  " + (k-1) + "   i  " + i);
            count++;
        }

        for (int x=0;x<k;x++) {
            arr[first+x] = temp[x];
            //System.out.println(temp[x] + "    最后的交换值    temp[x]");
        }
    }
}

3. 后记

注释的部分都是测试代码，可以更好地帮助你理解整个运行过程。