排序的不乱性
由于待排序的记录序列中可能存在两个或两个以上的关键字相等的记录， 排序结果可能会存在不独一的情况。所以就有不乱与不不乱的定义。文章源自微观生活（93wg.com）微观生活-https://93wg.com/10606.html
假定ki=kj，且在排序前的序列中ri领先于rj。如果排序后ri仍领先于rj，则称所用的排序办法是不乱的;反之，若可能使得排序后的序列中rj领先于ri，则称所用的排序办法是不不乱的。文章源自微观生活（93wg.com）微观生活-https://93wg.com/10606.html
只要有一组关键字产生相似情况，就可认为此排序办法是不不乱的。文章源自微观生活（93wg.com）微观生活-https://93wg.com/10606.html
内排序以及外排序文章源自微观生活（93wg.com）微观生活-https://93wg.com/10606.html
依据在排序进程中待排序记录是不是全体放在内存中，排序分为内排序以及外排序。文章源自微观生活（93wg.com）微观生活-https://93wg.com/10606.html
内排序是在排序整个进程中，待排序的所有记录全体被放置在内存中。文章源自微观生活（93wg.com）微观生活-https://93wg.com/10606.html
外排序是因为排序的记录个数太多，不能同时放置在内存中，整个排序进程需要在内外存之间屡次交流数据才能进行。文章源自微观生活（93wg.com）微观生活-https://93wg.com/10606.html
对内排序来讲，排序算法的性能主要有3个影响因素：文章源自微观生活（93wg.com）微观生活-https://93wg.com/10606.html
1、时间性能文章源自微观生活（93wg.com）微观生活-https://93wg.com/10606.html
排序算法的时间开消是衡量其好坏的最重要的标志。文章源自微观生活（93wg.com）微观生活-https://93wg.com/10606.html
在内排序中，主要进行两种操作：比较以及移动。
高效力的内排序算法应当拥有尽量少的关键字比较次数以及尽量少的记录移动次数。
2、辅助空间
评估算法的另外一个主要标准是执行算法所需要的辅助存储空间。
辅助存储空间是除了了寄存待排序所占用的存储空间外，执行算法所需要的其他存储空间。
3、算法的繁杂性
指算法自身的繁杂性，过于繁杂的算法也会影响排序的性能。
接下来
1. 冒泡排序Bubble Sort
冒泡排序是一种交流排序，它的基本思想是：
两两比较相邻记录的关键字，如果反序则交流，直到没有反序的记录为止。
算法繁杂度分析：
使用优化后的冒泡排序，最佳的情况下，仅需要n - 1次比较，时间繁杂度为O;最坏情况下，需要n/2次比较以及交流;
所以平均时间繁杂度为O。
2. 简单选择排序Simple Selection Sort
选择排序的基本思想：
每一一次遍用时选取关键字最小的记录作为有序序列的第i个记录。
算法繁杂度分析
简单选择排序最大的特色就是交流移动数据次数少，但它的比较次数是以及数组自身是不是有序是无关的，即不管最佳最差的情况，都要进行n/2次比较;在最佳的情况下，不需要进行交流，在最坏的情况下，进行n-1次交流。
所以平均时间繁杂度为O。
3. 直接插入排序Straight Insertion Sort
直接插入排序的基本操作：
将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录递增1的有序表。
插入排序是进行值移动，而是不值交流。所以在量较小的情况下插入排序性能要优于冒泡以及简单选择排序。
算法繁杂度分析：
在最佳的情况下，只需进行比较n - 1次，无需进行移动;
在最坏的情况下，比较/2次，交流/2次。
所以平均时间繁杂度O
4. 二分插入排序Binary Insert Sort
二分插入排序是一种在直接插入排序算法上进行小改动的排序算法。其与直接排序算法最大的区分在于查找插入位置时使用的是二分查找的方式，在速度上有一定晋升。
算法繁杂度分析：
插入每一个记录需要O比较，至多移动i+1次，起码2次。最好情况O，最差以及平均情况O。
总排序码比较次数比直接插入排序的最差情况好得多，但比最佳情况要差，所元素初始序列已经按排序码接近有序时，直接插入排序比二分插入排序比较次数少
5. 希尔排序Shell Sort
希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改良版本。希尔排序是非不乱排序算法。
希尔排序通过将比较的全体元素分为几个区域来晋升插入排序的性能。这样可让一个元素可以一次性地朝终究位置前进一大步。然后算法再取愈来愈小的步长进行排序，算法的最后一步就是普通的插入排序，然而到了这步，需排序的数据几近是已排好的了。
更好的理解方式
将数组列在一个表中并对行排序。重复这进程，无非每一次用更小的列来进行。最后整个表就只有一列了。
将数组转换至表是为了更好地舆解这算法，算法自身仅仅对原数组进行排序。
比如第一次放在5列中对每一行使用快速排序排序，第二次放在3列中，最后放在1列中。类比于步长从5到3再到1。
算法繁杂度分析
希尔排序的算法繁杂度以及增量序列有关，只要终究步长为1任何步长序列均可以工作。可以参加希尔排序。
6. 堆排序Heap Sort
堆
堆是拥有以下性质的完整二叉树：
每一个节点的值都大于或等于其左右孩子节点的值，成为大顶堆;
每一个节点的值都小于或等于其左右孩子节点的值，成为小顶堆;
完整二叉树性质
按完整二叉树的性质，该树可以被顺序存储在数组中，按不同的角标进行表示。
即：
Parent = /2，i 的父节点下标
Left = 2i + 1，i 的左子节点下标
Right = 2，i 的右子节点下标
基本思想
将待排序的序列构造成一个大顶堆。此时，整个序列的最大值就是堆定的根节点，将它移走，再将剩余n-1个序列从新构造成一个堆，这样就会得到第二大值，以此类推，就能得到一个有序序列了。
算法繁杂度分析
在构建堆时，对每一个非叶子节点来讲，至多进行2次比较以及互换操作，繁杂度为O;
在进行排序时，第i次取堆顶记录从新建堆需要用O时间，并需要取n-1次，所以重建堆的时间为O。
所以堆排序的时间繁杂度为O。
实现步骤：
最大堆调剂：从堆的倒数第一个非叶子节点作调剂，使得子节点永久小于父节点。没有必要从叶子节点开始，叶子节点可以看做是已相符堆特色的节点。
创立最大堆：将堆所有数据从新排序
堆排序：移除了位在第一个数据的根节点，并做最大堆调剂。
7. 归并排序Merge Sort
概念：
归并排序是树立在归并操作上的一种有效的排序算法，该算法是采取分治法的典型利用。
它指的是将两个已经排序的序列合并成一个序列的操作。归并排序算法依赖归并操作。归并排序有多路归并排序、两路归并排序 , 可用于内排序，也能够用于外排序。这里仅对内排序的两路归并办法进行讨论。
算法思路
把 n 个记录看成 n 个长度为 l 的有序子表
进行两两归并使记录关键字有序，得到 n/2 个长度为 2 的有序子表
重复第 2 步直到所有记录归并成一个长度为 n 的有序表为止。
算法繁杂度分析：
在最后一步，需要顺次遍历两个已排序的好的数组，此时的时间繁杂度为O。
同时又进行着二路归并，构成一颗完整二叉树，此时整个排序需要进行log2n次。
所以归并排序的时间繁杂度为O。这是它的最佳、最坏、平均的时间性能。
8. 快速排序Quick Sort
基本思想
通过一趟排序将待排序记录分割成独立的两部份，其中一部份记录的关键字均比另外一部份小，则可分别对这两部份记录继续进行排序，直到整个序列有序。
繁杂度分析
最佳情况：partition每一次划分的都很均匀，如果排序n个关键字，其递归树的深度就为floor+ 1次，此时的繁杂度为O。
如果是最坏情况，每一次partition都只操作一个数字，该递归树即为一颗斜树，比较次数为n/2，时间繁杂度为O。
平均繁杂度为O。
9. 桶排序Bucket Sort
基本思想
工作的原理是将数组分到有限数量的桶里。每一个桶再个别排序。
步骤
设置一个定量的数组当作空桶子。
寻访序列，并且把项目一个一个放到对应的桶子去。
对每一个不是空的桶子进行排序。
从不是空的桶子里把项目再放回原来的序列中。
算法繁杂度
对于N个待排数据，M个桶，平均每一个桶[N/M]个数据的桶排序平均时间繁杂度为：
O+Olog)=O)=O
可以看出，最佳情况即当N=M时，每一个桶只有一个数据时，能够到达O。
10. 计数排序Count Sort
基本思想
计数排序是一种不乱的线性时间排序算法。
计数排序使用一个额外的数组C，其中C数组的第i个元素是待排序数组A中值等于i的元素的个数。然后依据数组C来将A中的元素排到正确的位置。
步骤：
找出待排序的数组中最大以及最小的元素
统计数组中每一个值为i的元素呈现的次数，存入数组 C 的第 i 项
对所有的计数累加
反向填充目标数组：将每一个元素i放在新数组的第C项，每一放一个元素就将C减去1
算法繁杂度分析
当输入的元素是n个0到k之间的整数时，它的运行时间是Θ。计数排序不是比较排序，排序的速度快于任何比较排序算法。
因为用来计数的数组C的长度取决于待排序数组中数据的规模，这使得计数排序对于数据规模很大的数组，需要大量时间以及内存。
西安尚学堂 http://www.xasxt.com/
Java零基础就业班
上课地址：陕西省西安市高新区科技二路西安软件园天泽大厦五楼
咨询电话：029-62258374 QQ 2145598324
招生对象：
1. 零计算机编程基础学
2. 对行业不满意人士
3. 跨专业编程喜好者
4. 在校大学生实训
Java零基础班，10年 Java 以上开发经验技术讲师、架构师、行业大牛，亲身纯面授课程，手把手教你写编程。
10月新班免费试听课程已就绪，7天免费听课，体验Java乐趣。
以上就是微观生活（93wg.com）关于“常见的排序算法简介”的详细内容，希望对大家有所帮助！
评论