算法和数据结构第二讲——排序算法1 by hez2010
本帖最后由 hez2010 于 2016-10-31 10:00 编辑这里主要介绍的是各种排序算法，本帖中包含选择排序、冒泡排序、直接插入排序和采用二分思想的快速排序
提前说明一下，本讲中所有的例子都是将数组从大到小排序！
排序算法（第一部分）
选择排序：每次从数组中选出一个最大或最小值放到最前面，以此类推，最后就按顺序排完了
#include<iostream>
using namespace std;
int main(){
int a[ ]={4,5,6,3,7,2,2,3,5,4,6,7,8,7,5,4,5,6,2,1,4,55,6,4,3,6,5,7,8},n=29;
for (int i=0;i<n;i++){
int k=0,max=0;
for (int j=i;j<n;j++){
if (max<a[ j]) k=j,max=a[ j];
}
a[ k]=a[ i];
a[ i]=max;
}
for (int i=0;i<n;i++) cout<<a[ i]<<" ";
}
冒泡排序：
重复地遍历要排序的数组 for (int i=0;i<n;i++)，一次比较两个元素（a[ i]和a[ i+1]），如果他们的大小顺序错误就把他们交换过来。
重复上述操作进行直到没有再需要交换的元素为止，排序完成。为什么叫冒泡排序呢？因为这种排序方式一次交换相邻两个元素，数组中的元素就像冒泡泡一样一个一个浮上来~
#include<iostream>
using namespace std;
int main(){
int n=30,a[ ]={4,5,6,3,7,2,2,3,5,4,6,7,8,7,5,4,5,6,2,1,4,55,6,4,3,6,5,7,8,88};
for (int j=0;j<n-1;j++)
for (int i=0;i<n-1-j;i++){
if(a[ i]<a[ i+1]){
int temp;
temp=a[ i];
a[ i]=a[ i+1];
a[ i+1]=temp;
}
}
for (int i=0;i<n;i++) cout<<a[ i]<<" ";
}
插入排序：
当有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序，这个时候就要用到一种新的排序方法——插入排序法,插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为O(n^2)。
插入排序每次将一个待排序的数组，按其值的大小插入到前面已经排序的数组中适当位置上，直到全部插入完为止。
插入排序分为直接插入排序，二分插入排序（又称折半插入排序），链表插入排序，希尔排序（又称缩小增量排序）。都属于稳定排序（也就是排序后，原有的数据的相对位置不会变）
这里只复习一下直接插入排序。
假设现在有个数组a[ ]={1,2,3,4,5}已经有序了，我想在其中插入一个3，很明显，要把这个3放在原来的2和3之间。
依照这个思想，我们对一个数组进行排序。
步骤：
（1） 设置监视哨a[ 0]，将待插入的值赋值给a[ 0]；
（2） 设置开始查找的位置j；
（3） 在数组中进行搜索，搜索中将第j个数据后移，直至a[ 0]<=a[ j]为止；
（4） 将a[ 0]插入r[ j+1]的位置上。
代码很简单
#include<iostream>
using namespace std;
int main(){
int n=30,a[ ]={4,5,6,3,7,2,2,3,5,4,6,7,8,7,5,4,5,6,2,1,4,55,6,4,3,6,5,7,8,88};
for (int i=1;i<n;i++) {
int temp=a[ i];
int j=i-1;
while (j>=0&&temp>a[ j]){
a[ j+1]=a[ j];
j--;
}
a[ j+1]=temp;
}
for (int i=0;i<30;i++) cout<<a[ i]<<" ";
}
但是，以上三种算法的时间复杂度都是O(n^2)，很不理想，数据规模稍微一大就要排很久。
快速排序（quick sort）
何为快速排序？顾名思义就是快速的排序23333。快速排序其实是对冒泡排序的改进。
现在有一个数组a，我要将他从小到大排序，而且要快，怎么办呢？
考虑分治思想，这里用的是二分。
通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，直到分割出来的部分中只剩下一个元素为止。
举例：a[ ]={4,5,6,3,7,2,2,3,5,4,6,7,8,7,5,4,5,6,2,1,4,55,6,4,3,6,5,7,8,88}
首先我们从a这个数组中取出算便取出一个元素（与大小无关），比如a中有30个元素，下标从0一直到29，那么我想从中取出a[ 14]，记作key，刚开始的时候，我们让l=0，r=29，作为左右区间的位置。
开始的时候i=l,j=r
{
从j开始向前搜索，即由后开始向前搜索(j--)，找到第一个大于key的值a[ j]；
从i开始向后搜索，即由前开始向后搜索(i++)，找到第一个小于key的a[ i]；
如果 i<=j，将a[ i]和a[ j]互换
}
重复以上大括号内的内容，直到i>j为止（也就是这个区间找完了）
这就是一趟排序，这一趟排完后，我们再对区间[ i,r ]和[ l,j ]分别进行上述同样的排序操作，最后就排完了。
【又是一脸懵逼】
看图：
如图所示，带下划线的是划分的区域，是待排序的部分，绿色的是选取的key，我这个例子中的key取的是区间的中间那个值，这样一来，就很清晰了。
顺便再放一张特别厉害的图解释这个过程：
上代码：
#include<iostream>
using namespace std;
void quicksort(int a[ ],int l,int r){
int i=l,j=r,mid=a[ (l+r)/2];
do {
while (a[ i]>mid) i++;
while (a[ j]<mid) j--;
if (i<=j){
int temp=a[ i];
a[ i]=a[ j];
a[ j]=temp;
i++,j--;
}
}while (i<=j);
if (i<r) quicksort(a,i,r);
if (j>l) quicksort(a,l,j);
}
int main(){
int n=30,a[ ]={4,5,6,3,7,2,2,3,5,4,6,7,8,7,5,4,5,6,2,1,4,55,6,4,3,6,5,7,8,88};
quicksort(a,0,n-1);
for (int i=0;i<30;i++) cout<<a[ i]<<" ";
}
时间复杂度：O(nlog n)，最坏情况：O(n^2)
注意：快速排序属于不稳定排序算法，排序后原有数据的相对位置可能会改变。
快速排序的优化：
这部分内容有了上面的基础，相信很好理解，我就直接粘百科了2333
1、三平均分区法
关于这一改进的最简单的描述大概是这样的：与一般的快速排序方法不同，它并不是选择待排数组的第一个数作为中轴，而是选用待排数组最左边、最右边和最中间的三个元素的中间值作为中轴。这一改进对于原来的快速排序算法来说，主要有两点优势：
（1） 首先，它使得最坏情况发生的几率减小了。
（2） 其次，未改进的快速排序算法为了防止比较时数组越界，在最后要设置一个哨点。
2、根据分区大小调整算法
这一方面的改进是针对快速排序算法的弱点进行的。快速排序对于小规模的数据集性能不是很好。可能有人认为可以忽略这个缺点不计，因为大多数排序都只要考虑大规模的适应性就行了。但是快速排序算法使用了分治技术，最终来说大的数据集都要分为小的数据集来进行处理。由此可以得到的改进就是，当数据集较小时，不必继续递归调用快速排序算法，而改为调用其他的对于小规模数据集处理能力较强的排序算法来完成。Introsort就是这样的一种算法，它开始采用快速排序算法进行排序，当递归达到一定深度时就改为堆排序来处理。这样就克服了快速排序在小规模数据集处理中复杂的中轴选择，也确保了堆排序在最坏情况下O(n log n)的复杂度。
另一种优化改进是当分区的规模达到一定小时，便停止快速排序算法。也即快速排序算法的最终产物是一个“几乎”排序完成的有序数列。数列中有部分元素并没有排到最终的有序序列的位置上，但是这种元素并不多。可以对这种“几乎”完成排序的数列使用插入排序算法进行排序以最终完成整个排序过程。因为插入排序对于这种“几乎”完成的排序数列有着接近线性的复杂度。这一改进被证明比持续使用快速排序算法要有效的多。
另一种快速排序的改进策略是在递归排序子分区的时候，总是选择优先排序那个最小的分区。这个选择能够更加有效的利用存储空间从而从整体上加速算法的执行。
3、不同的分区方案考虑
对于快速排序算法来说，实际上大量的时间都消耗在了分区上面，因此一个好的分区实现是非常重要的。尤其是当要分区的所有的元素值都相等时，一般的快速排序算法就陷入了最坏的一种情况，也即反复的交换相同的元素并返回最差的中轴值。无论是任何数据集，只要它们中包含了很多相同的元素的话，这都是一个严重的问题，因为许多“底层”的分区都会变得完全一样。
对于这种情况的一种改进办法就是将分区分为三块而不是原来的两块：一块是小于中轴值的所有元素，一块是等于中轴值的所有元素，另一块是大于中轴值的所有元素。另一种简单的改进方法是，当分区完成后，如果发现最左和最右两个元素值相等的话就避免递归调用而采用其他的排序算法来完成。
4、并行的快速排序
由于快速排序算法是采用分治技术来进行实现的，这就使得它很容易能够在多台处理机上并行处理。
在大多数情况下，创建一个线程所需要的时间要远远大于两个元素比较和交换的时间，因此，快速排序的并行算法不可能为每个分区都创建一个新的线程。一般来说，会在实现代码中设定一个阀值，如果分区的元素数目多于该阀值的话，就创建一个新的线程来处理这个分区的排序，否则的话就进行递归调用来排序。
对于这一并行快速排序算法也有其改进。该算法的主要问题在于，分区的这一步骤总是要在子序列并行处理之前完成，这就限制了整个算法的并行程度。解决方法就是将分区这一步骤也并行处理。改进后的并行快速排序算法使用2n个指针来并行处理分区这一步骤，从而增加算法的并行程度。
详细的优化实现方式，可以参考微软公开的库函数qsort源码。
顺便引用一篇博文：http://blog.csdn.net/claien/article/details/16993263
最重要的事情：你看懂学会了技能get提升了，让我的吾爱币、热心值也提升一下子呗~~（反正评分又不会消耗你的）
谢谢楼主分享!,优秀的C++排序算法 不错，不错。 鼓励发帖，共同提高 算法，一直过不去的坎 mark 一下，复习下算法 谢谢分享，学习了，哈哈 收藏，学习学习 谢谢分享，学习了，{:17_1062:}{:17_1062:} {:1_912:}温故而知新。
页:
[1]