排序算法C++实现

#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<fstream>
#include<sstream>
#include<vector>

using namespace std;

inline void swap(int* arr, int i, int j){
    int t = *(arr + i);
    *(arr + i) = *(arr + j);
    *(arr + j) = t;
}

inline int get_bit(int d){
    stringstream ss;
    ss << d;
    string s;
    ss >> s;
    return s.size();
}

void merge_sort(int* arr, int left, int right);
void shell_sort(int* arr, int len);
void bucket_sort(int* arr, int len);
void radix_sort(int* arr, int len);
void direct_insert_sort(int* arr, int len);
void binary_insert_sort(int* arr, int len);
void quick_sort(int* arr, int left, int right);
void heap_sort(int* arr, int len);

void heaplify(int* arr, int current_node, int len);
void max_heaplify(int* arr, int len);
int partition(int* arr, int left, int right);

/**
 * 归并排序
 * [最坏情况]: nlogn
 * [最好情况]: nlogn
 * [平均情况]: nlogn
 * [稳定性]: 稳定
 */
void merge_sort(int* arr, int left, int right){
    if(left >= right)   return;
    int mid = left + (right - left) / 2;
    merge_sort(arr, left, mid);
    merge_sort(arr, mid + 1, right);

    int* aux = (int *) malloc(sizeof(int) * (right - left + 1));
    int index = 0, i = left, j = mid + 1;
    while(i <= mid && j <= right){
        if(*(arr + i) < *(arr + j))
            *(aux + index++) = *(arr + i++);
        else
            *(aux + index++) = *(arr + j++);
    }
    while(i <= mid)     *(aux + index++) = *(arr + i++);
    while(j <= right)   *(aux + index++) = *(arr + j++);
    for(int k = 0; k < index; k++)
        *(arr + left + k) = *(aux + k);
    free(aux);
}

/**
 * 希尔排序
 * [最坏情况]: n^2
 * [最好情况]: n
 * [平均情况]: 取决于gap的长短
 * [稳定性]: 不稳定
 */
void shell_sort(int* arr, int len){
    if(len <= 1)  return;
    int gap = 1;
    while(gap < len / 3) gap = gap * 3 + 1;
    while(gap >= 1){
        for(int i = gap; i < len; i++)
            for(int j = i; j >= gap && *(arr + j) < *(arr + j - gap); j -= gap)
                swap(arr, j, j - gap);
        gap /= 3;
    }
}

/**
 * 桶排序
 * [最坏情况]: n^2
 * [最好情况]: n + k: k为(max-min)范围
 * [平均情况]: n + k: k为(max-min)范围
 * [稳定性]: 不稳定
 */
void bucket_sort(int* arr, int len){
    int max = 0xffffffff, index = 0;
    for(int i = 0; i < len; i++)  max = *(arr + i) > max ? *(arr + i) : max;
    vector<int> buckets[max + 1];
    for(int i = 0; i < len; i++)  buckets[*(arr + i)].push_back(*(arr + i));
    for(int i = 0; i <= max; i++)
        for(int j = 0; j < buckets[i].size(); j++)
            *(arr + index++) = buckets[i][j];
}

/**
 * 基数排序
 * [最坏情况]: n*log(radix)(m)
 * [最好情况]: n*log(radix)(m)
 * [平均情况]: n*log(radix)(m)
 * [稳定性]: 稳定
 */
void radix_sort(int* arr, int len){
    if(len <= 1)  return;
    int max_bit = 0, radix = 1;
    for(int i = 0; i < len; i++)
        max_bit = max(max_bit, get_bit(*(arr + i)));
    int* tmp = (int*) malloc(sizeof(int) * len);
    int count[10];
    //每次按照位的次序来排序，因此需要进行max_bit次外层循环
    for(int i = 0; i < max_bit; i++){
        //将count清零
        for(int j = 0; j < 10; j++)
            count[j] = 0;
        for(int j = 0; j < len; j++)
            count[*(arr + j) / radix % 10]++;
        for(int j = 1; j < 10; j++)
            count[j] = count[j] + count[j - 1];
        for(int j = len - 1; j >= 0; j--){
            int k = *(arr + j) / radix % 10;
            *(tmp + count[k] - 1) = *(arr + j);
            count[k]--;
        }
        for(int i = 0; i < len; i++)
            *(arr + i) = *(tmp + i);
        radix *= 10;
    }
    free(tmp);
}

