文档章节

常见排序的指针实现【C++ Code】

shzwork
 shzwork
发布于 07/22 07:32
字数 989
阅读 6
收藏 0

本来是想加上传cmp函数的,后来也懒得写了 
然后基数排序虽然写的是模板类,但也只是支持整数了…

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <typeinfo>
using namespace std;
const int MAX_N = 500 + 10;
template <class T>
class MySort{
public :
    MySort();
    static void select_sort(T *_left, T *_right);
    static void bubble_sort(T *_left, T *_right);
    static void insert_sort(T *_left, T *_right);
    static void radix_sort(T *_left, T *_right);
    static void quick_sort(T *_left, T *_right);
    static void merge_sort(T *_left, T *_right);
    static int cmp(const T &a, const T& b){ //默认比较函数
        if (a == b) return 0;
        return a > b ? 1 : -1;
    }
private :
    static void print(char *ch, int *a, int n){ //输出中间排序结果
        printf("%s",ch);
        for (int i = 0;i < n;i++)
            printf("%d ",a[i]);
        printf("\n");
    }
};

template <class T>
void MySort<T>::select_sort(T *_left, T *_right) //选择排序
{
    for (T *_point = _left; _point != _right; ++_point){
        T *_tmp = _point;
        for (T *_next = _point + 1; _next != _right; ++_next){ //从无序部分选择出一个最小的元素
            if (cmp(*_tmp, *_next) > 0){
                _tmp = _next;
            }
        }
        swap(*_tmp, *_point); //放入有序部分的最后
        print("SelectSort: ",_left, _right - _left);
    }
}
template <class T>
void MySort<T>::bubble_sort(T *_left, T *_right) //冒泡排序
{
    for (T *_point = _left; _point != _right - 1; ++_point){
        for (T *_next = _point + 1; _next != _right; ++_next){
            if (cmp(*_point, *_next) > 0){  //比较相邻元素,若前面的大于后面的元素,交换它们的位置.
                swap(*_point, *_next);
            }
        }
        print("BubbleSort: ",_left, _right - _left);
    }
}
template <class T>
void MySort<T>::insert_sort(T *_left, T *_right) //插入排序
{
    for (T *_point = _left + 1; _point != _right; ++_point){
        T _tmp = *_point;
        for (T *_next = _point - 1; _next != _left - 1; --_next){
            if (cmp(_tmp, *_next) < 0){ //如果该元素比_tmp大,将_tmp向后挪一位
                *(_next + 1) = *_next;
            }else {                     //否则将该元素插入到_next+1位置.
                *(_next + 1) = _tmp;
                break;
            }
        }
        print("InsertSort: ",_left, _right - _left);
    }
}
template <class T>
void MySort<T>::radix_sort(T *_left, T *_right) //基数排序
{
    int n = _right - _left, *a = _left;
    int b[n];
    int m = *_left, exp = 1;
    for (int i = 1; i < n; i++){ //选择出最大的元素
        if (cmp(m,a[i]) < 0)
            m = a[i];
    }
    while (m / exp > 0){
        int bucket[10] = {0};
        for (int i = 0; i < n; i++) bucket[(a[i] / exp) % 10]++; //对每个数的某位进行桶排
        for (int i = 1; i < 10; i++) bucket[i] += bucket[i - 1];
        for (int i = n - 1; i >= 0; i--)
            b[--bucket[(a[i] / exp) % 10]] = a[i];
        for (int i=0;i<n;i++) a[i] = b[i]; //从桶中取出元素
        print("RadixSort: ",a, n);
        exp *= 10;
    }
}
template <class T>
void MySort<T>::quick_sort(T *_left, T *_right) //快速排序
{

    if (_left >= _right) return;
    T *_first = _left, *_last = _right, *_tmp = _left + ((_right - _left)>> 1); //确定基准元素
    while (_first < _last){ //让基准元素左边的元素逗比它小,右边的元素都比它大
        while ((cmp(*_first, *_tmp) < 0) && (_first < _last)) _first++;
        while ((cmp(*_last, *_tmp) > 0) && (_first < _last)) _last--;
        if (_first <= _last) {
            swap(*_first, *_last);
            _first++;
            _last--;
        }
    }
    quick_sort(_left, _last); //递归调用
    quick_sort(_first, _right);
    print("QuickSort: ",_left,_right - _left + 1);
}
template <class T>
void MySort<T>::merge_sort(T *_left, T *_right) //归并排序
{
    if (_left >= _right) return;

    T *_mid = _left + ((_right - _left) >> 1);
    merge_sort(_left, _mid); //递归调用排序
    merge_sort(_mid + 1, _right);
    T *_low = _left , *_high = _mid + 1; //已经得到两个有序的部分

    T tmp[_right - _left + 1] = {0};
    int  cnt = 0;
    while (_low <= _mid && _high <= _right){ //进行合并,先存到tmp数组
        if (cmp(*_low, *_high) < 0){
            tmp[cnt] = *_low;
            _low++;
        }else {
            tmp[cnt] = *_high;
            _high++;
        }
        cnt++;
    }
    for (int i = 0; i <= _mid - _low; i++)
        tmp[cnt++] = *(_low + i);
    for (int i = 0; i <= _right - _high; i++)
        tmp[cnt++] = *(_high + i);
    for (int i = 0; i < cnt; i++) *(_left + i) = tmp[i]; //放回原位置
    print("MergeSort: ",_left,_right - _left + 1);
}

