今天打算把排序算法复习一下，顺便整理一下
排序稳定性是指两个相等的元素排序之后二者的相对顺序是否不变
排序可以大致分为
1、插入排序（直接插入排序、希尔排序）
2、选择排序（简单选择排序、堆排序）
3、交换排序（冒泡排序、快排）
4、归并排序（归并排序）
首先讨论一下交换的问题
对于整型交换最简单的就是采用临时变量、其次可以采用代数运算或者异或运算。在代数运算中需要考虑溢出的问题。具体代码如下
void swapNormal(int &a, int &b)
{
if(a==b) return;
int temp = a;
a = b;
b = a;
}
void swapAlgebra(int &a, int &b)
{
if(a==b) return;
if ((a>0&&b>0)||(a<0&&b<0))//避免溢出
{
a = a-b;
b = a+b;
a = b-a;
}else
{
a = a+b;
b = a-b;
a = a-b;
}
}
void swapXor(int &a, int &b)
{
if (a==b) return;
a ^= b;
b ^= a;
a ^= b;
}
对于其他类型可以写成一个模板函数
template<typename T>
void swapT(T &a, T&b)
{
if(a==b) return;
T temp = a;
a = b;
b = temp;
}
对于c++中string，vector，map，set他们一般都自带swap函数，在高效c++中对他们有详细的探讨，具体用法是：对象实例.swap(另一个对象实例),这个是针对一个对象不是指对象里面的元素。下面开始说排序问题
冒泡排序
- 思路：前后对比，执行两次循环即可，有两种改进：1、如果有一趟比较没有发生交换则可以认为已经有序，可以设置flag标志，有序的时候结束。2、每一躺排序，最后交换的一个位置的后面已经有序，所以下一次仅需要遍历到这个位置即可，但需注意如果没有发生交换则已经结束，故每一趟比较开始时需要把这个光标设置为0。
- 时间复杂度：O(n^2)，效率较低，数据规模较小的时候使用
//大到小排序
void bubble(vector<int> &v)
{
int i,j;
for (i = 0; i<v.size();i++)
for (j=v.size()-1;j>i;j--)
if(v[j]>v[j-1])
swapT(v[j],v[j-1]);
}
void bubbleflag(vector<int> &v)
{
int j=v.size(),i;
bool flag = true;
while(flag)
{
flag = false;
for (i=1; i<j; i++)
if (v[i]>v[i-1])
{
swapT(v[i],v[i-1]);
flag = true;
}
j--;
}
}
void bubblefast(vector<int> &v)
{
int flag=v.size(),i,k;
while (flag>0)
{
k = flag;
flag = 0;
for (i=1; i<k; i++)
if (v[i]>v[i-1])
{
swapT(v[i],v[i-1]);
flag = i;
}
}
}
选择排序
- 思路：bubble排序，每一次比较都在不断交换，没有效率。另一个角度，就是先将序列分为有序区（开始无元素）和无序区。在无序区每一趟比较中，先找到最大的或者最小的，然后再将其与序列首部有序部分的尾部的下一个位置的值进行交换。
- 时间复杂度O(n^2)
void selectsort(vector<int> &v)
{
int i,j,maxN;
for(i=0; i<v.size()-1; i++)
{
maxN = i;
for (j=i+1;j<v.size();j++)
{
if (v[maxN]<v[j])
maxN = j;
}
if (i!=maxN)
swapT(v[maxN],v[i]);
}
}
直接插入排序
- 思路：与选择排序类似，将序列分为有序区和无序区，只不过每次将无序区内的一个元素取出，放到有序区形成新的有序区，与选择排序不同的这回所有的操作集中在有序区。
- 操作过程：先找到插入位置，然后将数据后移并插入
- 时间复杂度：O(n^2)
//插入排序
void insertsort(vector<int> &v)
{
int i,j;
for(i=1; i<v.size();i++)
{
//找到要插入的位置
for (j=0; j<i; j++)
{
if (v[i]>v[j])
break;
}
//将数据后移并插入
if(j!=i-1)
{
int temp = v[i];
//后移
for(int m=i;m>j;m--)
v[m]=v[m-1];
v[j] =temp;
}
}
}
//对上面进行写法是优化
void insertsortmd(vector<int> &v)
{
int i,j;
for(i=1; i<v.size();i++)
{
for (j=i; j>0; j--)
{
if (v[j]>v[j-1])
swapT(v[j],v[j-1]);
}
}
}
shell排序
- 思路：实质是分组插入排序，分组方法如下：
以长度为10的序列为例0 1 2 3 4 5 6 7 8 9
第一次分组间隔 10/2=5 获得5个分组
{0 5} {1 6} {2 7} {3 8} {4 9}
分别对每组数据进行插入排序，对排序后是序列{0 1 2 3 4 5 6 7 8 9 }进行第二次分组
第三次分组间隔 5/2=2 获得2个分组
{0 2 4 6 8} {1 3 5 7 9}
分别对每组数据进行插入排序，对排序后是序列{0 1 2 3 4 5 6 7 8 9 }进行第三次分组
第一次分组间隔 2/2=1 获得1个分组
{0 1 2 3 4 5 6 7 8 9}
对上组数据进行插入排序，结束。
- 算法复杂度：O(nlogn~n^2)
- 稳定性：非稳定排序算法
void shellsort(vector<int> &v)
{
int i,j,k,gap;
for(gap = v.size()/2; gap!=0; gap /=2) //分组间隔
for (i = 0; i<gap; i++) //每一个分组的元素
for(j = i+gap;j<v.size();j+=gap) //对每个分组元素进行插入排序
for(k = j;k>i;k-=gap)
if (v[k]>v[k-gap])
swapT(v[k],v[k-gap]);
}
//对上述写法进行优化
void shellsortmd(vector<int> &v)
{
int i,j,k,gap;
for(gap = v.size()/2; gap!=0; gap /=2) //分组间隔
for (i = gap; i<v.size(); i++) //插入排序
for(k = i;k>=gap;k-=gap)
if (v[k]>v[k-gap])
swapT(v[k],v[k-gap]);
}
shell排序的效率受分组的gap影响。维基百科中有如下描述
已知的最好步长串行是由Sedgewick提出的 (1, 5, 19, 41, 109,...)，该串行的项来自 9 * 4^i - 9 * 2^i + 1 和 4^i - 3 * 2^i + 1 这两个算式[1].这项研究也表明“比较在希尔排序中是最主要的操作，而不是交换。”用这样步长串行的希尔排序比插入排序和堆排序都要快，甚至在小数组中比快速排序还快，但是在涉及大量数据时希尔排序还是比快速排序慢。
另一个在大数组中表现优异的步长串行是(斐波那契数列除去0和1将剩余的数以黄金分区比的两倍的幂进行运算得到的数列)：（1, 9, 34, 182, 836, 4025, 19001, 90358, 428481, 2034035, 9651787, 45806244, 217378076, 1031612713, …）[2]
归并排序
- 思路：归并排序是采用分治法的典型应用。归并排序的思想就是先递归分解数组，再合并数组。重点在于合并，由于两部分均有序，就是谁大取谁，不过很有可能需要引入一个临时的存储空间，在分配空间的时候有可能导致运行时间增加。典型的两个子序列合并如下
void MergeT(int a[],int m, int b[], int n,int c[])
{
int i = 0,j=0,k=0;
while(i<m&&j<n)
if (a[i]>a[j])
c[k++]=a[i++];
else
c[k++]=b[j++];
while (i<m)
c[k++]=a[i++];
while (j<n)
c[k++]=b[j++];
}
//归并排序
void Merge(vector<int> &v,int s,int e)
{
int mid = (e+s)/2;
int i=s,j=mid+1,k=0;
vector<int> temp;
while(i<=mid && j<=e)
{
if (v[i]<v[j])
temp.push_back(v[j++]);
else
temp.push_back(v[i++]);
}
while(i<=mid)
temp.push_back(v[i++]);
while(j<=e)
temp.push_back(v[j++]);
while(s<=e)
v[s++]=temp[k++];
}
void mergesort(vector<int> &v,int s,int e)
{
if (e>s)
{
int mid = (e+s)/2;
mergesort(v,s,mid);
mergesort(v,mid+1,e);
Merge(v,s,e);
}
}
快速排序
- 思路：左右互攻，挖坑填数+分治法,一从大到小为例
1、从序列中选择一个数M，将该数与序列中第一个数交换；
2、从右边开始寻找一个比M大的数，将该数交换到左边存储M的位置，左边位置+1；
3、从左边开始寻找一个不大于M的数，将该数交换到右边存储M的位置，右边位置-1；
4、重复2-3，知道左右相遇，假设相遇位置为n。
5、把n左右两边两个子序列{begin,i-1} {i+1,end}重复1-5直达左右两边只有一个数。
下图来自经典排序算法总结与实现
Quicksort-example.gif
- 复杂度：O(nlogn)
- ps：最好的情况下复杂度为O(nlogn)，但最坏的情况下为O(n^2).空间复杂度而言主要是递归导致堆栈的使用。快排还有许多其他的改进版本，例如基准数选取，可以采用三数取中，或者9数取中的方式，避免基准过大或者过小。当数据规模较小的时候，再使用快排就有点大材小用了（由于递归的原因），因此可以考虑简单的排序方法，插入排序是简单排序中性能最好的——引自《大话数据结构》。
//快速排序
void quicksort(vector<int> &v,int begin, int end)
{
if (begin < end)
{
int i = begin,j = end;
int mid = v[begin];
while(i!=j)
{
while(i!=j)
{
if (v[j]>=mid)
{
v[i++] = v[j];
//swapT(v[j],v[i++]);
break;
}
j--;
}
while(i!=j)
{
if (v[i]<mid)
{
//swapT(v[j--],v[i]);
v[j--] = v[i];
break;
}
i++;
}
}
v[i] = mid;
quicksort(v,begin,i-1);
quicksort(v,i+1,end);
}
}
//针对小数据的优化，和写法上的优化
const int BIGNUM = 50;
void quicksortmd(vector<int> &v,int begin, int end)
{
if (end-begin>BIGNUM)
{
if (begin < end)
{
int i = begin,j = end;
int mid = v[begin];
while(i!=j)
{
while(i!=j&&mid>v[j])
j--;
if(i<j) v[i++] = v[j];
while(i!=j&&v[i]>=mid)
i++;
if(i<j) v[j--] = v[i];
}
v[i] = mid;
quicksort(v,begin,i-1);
quicksort(v,i+1,end);
}
}
else
{
for(int i=begin+1; i<=end;i++)
for (int j=i; j>begin && v[j]>v[j-1]; j--)
swapT(v[j],v[j-1]);
}
}
- 对于递归操作的优化，由于递归需要使用堆栈资源，当极端的情形下，递归深度为n（好的情况logn），因此在某些情形下，需要对递归进行优化减少递归的次数，采用while循环，即互攻过程可以多次使用
//快速排序,对小规模数据和递归进行优化，选择while循环
void quicksortmd2(vector<int> &v,int begin,int end)
{
if (end - begin > BIGNUM)
{
while(begin<end)
{
int i = begin,j = end;
int mid = v[begin];
while (i!=j)
{
while(i!=j&&v[j]<mid)
j--;
if(i<j) v[i++] = v[j];
while(i!=j&&v[i]>=mid)
i++;
if(i<j) v[j--] = v[i];
}
v[i] = mid;
quicksortmd2(v,begin,i-1);
begin = i+1;
}
}
else
for (int i = begin+1; i<=end; i++)
for (int j = i; j>begin &&v[j]>v[j-1]; j--)
swapT(v[j],v[j-1]);
}
- 堆排序
思路：堆排序是采用二叉堆，即近似完全二叉树 。
二叉堆具有以下性质：
1、父节点值总是大于或等于（小于或等于）任何一个子节点值。
2、每个节点的左右子树都是一个二叉堆（都是最大堆或最小堆）。
排序方法
将待排序的数组{0到n-1}构成大根堆（或者小跟堆），将堆首和堆尾交换，重新调整剩下的{0到n-2}重新构成大根堆（或者小跟堆），继续上述步骤知道数组首位
需解决两个问题
1、如何由一个无序序列构成一个小、大根堆；
2、调整剩余元素为小、大根堆
//堆排序
void heapAdjust(vector<int> &v,int begin,int end)
{
for (int j = begin*2+1; j<=end; j=2*j+1) //找到begin的子节点
{
if (j<end&&v[j]>v[j+1]) //找到左右孩子中更小的那个
j++;
if (v[begin] <= v[j]) //表明满足小根堆条件了
break;
swapT(v[j],v[begin]);
begin = j;
}
}
void heapsort(vector<int> &v)
{
for (int i = v.size()/2-1;i>=0;i--) //构建小根堆，刚刚开始时认为叶子几点都已经是小根堆了，所以从v.size()/2-1开始
heapAdjust(v,i,v.size()-1);
for (int i = v.size()-1;i>0;i--) //每一次将堆首移到已排序区，重新调整堆
{
swapT(v[i],v[0]);
heapAdjust(v,0,i-1);
}
}
总结
简单排序有：bubble排序、直接选择排序、直接插入排序
复杂排序有：shell排序（性能略差）、归并排序、快排、堆排序
sort-summary.png
从最好的角度看，冒泡和直接插入排序较好，因此在数据较少时，且整体有序时候，可以考虑冒泡或者直接插入排序
在最坏的情形下，堆排序和归并排序较好。其实从另外一个角度说明是逆序的情形下，是否可以考虑先逆转在进行排序。
递归角度考虑，采用递归实现的包括：归并排序和快排，需要考虑递归深度问题。
reference
1、经典排序算法总结与实现
2、MoreWindows Blog
3、《大话数据结构》
网友评论