JAVA 九种排序算法详解（中）

加百利

关注

发布于: 4 小时前

五、简单选择排序：

1.基本思想：

在要排序的一组数中，选出最小的一个数与第一个位置的数交换；然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环到倒数第二个数和最后一个数比较为止

2.实现过程：

原数组值：
32 , 43, 23, 13, 5
第一轮比较：遍历整个序列，将最小的数放在最前面，得到结果：
5 , 32, 43, 23, 13
第二轮比较：遍历剩下的序列，将最小的数放在最前面，得到结果：
5 , 13， 32, 43, 23
第三轮比较：遍历剩下的序列，将最小的数放在最前面，得到结果：
5 , 13， 23， 32， 43
第四轮比较：遍历剩下的序列，将最小的数放在最前面，得到结果
5 , 13， 23， 32， 43
第五轮比较：遍历剩下的序列，将最小的数放在最前面，得到结果
5 , 13， 23， 32， 43

实现过程如图所示：

3.实现代码：

package cn.hz.demo2;
/** * @author hz * @version 1.0 * * 简单选择排序 * 需求分析： * 遍历整个序列，将最小的数放在最前面。 * 遍历剩下的序列，将最小的数放在最前面。 * 重复第二步，直到只剩下一个数。 */public class Demo4 {    public static void main(String[] args) {        int[] a={49,38,65,97,76,13,27,49,78,34,12,64,1};  //定义需要排序数组        System.out.println("简单选择排序前");        for (int i:a){            System.out.print(i+"t");        }        int length = a.length;        for (int i = 0; i < length; i++) {//循环次数            int key = a[i];            int position=i;            for (int j = i + 1; j < length; j++) {//选出最小的值和位置                if (a[j] < key) {                    key = a[j];                    position = j;                }            }            a[position]=a[i];//交换位置            a[i]=key;        }        System.out.println("n简单选择排序后");        for (int i:a){            System.out.print(i+"t");        }
    }}

复制代码

实现效果：

4.分析：

简单选择排序是不稳定的排序。

时间复杂度：T(n)=O(n2)。

5.稳定性总结：

选择排序即是给每个位置选择待排序元素中当前最小的元素。比如给第一个位置选择最小的，在剩余元素里面给第二个位置选择次小的，

依次类推，直到第 n-1 个元素，第 n 个元素不用选择了，因为只剩下它一个最大的元素了。

那么，在一趟选择时，如果当前锁定元素比后面一个元素大，而后面较小的那个元素又出现在一个与当前锁定元素相等的元素后面，那么交换后位置顺序显然改变了。

呵呵！比较拗口，举个例子：序列 5 8 5 2 9，我们知道第一趟选择第 1 个元素 5 会与 2 进行交换，那么原序列中两个 5 的相对先后顺序也就被破坏了。

所以选择排序不是一个稳定的排序算法。

六、堆排序：

1.基本思想：

堆排序是一种树形选择排序，是对直接选择排序的有效改进。

堆的定义：具有 n 个元素的序列（h1,h2,...,hn),当且仅当满足（hi>=h2i,hi>=2i+1）或（hi<=h2i,hi<=2i+1） (i=1,2,...,n/2)时称之为堆。在这里只讨论满足前者条件的堆。由堆的定义可以看出，堆顶元素（即第一个元素）必为最大项（大顶堆）。完全二叉树可以很直观地表示堆的结构。堆顶为根，其它为左子树、右子树。

思想: 初始时把要排序的数的序列看作是一棵顺序存储的二叉树，调整它们的存储序，使之成为一个堆，这时堆的根节点的数最大。然后将根节点与堆的最后一个节点交换。然后对前面(n-1)个数重新调整使之成为堆。依此类推，直到只有两个节点的堆，并对它们作交换，最后得到有 n 个节点的有序序列。从算法描述来看，堆排序需要两个过程，一是建立堆，二是堆顶与堆的最后一个元素交换位置。所以堆排序有两个函数组成。一是建堆的渗透函数，二是反复调用渗透函数实现排序的函数。