int a[MAX_N], b[MAX_N];
int main()
{
    int n;
    scanf("%d",&n);
    for (int i=0;i<n;i++) {
        scanf("%d", a + i);
        b[i] = a[i];
    }
    MySort<int>::select_sort(b, b + n);
    puts("");
    for (int i=0;i<n;i++) b[i] = a[i];
    MySort<int>::radix_sort(b, b + n);
    puts("");
    for (int i=0;i<n;i++) b[i] = a[i];
    MySort<int>::insert_sort(b, b + n);
    puts("");
    for (int i=0;i<n;i++) b[i] = a[i];
    MySort<int>::bubble_sort(b, b + n);
    puts("");
    for (int i=0;i<n;i++) b[i] = a[i];
    MySort<int>::quick_sort(b, b + n - 1);
    puts("");
    for (int i=0;i<n;i++) b[i] = a[i];
    MySort<int>::merge_sort(b, b + n - 1);
}
--------------------- 
作者:ProboxDu 
来源:CSDN 
原文:https://blog.csdn.net/d_vip/article/details/78587598 
版权声明:本文为博主原创文章,转载请附上博文链接!

本文转载自:https://blog.csdn.net/d_vip/article/details/78587598

shzwork
粉丝 11
博文 649
码字总数 10251
作品 0
厦门
私信 提问
C++ 的排序,速度是 C 语言的 3 倍

如果你还不熟悉 C++,你应该会惊奇 C++ 在某些时候速度比 C 更快些。特别是当代码比较简短时,因为 C++ 的强项 —— 内联(inlineing) 和模板化。 下面的代码对 C 和 C++ 的排序功能进行比较:...

彭博
2012/11/27
864
4
C++ 的排序,速度是 C 语言的 3 倍

如果你还不熟悉 C++,你应该会惊奇 C++ 在某些时候速度比 C 更快些。特别是当代码比较简短时,因为 C++ 的强项 —— 内联(inlineing) 和模板化。 下面的代码对 C 和 C++ 的排序功能进行比较:...

红薯
2012/03/17
2.9K
9
C++ STL学习——vector

学过C++的人肯定会很熟悉STL标准模板库,STL其实就是封装了一系列的接口,供我们调用。很多函数或者算法的实现不需要我们从头开始写,大大提高我们的编程效率。这篇博客在简单介绍STL的情况下...

chenyufeng1991
2016/08/21
0
0
最好的朋友:C++11 移动语义和 Pimpl 手法

当编译器可以用廉价的挪动操作替换昂贵的复制操作时,也就是当它可以用一个指向一个大对象的指针的浅层复制来替换对这个大对象的深层复制的时候,挪动语义要比复制语义更快速。因此,在类中利...

乌合之众
2016/06/08
3.3K
5
QT容器中的通用算法

今天开始的部分是关于Qt提供的一些通用算法。这部分内容来自C++ GUI Programming with Qt 4, 2nd Edition。 提供了一系列通用的模板函数,用于实现容器上面的基本算法。这部分算法很多依赖于...

晨曦之光
2012/04/13
373
0

没有更多内容

加载失败,请刷新页面

加载更多

Giraph源码分析(八)—— 统计每个SuperStep中参与计算的顶点数目

作者|白松 目的:科研中,需要分析在每次迭代过程中参与计算的顶点数目,来进一步优化系统。比如,在SSSP的compute()方法最后一行,都会把当前顶点voteToHalt,即变为InActive状态。所以每次...

数澜科技
51分钟前
2
0
Xss过滤器(Java)

问题 最近旧的系统,遇到Xss安全问题。这个系统采用用的是spring mvc的maven工程。 解决 maven依赖配置 <properties><easapi.version>2.2.0.0</easapi.version></properties><dependenci......

亚林瓜子
今天
7
0
Navicat 快捷键

操作 结果 ctrl+q 打开查询窗口 ctrl+/ 注释sql语句 ctrl+shift +/ 解除注释 ctrl+r 运行查询窗口的sql语句 ctrl+shift+r 只运行选中的sql语句 F6 打开一个mysql命令行窗口 ctrl+l 删除一行 ...

低至一折起
今天
7
0
Set 和 Map

Set 1:基本概念 类数组对象, 内部元素唯一 let set = new Set([1, 2, 3, 2, 1]); console.log(set); // Set(3){ 1, 2, 3 } [...set]; // [1, 2, 3] 接收数组或迭代器对象 ...

凌兮洛
今天
1
0
PyTorch入门笔记一

张量 引入pytorch,生成一个随机的5x3张量 >>> from __future__ import print_function>>> import torch>>> x = torch.rand(5, 3)>>> print(x)tensor([[0.5555, 0.7301, 0.5655],......

仪山湖
今天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部