第二章 排序
1.选择排序
一种最简单的排序算法是这样的：首先，找到数组中最小的那个元素，其次，将它和数组的第一个元素交换位置（如果第一个元素就是最小元素那么它就和自己交换）。再次，在剩下的元素中找到最小的元素，将它与数组的第二个元素交换位置。如此往复，直到将整个数组排序。这种方法叫做选择排序，因为它在不断地选择剩余元素之中的最小者。
void SelectSort(vector<int>&a, int n)
{
for (int i = 0; i < n - 1; ++i)//一共进行n-1趟
{
int index = i;//记录最小元素位置
for (int j = i + 1; j < n; ++j)//在a[i...n-1]中选择最小的元素
{
if (a[index] > a[j])
{
index = j;//更新最小元素位置
}
}
if (index != i)
{
swap(a[i], a[index]);//与第i个位置交换
}
}
}
//测试代码
int main() {
vector<int>v{14,5,6,89,34,55,674,345};
SelectSort(v,v.size());
for(auto c:v)
cout<<c<<" ";
}
//输出结果：5 6 14 34 55 89 345 674 2.插入排序
与选择排序一样，当前索引左边的所有元素都是有序的，但它们的最终位置还不确定，为了给更小的元素腾出空间，它们可能会被移动。但是当索引到达数组的右端时，数组排序就完成了。和选择排序不同的是，插入排序所需的时间取决于输入中元素的初始顺序。例如，对一个很大且其中的元素已经有序（或接近有序）的数组进行排序将会比对随机顺序的数组或是逆序数组进行排序要快得多。
void InsertSort(vector<int>&a)
{
for (int i = 1; i < a.size(); ++i)
{
for (int j = i ; j >= 0; --j)
{
if(a[i]<a[j])
{
std::swap(a[i], a[j]);
i=j;
}
}
}
}
int main() {
vector<int>v{5,6,3,1,2,9,0,12,4,0};
InsertSort(v);
for(auto c:v)
cout<<c<<" ";
return 0;
}
//输出结果：0 0 1 2 3 4 5 6 9 12总的来说，插入排序对于部分有序的数组十分高效，也很适合小规模数组。这很重要，因为这些类型的数组在实际应用中经常出现，而且它们也是高级排序算法的中间过程。我们会在学习高级排序算法时再次接触到插入排序。
3.希尔排序
对于大规模乱序数组插入排序很慢，因为它只会交换相邻的元素，因此元素只能一点一点地从数组的一端移动到另一端。例如，如果主键最小的元素正好在数组的尽头，要将它挪到正确的位置就需要N-1次移动。希尔排序为了加快速度简单地改进了插入排序，交换不相邻的元素以对数组的局部进行排序，并最终用插入排序将局部有序的数组排序。
希尔排序的思想是使数组中任意间隔为h的元素都是有序的。这样的数组被称为h有序数组。换句话说，一个h有序数组就是h个互相独立的有序数组编织在一起组成的一个数组。
void shellsort(vector<int>&a)
{
for(int gap=a.size()/3;gap>0;gap/=3)
{
for (int i = gap; i < a.size(); ++i)
{
for (int j = i ; j >= 0; j-=gap)
{
if(a[i]<a[j])
{
std::swap(a[i], a[j]);
i=j;
}
}
}
}
}
int main() {
vector<int>v{5,6,3,1,2,9,0,12,4,0};
shellsort(v);
for(auto c:v)
cout<<c<<" ";
return 0;
}
//输出结果：0 0 1 2 3 4 5 6 9 12 4.归并排序
在本节中我们所讨论的算法都基于归并这个简单的操作，即将两个有序的数组归并成一个更大的有序数组。很快人们就根据这个操作发明了一种简单的递归排序算法：归并排序。要将一个数组排序，可以先（递归地）将它分成两半分别排序，然后将结果归并起来。
void mergesort(vector<int>&v,int l,int r)
{
if(r-l<2)return;
auto mi=l+(r-l)/2;
mergesort(v,l,mi);
mergesort(v,mi,r);
merge(v,l,mi,r);
}
void merge(vector<int>&nums,int l,int mi,int r)
{
int *temp=new int [r-l];
int t=0;
for(int i=l,j=mi;i<mi||j<r;++t)
{
if(i==mi){temp[t]=nums[j];++j;continue;}
if(j==r){temp[t]=nums[i];++i;continue;}
if(nums[i]<nums[j]){temp[t]=nums[i];++i;}
else {temp[t]=nums[j];++j;}
}
for(int k=0;k<r-l;++k)
nums[k+l]=temp[k];
delete []temp;
}
int main() {
vector<int>v{5,6,3,1,2,9,0,12,4,0};
mergesort(v,0,v.size());
for(auto c:v)
cout<<c<<" ";
return 0;
}
//输出结果：0 0 1 2 3 4 5 6 9 12 5.快速排序
快速排序流行的原因是它实现简单、适用于各种不同的输入数据且在一般应用中比其他排序算法都要快得多。快速排序引人注目的特点包括它是原地排序（只需要一个很小的辅助栈），且将长度为N的数组排序所需的时间和MgN成正比。我们已经学习过的排序算法都无法将这两个优点结合起来。另外，快速排序的内循环比大多数排序算法都要短小，这意味着它无论是在理论上还是在实际中都要更快。它的主要缺点是非常脆弱，在实现时要非常小心才能避免低劣的性能。已经有无数例子显示许多种错误都能致使它在实际中的性能只有平方级别。幸好我们将会看到，由这些错误中学到的教训也大大改进了快速排序算法，使它的应用更加广泛。
快速排序是一种分治的排序算法。它将一个数组分成两个子数组，将两部分独立地排序。快速排序和归并排序是互补的：归并排序将数组分成两个子数组分别排序，并将有序的子数组归并以将整个数组排序；而快速排序将数组排序的方式则是当两个子数组都有序时整个数组也就自然有序了。在第一种情况中，递归调用发生在处理整个数组之前；在第二种情况中，递归调用发生在处理整个数组之后。在归并排序中，一个数组被等分为两半；在快速排序中，切分（partition）的位置取决于数组的内容。
int partition1(std::vector<int>&a,int io, int hi)//轴点选取算法，版本1
{
int pivot = a[io];
while (io < hi)
{
while (io < hi&&a[hi] >= pivot)hi--;
a[io] = a[hi];
while (io < hi&&a[io] <= pivot)io++;
a[hi] = a[io];
}
a[io] = pivot;
return io;
}
int partition2(std::vector<int>&a, int io, int hi) //版本2
{
int pivot = a[io],mi=io;
for (int k = io + 1; k <= hi; k++)
{
if (pivot > a[k])
{
std::swap(a[k], a[++mi]);
}
}
std::swap(a[io], a[mi]);
return mi;
}
void quicksort(std::vector<int>&a, int io, int hi)
{
if (hi - io <= 1)return ;
auto mi=partition1(a, io, hi-1);
quicksort(a, io, mi);
quicksort(a, mi+1, hi);
}
int main() {
vector<int>v{5,6,3,1,2,9,0,12,4,0};
quicksort(v,0,v.size());
for(auto c:v)
cout<<c<<" ";
return 0;
}
//输出结果：0 0 1 2 3 4 5 6 9 12 快速排序是由C.A.RHoare在1960年发明的，从那时起就有很多人在研究并改进它。改进快速排序总是那么吸引人，发明更快的排序算法就好像是计算机科学届的“老鼠夹子”，而快速排序就是夹子里的那块奶酪。几乎从Hoare第一次发表这个算法开始，人们就不断地提出各种改进方法。并不是所有的想法都可行，因为快速排序的平衡性已经非常好，改进所带来的提高可能会被意外的副作用所抵消。但其中一些，也是我们现在要介绍的，非常有效。
如果你的排序代码会被执行很多次或者会被用在大型数组上（特别是如果它会被发布成一个库函数，排序的对象数组的特性是未知的），那么下面所讨论的这些改进意见值得你参考。需要注意的是，你需要通过实验来确定改进的效果并为实现选择最佳的参数。一般来说它们能将性能提升20%~30%。
1.切换到插入排序
1.和大多数递归排序算法一样，改进快速排序性能的一个简单办法基于以下两点：
2.对于小数组，快速排序比插入排序慢；
因为递归，快速排序的sort（）方法在小数组中也会调用自己。
因此，在排序小数组时应该切换到插入排序。简单地改动算法2.5就可以做到这一点：将sort（）中的语句
if（hi <= 1o）return；替换成下面这条语句来对小数组使用插入排序：
if（hi <= 1o+M）{Insertion.sort（a，1o，hi）；return；}
转换参数M的最佳值是和系统相关的，但是5~15之间的任意值在大多数情况下都能令人满意
2.三取样切分
改进快速排序性能的第二个办法是使用子数组的一小部分元素的中位数来切分数组。这样做得到的切分更好，但代价是需要计算中位数。人们发现将取样大小设为3并用大小居中的元素切分的效果最好。
3.熵最优的排序
实际应用中经常会出现含有大量重复元素的数组，例如我们可能需要将大量人员资料按照生日排序，或是按照性别区分开来。在这些情况下，我们实现的快速排序的性能尚可，但还有巨大的改进空间。例如，一个元素全部重复的子数组就不需要继续排序了，但我们的算法还会继续将它切分为更小的数组。在有大量重复元素的情况下，快速排序的递归性会使元素全部重复的子数组经常出现，这就有很大的改进潜力，将当前实现的线性对数级的性能提高到线性级别。
一个简单的想法是将数组切分为三部分，分别对应小于、等于和大于切分元素的数组元素。这种切分实现起来比我们目前使用的二分法更复杂，人们为解决它想出了许多不同的办法。这也是E.W.Dijkstra的荷兰国旗问题引发的一道经典的编程练习，因为这就好像用三种可能的主键值将数组排序一样，这三种主键值对应着荷兰国旗上的三种颜色。
6.堆排序
我们可以把任意优先队列变成一种排序方法。将所有元素插入一个查找最小元素的优先队列，然后再重复调用删除最小元素的操作来将它们按顺序删去。用无序数组实现的优先队列这么做相当于进行一次插入排序。用基于堆的优先队列这样做等同于哪种排序？一种全新的排序方法！下面我们就用堆来实现一种经典而优雅的排序算法——堆排序。
堆排序可以分为两个阶段。在堆的构造阶段中，我们将原始数组重新组织安排进一个堆中；然后在下沉排序阶段，我们从堆中按递减顺序取出所有元素并得到排序结果。为了和我们已经学习过的代码保持一致，我们将使用一个面向最大元素的优先队列并重复删除最大元素。为了排序的需要，
我们不再将优先队列的具体表示隐藏，并将直接使用swim（）和sink）操作。这样我们在排序时就可以将需要排序的数组本身作为堆，因此无需任何额外空间。
#define parent(i) ((i-1)>>1)
#define last(n) (parent(n-1))
#define lchild(i) ((2*i)+1)
#define rchild(i) ((2*i)+2)
int down(std::vector<int> &a, int i);
int up(std::vector<int> &a, int i);
void insert(std::vector<int> &a, int x);
void remove(std::vector<int> &a);
int getmax(std::vector<int>a);
/* Floyd建堆算法的实现,每一个节点进行下滤操作
*/
void heap(std::vector<int> &a,int n)
{
for (int i =last(n); i >= 0 && i < n; i--)
{
down(a, i);
}
}
//上滤操作
int up(std::vector<int> &a, int i)
{
auto n = a.size();
while (parent(i) >= 0 && parent(i) < n)
{
if (a[i] > a[parent(i)])
{
std::swap(a[i], a[parent(i)]);
i = parent(i);
}
else break;
}
return i;
}
int down(std::vector<int> &a, int i)
{
auto n = a.size();
while (1)
{
if (0 <= lchild(i) && lchild(i) < n && (a[i] < a[lchild(i)]))
{
if (0 <= rchild(i) && rchild(i) < n && (a[lchild(i)] < a[rchild(i)]))
{
std::swap(a[i], a[rchild(i)]);
i = rchild(i);
}
else if (0 > rchild(i) || rchild(i) >= n)
{
std::swap(a[i], a[lchild(i)]);
i=lchild(i);
}
else if ((a[lchild(i)] > a[rchild(i)]))
{
std::swap(a[i], a[lchild(i)]);
i = lchild(i);
}
}
else if (0 <= rchild(i) && rchild(i) < n && (a[i] < a[rchild(i)]))
{
std::swap(a[i], a[rchild(i)]);
i = rchild(i);
}
else break;
}
return i;
}
void insert(std::vector<int> &a,int x)
{
auto n = a.size();
a.push_back(x);
up(a, a.size()-1);
}
void remove(std::vector<int> &a)
{
auto n = a.size();
if (n == 0)return;
std::swap(a[0], a[n - 1]);
a.pop_back();
down(a, 0);
}
int getmax(std::vector<int>a)
{
if (a.size() == 0)return -1;
else return a[0];
}
int main() {
vector<int>v{5,6,3,1,2,9,0,12,4,0};
heap(v,v.size());
for(auto c:v)
cout<<c<<" ";
return 0;
}
//输出结果：12 6 9 5 2 3 0 1 4 0 
京公网安备 11010502036488号