堆排序快速排序插入排序-創(chuàng)新互聯(lián)

數(shù)據(jù)結(jié)構(gòu)使用的是1 dimension的數(shù)組來作為二叉樹的堆結(jié)構(gòu)，所以并沒有使用結(jié)構(gòu)體，而是直接使用了數(shù)組

而且堆是完全二叉樹，也就是除了最后一層以外，其他層都是滿二叉樹，最后一層可能不滿，所以1dimension數(shù)組產(chǎn)生二叉樹就很方便，第一個數(shù)字就是根節(jié)點(diǎn)，然后是左右子節(jié)點(diǎn)，層序遍歷即可

性質(zhì)：完全二叉樹的孩子節(jié)點(diǎn)是父節(jié)點(diǎn)的2xn或者2x?n+1

第一步：產(chǎn)生堆，要滿足性質(zhì)，每個父節(jié)點(diǎn)的值比孩子節(jié)點(diǎn)都要大（?。?，遞推的話根節(jié)點(diǎn)就是大（小）值

這里要注意，孩子節(jié)點(diǎn)是父節(jié)點(diǎn)的2xn或者2x?n+1，所以從len/2-1的位置開始調(diào)整即可也即是最后一個父節(jié)點(diǎn)

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

第二步：分區(qū)，兩個區(qū)，堆區(qū)和已經(jīng)排好序的區(qū)，堆區(qū)是無序的，每次將堆的根節(jié)點(diǎn)也就是大值移到末尾，然后再次產(chǎn)生堆，由于堆已經(jīng)是大小一致，只要將根節(jié)點(diǎn)移到合適的位置即可

輸入：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]) //子節(jié)點(diǎn)的大值
            son++;
        if(arr[dad] >arr[son]) return;   //父節(jié)點(diǎn)是大值返回
        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拿到最后一個父節(jié)點(diǎn)的序號，從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;
}

選定（樞軸）支點(diǎn)pivot，然后配置左右的定位符i，j

支點(diǎn)可以任意選取，支點(diǎn)所在值記為A，左右定位符一般是0， len - 1

1. 從右向左掃描，若是值小于A，則將該值放到支點(diǎn)，然后此處產(chǎn)生空洞L
2. 從左向右掃描，若是值大于A，則將該值放到空洞L所在位置，此處產(chǎn)生空洞，用A來填補(bǔ)即可
3. 分片，以支點(diǎn)所在位置分片，左右分別進(jìn)行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;//填補(bǔ)最后的空洞
        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;
}