快速、堆排序算法，能用的来，不能用的免语

分而治之算法
分治算法是一种利用递归的问题解决算法。当这些递归调用将数据分隔成一些互相独立的集合从而处理这些较小的数据集合时候，分治算法将会很高效。
用动态程序设计的新技术来对付那些设计数据重叠的分治算法

1：创建标尺
最简单的分治算法的运用
void drawRular(double low, doulbe high, int h)
{
if(h>=1)
{
midpt = (high+low)/2;
drawMark(midpt, h);
drawRular(low, midpt, h-1);
drawRular(midpt, high, h-1);
}
}
2:归并算法
给出可执行程序：
#include <vector>
#include <iostream>
#include <time.h>

using namespace std;

template <typename T>
void mergeSort(vector<T>& v, int first, int last)
{
if(first+1 < last)
{
int mid = (first+last)/2;
mergeSort(v, first, mid);
mergeSort(v, mid, last);
merges(v, first, mid, last);
}
}

template <typename T>
void merges(vector<T>& v, int first, int mid, int last)
{
vector<T> tmp;
// tmp.resize(v.size());
int i, j, k;
i=first;
j=mid;
while(i<mid && j<last)
{
if(v[i] <= v[j])
{
tmp.push_back(v[i]);
i++;
}
else
{
tmp.push_back(v[j]);
j++;
}
}
while(i<mid)
{
tmp.push_back(v[i]);
i++;
}
while(j<last)
{
tmp.push_back(v[j]);
j++;
}
j=first;
for(i=0; i<tmp.size(); i++) // 注意这里从tmp将东西靠到原来v中时候，v的开始是first，不是0
{
v[j] = tmp[i];
j++;
}
}

void main()
{
srand(time(0));
vector<int> v;
for(int i=0; i<15; i++)
v.push_back(rand()%100);

cout<<"before sort, v is: "<<endl;
for(i=0; i<15; i++)
cout<<v[i]<<" ";
cout<<endl;

mergeSort(v, 0, 15);

cout<<"after sort, v is: "<<endl;
for(i=0; i<15; i++)
cout<<v[i]<<" ";

}
算法实现简化为两个步骤：1将原来的数据表分为排好序的字表，第二步使用merge()函数把字表并为有序表。一定要理解是怎么递归的，它和快速排序正好是反向的。

快速排序
和堆排序正好是相反的，堆排序是将一个数组进行二二分解成小的数组，知道最后只有两个，然后将其排序，在一次将这些小的进行合并，最后形成一个整的有序的数组。快速排序是直接先将大的分成两段，左边都比中间元素小，右边都比中间元素大，然后在将这两边进行相同的操作，直到最后。每次划分算法执行一系列的交换，以便为中心值找到合适的最终位置。和归并相比，归并需要把元素在临时向量中拷进拷出，而快速排序是就地排序，它只在表中对元素进行交换。
template<typename T>
int pivotIndex(vector<T>& v, int first, int last)
{
int mid, scanup, scandown;
T pivot, temp;
if(first ==last)
return last;
else if(first>last)
return first;
else
{
mid =(first+last)/2;
pivot = v[mid];
//交换中心值和first
v[mid]=v[first];
v[first]=pivot;
scanup = first++;
scandown=last--;

for(;;)
{
while(scanup<=scandown && v[scanup]<pivot)
scanup++;
while(pivot<v[scandown])
scandown--;
if(scanup>=scandown)
break;
temp = v[scanup];
v[scanup]=v[scandown];
v[scandowm]=temp;
scanup++;
scandowm--;
}
v[first]=v[scandown];
v[scandown]=pivot;
}
}

template <typename T>
void quickSort(vector<T>& v, int first, int last)
{
int pivotLoc;
T temp;
if(last-first <=1)
return;
else if(last-first=2)
{
if(v[last-1] <v[first])
{
temp = v[last-1];
v[last-1]=v[first];
v[frist]=temp;
}
return;
}
else
{
povotLoc = pivotIndex(v,first,last);
quickSort(v, first, pivotLoc);
quickSort(v, pivotLoc, last);
}
}
快速排序的平均时间复杂度是O(nlogn),最坏情况是O(n^2)。
各种排序算法的比较：
主要有选择排序，插入排序，堆排序，归并排序，快速排序。
选择排序，插入排序他们总是需要对邻近的元素进行比较，平均时间复杂度是O(n^2),
后三个的平均时间复杂度是O(nlogn),他们对非邻近元素进行比较，堆排序在任何情况下的复杂度都是O(nlogn),而其他两个的最坏情况是n^2,但出现的可能性很小。归并排序需要额外的内存，降低了性能。总的来说快速排序最好。
还记得第八张的基数排序吧，时间复杂度也是O(nlogn)，他不是基于比较的排序算法，但是内存消耗超级厉害。

定理：任何使用比较来达到排序目的的算法的最坏性能不可能好于O(nlogn),基于比较的算法的性能不可能为O(n)

