堆排序

数据结构使用的是1 dimension的数组来作为二叉树的堆结构，所以并没有使用结构体，而是直接使用了数组

而且堆是完全二叉树，也就是除了最后一层以外，其他层都是满二叉树，最后一层可能不满，所以1dimension数组产生二叉树就很方便，第一个数字就是根节点，然后是左右子节点，层序遍历即可

性质：完全二叉树的孩子节点是父节点的2xn或者2x n+1

第一步：产生堆，要满足性质，每个父节点的值比孩子节点都要大（小），递推的话根节点就是最大（小）值

这里要注意，孩子节点是父节点的2xn或者2x n+1，所以从len/2-1的位置开始调整即可也即是最后一个父节点

    for(int i = len/2 - 1; i >= 0; i--)   //create heap structmax_heapify(i, len - 1);

第二步：分区，两个区，堆区和已经排好序的区，堆区是无序的，每次将堆的根节点也就是最大值移到末尾，然后再次产生堆，由于堆已经是大小一致，只要将根节点移到合适的位置即可

输入：8 9 10 1 3 6 5 4 2 7 0

图来自 https://www.runoob.com/w3cnote/heap-sort.html

1.7 堆排序 | 菜鸟教程 (runoob.com)​www.runoob.com/w3cnote/heap-sort.html

#include
#include
#includeusing namespace std;
vector s6;void printvec(vector a){for(int i=0; i s6[son]) {return;}else {swap(s6[son], s6[dad]);dad = son;son = dad * 2 + 1;}}return;
}int main(void){int n, num;cin>>n;for(int i=0; i>num;s6.push_back(num);}int len = s6.size();for(int i = len/2 - 1; i >= 0; i--)   //create heap structmax_heapify(i, len - 1);for(int i = len - 1; i > 0; i--) { //move the largest to end and recreate heap structswap(s6[0], s6[i]);max_heapify(0, i - 1);}printvec(s6);return 0;
}

1.7 堆排序 | 菜鸟教程 (runoob.com) 

#include
using namespace std;
int arr[] = {2, 9, 6, 1, 5, 8, 7, 11, 100, 30, 31, 38, 60, 50, 30};
void printvec(int len) {printf("%d", arr[0]);for(int i = 1; i < len; i++) printf(" %d", arr[i]);
}
void maxheapify(int start, int end) {int dad = start;int son = dad * 2 + 1;while(son < end) {           //是while不是ifif(son+1 < end && arr[son+1] > arr[son]) //子节点的最大值son++;if(arr[dad] > arr[son]) return;   //父节点是最大值返回if(arr[dad] < arr[son]) {swap(arr[dad], arr[son]);dad = son;son = dad * 2 + 1;}}
}
void heapsort(int len) {for(int i = len/2 - 1; i >= 0; i--) //len/2-1拿到最后一个父节点的序号，从0开始maxheapify(i, len);   //从下到上, generate heapfor(int i = len - 1; i > 0; i--) {   swap(arr[0], arr[i]);maxheapify(0, i-1); //从上到下}
}
int main(int argc, char **argv) {int len = sizeof(arr)/sizeof(*arr);if(len==1) {printvec(len);return EXIT_SUCCESS;}heapsort(len);printvec(len);return EXIT_SUCCESS;
}

快速排序

选定（枢轴）支点pivot，然后配置左右的定位符i，j

支点可以任意选取，支点所在值记为A，左右定位符一般是0， len - 1

1. 从右向左扫描，若是值小于A，则将该值放到支点，然后此处产生空洞L
2. 从左向右扫描，若是值大于A，则将该值放到空洞L所在位置，此处产生空洞，用A来填补即可
3. 分片，以支点所在位置分片，左右分别进行1、2，不断递归直到只剩一个值

#include
#include
#includeusing namespace std;
vector v6;void printvec(vector a){for(int i=0; i= A)j--;if(i < j) {v6[start] = v6[j];i++;}while(i < j && v6[i] < A)i++;if(i < j) {v6[j] = v6[i];v6[i] = A;j--;}}v6[i] = A;//填补最后的空洞quick_sort(start, i - 1);quick_sort(i + 1, end);}return;
}int main(void){int n, num;cin>>n;for(int i=0; i>num;v6.push_back(num);}int len = v6.size();quick_sort(0, len - 1);printvec(v6);return 0;
}

 快速排序 | 菜鸟教程 (runoob.com)

#include
using namespace std;
int arr[] = {2, 9, 6, 1, 5, 8, 7, 11, 100, 30, 31, 38, 60, 50, 30};
void printvec(int len) {printf("%d", arr[0]);for(int i = 1; i < len; i++) printf(" %d", arr[i]);
}
void quicksort(int l, int r) {if(l>=r) return;int h = arr[l];int start = l;int end = r;while(l < r) {while(l < r && arr[r] >= h)r--;if(l

#include
#include
#includeusing namespace std;void printvec(vector a){for(int i=0; i s0;int n, num;cin>>n;for(int i=0; i>num;s0.push_back(num);}for(int i=0; i=s0[i+1]){s0.insert(s0.begin()+j, s0[i+1]);s0.erase(s0.begin()+i+2);}}}}printvec(s0);return 0;
}