2.实现过程：

原数组值：
32 , 43, 23, 13, 5
将数组值构建大顶堆（堆顶元素（即第一个元素）必为最大项），得到结果如下：

将根节点与最后一个节点交换，然后断开最后一个节点。

重复第一、二步，直到所有节点断开。
重新建大顶堆：

根节点与最后节点交换，然后断开最后节点

重复第一、二步，直到所有节点断开。

得到结果 5, 13, 23, 32, 43

3.实现代码：

package cn.hz.demo2;
/** * @author hz * @version 1.0 * * 堆排序 * 需求分析： * 将序列构建成大顶堆。 * 将根节点与最后一个节点交换，然后断开最后一个节点。 * 重复第一、二步，直到所有节点断开。 * */public class Demo6 {    public static void main(String[] args) {        int[] a = {49, 38, 65, 97, 76, 13, 27, 49, 78, 34, 12, 64, 1};  //定义需要排序数组        System.out.println("堆排序前");        for (int i : a) {            System.out.print(i + "t");        }        int arrayLength=a.length;        //循环建堆        for(int i=0;i<arrayLength-1;i++){            //建堆            buildMaxHeap(a,arrayLength-1-i);            //交换堆顶和最后一个元素            swap(a,0,arrayLength-1-i);        }
        System.out.println("n堆排序后：");        for (int i : a) {            System.out.print(i + "t");        }    }
    /**     * 交换     */    private static void swap(int[] data, int i, int j) {        int tmp = data[i];        data[i] = data[j];        data[j] = tmp;    }
    /**     * 对data数组从0到lastIndex建大顶堆     */    private static void buildMaxHeap(int[] data, int lastIndex) {        //从lastIndex处节点（最后一个节点）的父节点开始        for (int i = (lastIndex - 1) / 2; i >= 0; i--) {            //k保存正在判断的节点            int k = i;            //如果当前k节点的子节点存在            while (k * 2 + 1 <= lastIndex) {                //k节点的左子节点的索引                int biggerIndex = 2 * k + 1;                //如果biggerIndex小于lastIndex，即biggerIndex+1代表的k节点的右子节点存在                if (biggerIndex < lastIndex) {                    //若果右子节点的值较大                    if (data[biggerIndex] < data[biggerIndex + 1]) {                        //biggerIndex总是记录较大子节点的索引                        biggerIndex++;                    }                }                //如果k节点的值小于其较大的子节点的值                if (data[k] < data[biggerIndex]) {                 //交换他们                    swap(data, k, biggerIndex);                //将biggerIndex赋予k，开始while循环的下一次循环，重新保证k节点的值大于其左右子节点的值                    k = biggerIndex;                } else {                    break;                }            }        }    }}

复制代码

实现效果:

4.分析：

堆排序也是一种不稳定的排序算法。

堆排序优于简单选择排序的原因：

直接选择排序中，为了从 R[1..n]中选出关键字最小的记录，必须进行 n-1 次比较，然后在 R[2..n]中选出关键字最小的记录，又需要做 n-2 次比较。事实上，后面的 n-2 次比较中，有许多比较可能在前面的 n-1 次比较中已经做过，但由于前一趟排序时未保留这些比较结果，所以后一趟排序时又重复执行了这些比较操作。

堆排序可通过树形结构保存部分比较结果，可减少比较次数。

堆排序的最坏时间复杂度为 O(nlogn)。堆序的平均性能较接近于最坏性能。由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。

5.稳定性总结：

我们知道堆的结构是节点 i 的孩子为 2i 和 2i+1 节点，大顶堆要求父节点大于等于其 2 个子节点，小顶堆要求父节点小于等于其 2 个子节点。

在一个长为 n 的序列，堆排序的过程是从第 n/2 开始和其子节点共 3 个值选择最大（大顶堆）或者最小（小顶堆），这 3 个元素之间的选择当然不会破坏稳定性。

但当为 n/2-1, n/2-2, ...1 这些个父节点选择元素时，就会破坏稳定性。

有可能第 n/2 个父节点交换把后面一个元素交换过去了，而第 n/2-1 个父节点把后面一个相同的元素没有交换，那么这 2 个相同的元素之间的稳定性就被破坏了。

所以，堆排序不是稳定的排序算法。

七、冒泡排序：

1.基本思想：

在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换

2.实现过程：

原数组值：
32 , 43, 23, 13, 5
第一轮比较：将序列中所有元素两两比较，将最大的放在最后面，得到结果：
32 , 23, 13, 5, 43
如图所示：

第二轮比较：将剩余序列中所有元素两两比较，将最大的放在最后面,得到结果：
23 , 13, 5, 32, 43
如图所示：

第三轮比较：将剩余序列中所有元素两两比较，将最大的放在最后面,得到结果：
13 , 5, 23, 32, 43

如图所示：

第三轮比较：将剩余序列中所有元素两两比较，将最大的放在最后面,得到结果：
5 , 13, 23, 32, 43
如图所示：

3.实现代码：

package cn.hz.demo2;
/** * @author hz * @version 1.0 * * 冒泡排序 * 需求分析： * 设置循环次数。 * 设置开始比较的位数，和结束的位数。 * 两两比较，将最小的放到前面去。 * 重复2、3步，直到循环次数完毕。 * */public class Demo7 {    public static void main(String[] args) {        int[] a={49,38,65,97,76,13,27,49,78,34,12,64,1};  //定义需要排序数组        System.out.println("冒泡排序前");        for (int i:a){            System.out.print(i+"t");        }        int length=a.length;        int temp;        for(int i=0;i<a.length;i++){            for(int j=0;j<a.length-i-1;j++){                if(a[j]>a[j+1]){                    temp=a[j];                    a[j]=a[j+1];                    a[j+1]=temp;                }            }        }        System.out.println("n冒泡排序后");        for (int i:a){            System.out.print(i+"t");        }
    }}

复制代码

实现效果：

4.分析：

冒泡排序是一种稳定的排序方法。

若文件初状为正序，则一趟起泡就可完成排序，排序码的比较次数为 n-1，且没有记录移动，时间复杂度是 O(n)
若文件初态为逆序，则需要 n-1 趟起泡，每趟进行 n-i 次排序码的比较，且每次比较都移动三次，比较和移动次数均达到最大值∶O(n2)
起泡排序平均时间复杂度为 O(n2)

5.稳定性总结：

冒泡排序就是把小的元素往前调（或者把大的元素往后调）。注意是相邻的两个元素进行比较，而且是否需要交换也发生在这两个元素之间。

所以，如果两个元素相等，我想你是不会再无聊地把它们俩再交换一下。

如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个元素相邻起来，最终也不会交换它俩的位置，所以相同元素经过排序后顺序并没有改变。

所以冒泡排序是一种稳定排序算法。

发布于: 4 小时前阅读数: 7

加百利

关注

还未添加个人签名 2021.06.08 加入

还未添加个人简介

评论 (1 条评论)

发布

朝歌

老师您好，我是图书策划编辑，想要邀请您写书，不知道您有没有这个意向呢

10 分钟前

 0 回复

没有更多了

创作场景

JAVA 九种排序算法详解（中）

五、简单选择排序：

1.基本思想：

2.实现过程：

3.实现代码：

4.分析：

5.稳定性总结：

六、堆排序：

1.基本思想：

2.实现过程：

3.实现代码：

4.分析：

5.稳定性总结：

七、冒泡排序：

1.基本思想：

2.实现过程：

3.实现代码：

4.分析：

5.稳定性总结：

加百利

评论 (1 条评论)