各排序算法

堆排序以后补

//
//  main.cpp
//  sort
//
//  Created by MaKai on 2017/3/22.
//  Copyright © 2017年 MaKai. All rights reserved.
//

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void maopao(vector<int> &a);
void charu(vector<int> &a);
void xier(vector<int> &a);
void shellsort(vector<int> &a, int dk);
void jiandanxuanze(vector<int> &a);
void guibing(vector<int> &a, int l, int r);
void merge(vector<int> &a, int l, int m, int r);
void kuaipai(vector<int> &a, int l, int r);
int kp(vector<int> &a, int l, int r);

int main(int argc, const char * argv[]) {
    
    vector<int> a = {3,1,34,6,7,8,2,0,9,5,7,10,11,16,32,18};
//    maopao(a);
//    charu(a);
//    jiandanxuanze(a);
//    guibing(a, 0, int(a.size() - 1));
//    kuaipai(a, 0, int(a.size()) - 1);
    xier(a);
    
    for (auto x : a) {
        cout<<x << " ";
    }
    
    return 0;
}

// 冒泡排序
// stable, in-place sort
// 平均时间 O(n^2)
void maopao(vector<int> &a){
    
    for (int i = int(a.size() - 1); i >= 0; --i) {
        for (int j = 0; j < i; ++j) {
            if (a[j] > a[j+1]) {
                swap(a[j], a[j+1]);
            }
        }
    }
}


// 插入排序
// stable, in-place sort
// 时间O(n^2)
void charu(vector<int> &a) {
    
    if (a.size() <= 1) return;
    for (int i = 1; i < a.size(); ++i) {
        int n = a[i];
        int j = i - 1;
        while (j >= 0 && n < a[j]) {
            a[j+1] = a[j];
            j--;
        }
        a[++j] = n;
    }
}

// 希尔排序，又叫缩小增量排序
// unstable, in-place sort
// 时间O（n^1.3）
void xier(vector<int> &a) {
    
    int dk = int(a.size()) / 2;
    while (dk >= 1) {
        shellsort(a, dk);
        dk /= 2;
    }
}

void shellsort(vector<int> &a, int dk) {
    
    for (int i = dk; i < a.size(); i++) {
        if (a[i] < a[i - dk]) {
            int j = i - dk;
            int n = a[i];
            while (a[j] > n) {
                a[j + dk] = a[j];
                j -= dk;
            }
            a[j+dk] = n;
        }
    }
}


// 简单选择排序
// unstable, in-place sort
// 时间O(n^2)
void jiandanxuanze(vector<int> &a) {
    
    for (int i = 0; i < a.size() - 1; ++i) {
        int min_n = a[i];
        int min_i = i;
        for (int j = i + 1; j < a.size(); ++j) {
            if (a[j] < min_n) {
                min_i = j;
                min_n = a[j];
            }
        }
        a[min_i] = a[i];
        a[i] = min_n;
    }
}

// 归并排序
// stable, out-place sort
// 时间O(nlogn)
// 缺点：out-place sort，相比快排需要更多的额外空间
void guibing(vector<int> &a, int l, int r) {
    if (l < r) {
        int m = (l + r) / 2;
        guibing(a, l, m);
        guibing(a, m + 1, r);
        merge(a, l, m, r);
    }
}

void merge(vector<int> &a, int l, int m, int r) {

    vector<int> temp;
    int i, j;
    for (i = l, j = m + 1; i <= m && j <= r;) {
        if (a[i] <= a[j]) temp.push_back(a[i++]);
        else temp.push_back(a[j++]);
    }
    while (i <= m) temp.push_back(a[i++]);
    while (j <= r) temp.push_back(a[j++]);
    i = l;
    for (auto n : temp) a[i++] = n;
}


// 快速排序
// unstable, in-place sort
// 时间 O(nlogn)，当数组已排序时，时间O(n^2)
void kuaipai(vector<int> &a, int l, int r) {
    
    if (l < r) {
        int m = kp(a, l, r);
        kuaipai(a, l, m);
        kuaipai(a, m+1, r);
    }
}


int kp(vector<int> &a, int l, int r) {
    
    int v = a[l];
    while (l < r) {
        while (l < r && a[r] >= v) r--;
        a[l] = a[r];
        while (l < r && a[l] <= v) l++;
        a[r] = a[l];
    }
    a[l] = v;
    return l;
}