/**
 * 直接插入排序
 * [最坏情况]: n^2
 * [最好情况]: n
 * [平均情况]: n^2
 * [稳定性]: 不稳定
 */
void direct_insert_sort(int* arr, int len){
    if(len <= 1)  return;
    //不带哨兵版本的，如果带哨兵就要从index=1开始记录数据
    for(int i = 1; i < len; i++){
        int t;
        if(*(arr + i) < *(arr + i - 1)){
            t = *(arr + i);
            int j;
            //下面是根据每一位与前面进行比较，可以通过折半查找来提高算法性能
            for(j = i - 1; j >= 0 && *(arr + j) > t; *(arr + j-- + 1) = *(arr + j));
            *(arr + j + 1) = t;
        }
    }
}

/**
 * 折半插入排序
 * [最坏情况]: n^2
 * [最好情况]: n
 * [平均情况]: n^2
 * [稳定性]: 不稳定
 */
void binary_insert_sort(int* arr, int len){
    if(len <= 1)  return;
    for(int i = 2; i < len; i++){
        if(*(arr + i) < *(arr + i - 1)){
            int t = *(arr + i);
            int left = 0, right = i - 1;
            while(left <= right){
                int mid = left + (right - left) / 2;
                if(*(arr + i) < *(arr + mid))
                    right = mid - 1;
                else
                    left = mid + 1;
            }
            //left=right即为插入点
            for(int j = i - 1; j >= left; *(arr + j-- + 1) = *(arr + j));
            *(arr + left) = t;
        }
    }
}

/**
 * 快速排序
 * [最坏情况]: n^2
 * [最好情况]: nlogn
 * [平均情况]: nlogn
 * [稳定性]: 不稳定
 */
void quick_sort(int* arr, int left, int right){
    if(left >= right)   return;
    int p = partition(arr, left, right);
    quick_sort(arr, left, p - 1);
    quick_sort(arr, p + 1, right);
}

//切分算法
int partition(int* arr, int left, int right){
    int i = left, j = right + 1, v = *(arr + left);
    while(1){
        while(*(arr + ++i) < v)
            if(i == right)
                break;
        while(*(arr + --j) > v)
            if(j == left)
                break;
        if(i >= j)  break;
        swap(arr, i , j);
    }
    swap(arr, left, j);
    return j;
}

/**
 * 堆排序
 * [最坏情况]: nlogn
 * [最好情况]: nlogn
 * [平均情况]: nlogn
 * [稳定性]: 不稳定
 */
void heap_sort(int* arr, int len){
    for(int i = 0; i < len; i++){
        max_heaplify(arr, len - i);
        swap(arr, 0, len - i - 1);
    }
}

void max_heaplify(int* arr, int len){
    for(int i = len - 1; i >= 0; i--)
        heaplify(arr, i, len);
}

void heaplify(int* arr, int current_node, int len){
    if(current_node >= len)   return;
    int max = current_node;
    int left = 2 * current_node + 1, right = 2 * current_node + 2;
    if(left < len){
        max = *(arr + left) > *(arr + max) ? left : max;
    }
    if(right < len){
        max = *(arr + right) > *(arr + max) ? right : max;
    }
    if(max != current_node){
        swap(arr, max, current_node);
        heaplify(arr, max, len);
    }
}

int main(){
    vector<int> v;
    ifstream data("./data.txt");
    string line;
    while(getline(data, line)){
        stringstream ss;
        ss << line;
        if(!ss.eof()){
            int t;
            while(ss >> t)
                v.push_back(t);
        }
    }
    int* arr = (int*) malloc(sizeof(int) * v.size());
    for(int i = 0; i < v.size(); *(arr + i++) = v[i]);
    //two_way_insert_sort(arr, v.size());
    heap_sort(arr, v.size());
    for(int i = 0; i < v.size(); i++){
        if(i != 0 && i % 10 == 0)   cout << endl;
        printf("%7d ", *(arr + i));
    }
    return 0;
}

排序算法C++实现

原文：https://www.cnblogs.com/dotdashdotdash/p/11863595.html