堆排序快速排序插入排序-创新互联

数据结构使用的是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 struct
        max_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#include

using namespace std;
vectors6;

void printvec(vectora){
    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 struct
        max_heapify(i, len - 1);
    for(int i = len - 1; i >0; i--) { //move the largest to end and recreate heap struct
        swap(s6[0], s6[i]);
        max_heapify(0, i - 1);
    }
    printvec(s6);
    return 0;
}

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

#includeusing 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不是if
        if(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 heap
    for(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#include

using namespace std;
vectorv6;

void printvec(vectora){
    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)

#includeusing 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#include

using namespace std;

void printvec(vectora){
    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;
}