一个应用：找出v中的第k大的值
用到快速排序中的pivotIndex函数
findK(vector<T>& v, first, last, k)
{
int index = pivotIndex(v, fist, last);
if(index ==k)
return;
if(k>index)
findK(v, index, last, k);
else
findK(v, first, index, k);
}
他的最坏情况和快速排序一样，为O(n^2),
按取中间值来计算，每次比较为n+n/2+n/4+n/8+.......=2n
所以平均复杂度是O(n)，线性复杂度

#include "stdio.h"
#include "windows.h"
#include <conio.h>
//#include <stdlib.h>
#include<math.h>
#pragma comment(lib,"winmm.lib")
//#pragma comment( linker, "/subsystem:\"windows\" /entry:\"mainCRTStartup\"" )
void quicklysort(int *,int ,int );//快速排序算法
void heapadjust(int *,int ,int );//堆调整
void heapsort(int *,int );//堆排序算法
HANDLE hout;
SYSTEMTIME st;
void setpoint(int x,int y)
{
COORD tp;
tp.X=x;
tp.Y=y;
SetConsoleCursorPosition(hout,tp);
}
void main()
{
system("color 1E");
int i,j;
COORD pt;
GetLocalTime(&st);
hout=GetStdHandle(STD_OUTPUT_HANDLE);
SetConsoleTitle("排序算法");
setpoint(0,1);
printf(" ");
printf("┏");
for(i=0;i<9;i++)
if(i==4) printf("快速排序算法(升序)");
else
printf("━");
printf("┳");

for(i=0;i<10;i++)
if(i==4) printf("堆排序算法(降序)");
else
printf("━");
printf("┓");
for(i=0;i<20;i++)
{

setpoint(3,i+2);
printf("*");

setpoint(39,i+2);
printf("*");

setpoint(75,i+2);
printf("*");

}
setpoint(3,21);
printf("┗");
for(j=0;j<35;j++)
if(j==17) printf("┻");
else printf("━");
printf("┛");
pt.X=30;
pt.Y=23;
SetConsoleCursorPosition(hout,pt);
printf("%d-%d-%d %d:%d:%d",st.wYear,st.wMonth,st.wDay,st.wHour,st.wMinute,st.wSecond);
for(i=0;i<2;i++)
{
setpoint(5,2*i+3);
if(i==0)
{
int i,a[10];
printf("随机产生十个数字:");
GetLocalTime(&st);
setpoint(5,4);
a[0]=st.wMilliseconds%99;
printf("%d ",a[0]);
for(i=1;i<10;i++)
{
a[i]=((int)(sqrt(a[i-1])*101))%99;
printf("%d ",a[i]);
}
setpoint(5,5);
printf("排序后:");
setpoint(5,6);
quicklysort(a,0,9);
for(i=0;i<10;i++)
printf("%d ",a[i]);

}
else
{
int i,a[10];
setpoint(41,3);
printf("随机产生十个数字:");
GetLocalTime(&st);
setpoint(41,4);
a[0]=(st.wMilliseconds+st.wSecond*1000)%99+10;
printf("%d ",a[0]);
for(i=1;i<10;i++)
{
a[i]=((int)(sqrt(a[i-1])*11))%90+10;
printf("%d ",a[i]);
}
setpoint(41,5);
printf("排序后:");
setpoint(41,6);
heapsort(a,9);
for(i=0;i<10;i++)
printf("%d ",a[i]);
setpoint(41,7);
printf("堆样式");

i=0;
while(i==0)
{
setpoint(48,8);
printf("%d ",a[i]);
i++;
}
setpoint(45,9);
while(i>0&&i<3)
{
printf("%d ",a[i]);
i++;
}
setpoint(43,10);
while(i>=3&&i<7)
{
printf("%d ",a[i]);
i++;
}
setpoint(41,11);
while(i>=7&&i<10)
{
printf("%d ",a[i]);
i++;
}

}
}
setpoint(25,24);
}
void quicklysort(int *a,int s,int t)
{
int i=s,j=t;
int temp;
temp=a[s];
while(j>i)
{
while(j>i&&a[j]>temp) j--;
if(j>i) a[i]=a[j];
while(j>i&&a[i]<=temp) i++;
if(j>i) a[j]=a[i];
}
a[i]=temp;
if(s<i-1) quicklysort(a,s,i-1);
if(i+1<t) quicklysort(a,i+1,t);
}
void heapadjust(int *a,int s,int t)
{
int i=s;
int j;
j=2*i;
int temp;
temp=a[s];
while(j<=t)
{
if(j<t && a[j]>a[j+1]) j++;
if(temp>a[j])
{
a[i]=a[j];
i=j;
j=2*i;
}
else
j=t+1;
}
a[i]=temp;
}
void heapsort(int *a,int n)
{
int i;
int temp;
for(i=n/2;i>=0;i--)
heapadjust(a,i,n);
for(i=n;i>0;i--)
{
temp=a[0];
a[0]=a[i];
a[i]=temp;
heapadjust(a,0,i-1);
}
}