排序 / iVAN

排序

Data.h

template<typename Type> class Element{
public:
    Type GetKey(){
        return key;
    }

    void SetKey(Type item){
        key = item;
    }

public:
    Element<Type>& operator =(Element<Type> copy){
        key = copy.key;
        return *this;
    }

    bool operator ==(Element<Type> item){
        return this->key == item.key;
    }

    bool operator !=(Element<Type> item){
        return this->key != item.key;
    }

    bool operator <(Element<Type> item){
        return this->key < item.key;
    }

    bool operator >(Element<Type> item){
        return this->key > item.key;
    }

    bool operator >=(Element<Type> item){
        return this->key >= item.key;
    }

    bool operator <=(Element<Type> item){
        return this->key <= item.key;
    }

private:
    Type key;
};

template<typename Type> class Sort;
template<typename Type> class DataList{
public:
    friend class Sort<Type>;
    DataList(int size=m_nDefaultSize): m_nMaxSize(size), m_ncurrentsize(0){
        m_pvector = new Element<Type>[size];
    }

    DataList(Type *data, int size);

    bool Insert(Type item);
    ~DataList(){
        delete[] m_pvector;
    }

    int Size(){
        return this->m_ncurrentsize;
    }
    void Swap(Element<Type> &left, Element<Type> &right){
        Element<Type> temp = left;
        left = right;
        right = temp;
    }

    void Print();
private:
    static const int m_nDefaultSize = 10;
    Element<Type> *m_pvector;
    const int m_nMaxSize;
    int m_ncurrentsize;
};

template<typename Type> DataList<Type>::DataList(Type *data, int size)
        : m_nMaxSize(size > m_nDefaultSize ? size : m_nDefaultSize), m_ncurrentsize(0){
    this->m_pvector = new Element<Type>[size];
    for (int i=0; i<size; i++){
        this->m_pvector[i].SetKey(data[i]);
    }
    this->m_ncurrentsize += size;

}

template<typename Type> bool DataList<Type>::Insert(Type item){
    if (this->m_ncurrentsize == this->m_nMaxSize){
        cerr << "The list is full!" <<endl;
        return 0;
    }
    this->m_pvector[this->m_ncurrentsize++].SetKey(item);
}

template<typename Type> void DataList<Type>::Print(){
    cout << "The list is:";
    for (int i=0; i<this->m_ncurrentsize; i++){
        cout << " " << this->m_pvector[i].GetKey();
    }
}

QueueNode.h

template<typename Type> class LinkQueue;

template<typename Type> class QueueNode{

private:

friend class LinkQueue<Type>;

QueueNode(const Type item,QueueNode<Type> *next=NULL)

:m_data(item),m_pnext(next){}

private:

Type m_data;

QueueNode<Type> *m_pnext;

};

LinkQueue.h

#include "QueueNode.h"

template<typename Type> class LinkQueue{
public:
	LinkQueue():m_prear(NULL),m_pfront(NULL){}
	~LinkQueue(){
		MakeEmpty();
	}
	void Append(const Type item);
	Type Delete();
	Type GetFront();
	void MakeEmpty();
	bool IsEmpty() const{
		return m_pfront==NULL;
	}
	void Print();

private:
	QueueNode<Type> *m_prear,*m_pfront;
};

template<typename Type> void LinkQueue<Type>::MakeEmpty(){
	QueueNode<Type> *pdel;
	while(m_pfront){
		pdel=m_pfront;
		m_pfront=m_pfront->m_pnext;
		delete pdel;
	}
}

template<typename Type> void LinkQueue<Type>::Append(const Type item){
	if(m_pfront==NULL){
		m_pfront=m_prear=new QueueNode<Type>(item);
	}
	else{
		m_prear=m_prear->m_pnext=new QueueNode<Type>(item);
	}
}

template<typename Type> Type LinkQueue<Type>::Delete(){
	if(IsEmpty()){
		cout<<"There is no element!"<<endl;
		exit(1);
	}
	QueueNode<Type> *pdel=m_pfront;
	Type temp=m_pfront->m_data;
	m_pfront=m_pfront->m_pnext;
	delete pdel;
	return temp;
}

template<typename Type> Type LinkQueue<Type>::GetFront(){
	if(IsEmpty()){
		cout<<"There is no element!"<<endl;
		exit(1);
	}
	return m_pfront->m_data;
}

template<typename Type> void LinkQueue<Type>::Print(){
	QueueNode<Type> *pmove=m_pfront;
	cout<<"front";
	while(pmove){
		cout<<"--->"<<pmove->m_data;
		pmove=pmove->m_pnext;
	}
	cout<<"--->rear"<<endl<<endl<<endl;
}

Sort.h

#include "Data.h"
#include "LinkQueue.h"

template<typename Type> class Sort{
public:
    void InsertSort(DataList<Type> &list, int n=-1);
    void BinaryInsertSort(DataList<Type> &list, int n=-1);
    void ShellSort(DataList<Type> &list, const int gap=-1);
    void BubbleSort(DataList<Type> &list);
    void QuickSort(DataList<Type> &list, int left=0, int right=-3);
    void SelectSort(DataList<Type> &list);
    void HeapSort(DataList<Type> &list);
    void MergeSort(DataList<Type> &list);
    void RadixSort(DataList<int> &list, int m, int d);      //just use for integer!

private:
    void BubbleSwap(DataList<Type> &list, const int n, int &flag);
    void SelectChange(DataList<Type> &list, const int n);
    void HeapAdjust(DataList<Type> &list, const int start, const int end);
    void Merge(DataList<Type> &list, DataList<Type> &mergedlist, const int len);
    void MergeDouble(DataList<Type> &list, DataList<Type> &mergedlist, const int start, const int part, const int end);
};

template<typename Type> void Sort<Type>::InsertSort(DataList<Type> &list, int n){
    if (-1 == n){
        for (int i=1; i<list.m_ncurrentsize; i++){
            InsertSort(list, i);
        }
        return;
    }
    Element<Type> temp = list.m_pvector[n];
    int i;
    for (i=n; i>0; i--){
        if (temp > list.m_pvector[i-1]){

            break;
        }
        else{
            list.m_pvector[i] = list.m_pvector[i-1];
        }
    }
    list.m_pvector[i] = temp;
}

template<typename Type> void Sort<Type>::BinaryInsertSort(DataList<Type> &list, int n){
    if (-1 == n){
        for (int i=1; i<list.m_ncurrentsize; i++){
            BinaryInsertSort(list, i);
        }
        return;
    }
    Element<Type> temp = list.m_pvector[n];
    int left = 0, right = n-1;
    while(left <= right){
        int middle = (left + right) / 2;
        if (temp < list.m_pvector[middle]){
            right = middle - 1;
        }
        else {
            left = middle + 1;
        }
    }
    for (int i=n-1; i>=left; i--){
        list.m_pvector[i+1] = list.m_pvector[i];
    }
    list.m_pvector[left] = temp;
}

template<typename Type> void Sort<Type>::ShellSort(DataList<Type> &list, const int gap){
    if (-1 == gap){
        int gap = list.m_ncurrentsize / 2;
        while (gap){
            ShellSort(list, gap);
            gap = (int)(gap / 2);
        }
        return;
    }
    for (int i=gap; i<list.m_ncurrentsize; i++){
        InsertSort(list, i);
    }
}

template<typename Type> void Sort<Type>::BubbleSwap(DataList<Type> &list, const int n, int &flag){
    flag = 0;
    for (int i=list.m_ncurrentsize-1; i>=n; i--){
        if (list.m_pvector[i-1] > list.m_pvector[i]){
            list.Swap(list.m_pvector[i-1], list.m_pvector[i]);
            flag = 1;
        }
    }
}

template<typename Type> void Sort<Type>::BubbleSort(DataList<Type> &list){
    int flag = 1, n = 0;
    while (++n<list.m_ncurrentsize && flag){
        BubbleSwap(list, n, flag);
    }
}

template<typename Type> void Sort<Type>::QuickSort(DataList<Type> &list, int left=0, int right=-1){
    if (-3 == right){
        right = list.m_ncurrentsize - 1;
    }
    if (left < right){
        int pivotpos = left;
        Element<Type> pivot = list.m_pvector[left];
        for (int i=left+1; i<=right; i++){
            if (list.m_pvector[i]<pivot && ++pivotpos!=i){
                list.Swap(list.m_pvector[pivotpos], list.m_pvector[i]);
            }
            list.Swap(list.m_pvector[left], list.m_pvector[pivotpos]);
        }
        QuickSort(list, left, pivotpos-1);
        QuickSort(list, pivotpos+1, right);
    }

}

template<typename Type> void Sort<Type>::SelectChange(DataList<Type> &list, const int n){
    int j = n;
    for (int i=n+1; i<list.m_ncurrentsize; i++){
        if (list.m_pvector[i] < list.m_pvector[j]){
            j = i;
        }
    }
    if (j != n){
        list.Swap(list.m_pvector[n], list.m_pvector[j]);
    }
}

template<typename Type> void Sort<Type>::SelectSort(DataList<Type> &list){
    for (int i=0; i<list.m_ncurrentsize-1; i++){
        SelectChange(list, i);
    }
}

template<typename Type> void Sort<Type>::HeapAdjust(DataList<Type> &list, const int start, const int end){
    int current = start, child = 2 * current + 1;
    Element<Type> temp = list.m_pvector[start];
    while (child <= end){
        if (child<end && list.m_pvector[child]<list.m_pvector[child+1]){
            child++;
        }
        if (temp >= list.m_pvector[child]){
            break;
        }
        else {
            list.m_pvector[current] = list.m_pvector[child];
            current = child;
            child = 2 * current + 1;
        }
    }
    list.m_pvector[current] = temp;
}

template<typename Type> void Sort<Type>::HeapSort(DataList<Type> &list){
    for (int i=(list.m_ncurrentsize-2)/2; i>=0; i--){
        HeapAdjust(list, i, list.m_ncurrentsize-1);
    }

    for (int i=list.m_ncurrentsize-1; i>=1; i--){
        list.Swap(list.m_pvector[0], list.m_pvector[i]);
        HeapAdjust(list, 0, i-1);
    }
}

template<typename Type> void Sort<Type>::MergeDouble(DataList<Type> &list, DataList<Type> &mergedlist, const int start, const int part, const int end){
    int i = start, j = part + 1, k = start;
    while (i<=part && j<=end){
        if (list.m_pvector[i] <= list.m_pvector[j]){
            mergedlist.m_pvector[k++] = list.m_pvector[i++];
        }
        else {
            mergedlist.m_pvector[k++] = list.m_pvector[j++];
        }
    }
    if (i <= part){
        for (int m=i; m<=part && k<=end;){
            mergedlist.m_pvector[k++] = list.m_pvector[m++];
        }
    }
    else {
        for (int m=j; m<=end && k<=end; m++){
            mergedlist.m_pvector[k++] = list.m_pvector[m];
        }
    }
}
template<typename Type> void Sort<Type>::Merge(DataList<Type> &list, DataList<Type> &mergedlist, const int len){
    int n = 0;
    while (n+2*len < list.m_ncurrentsize){
        MergeDouble(list, mergedlist, n, n+len-1, n+2*len-1);
        n += 2*len;
    }
    if (n+len < list.m_ncurrentsize){
        MergeDouble(list, mergedlist, n, n+len-1, list.m_ncurrentsize-1);
    }
    else {
        for (int i=n; i<list.m_ncurrentsize; i++){
            mergedlist.m_pvector[i] = list.m_pvector[i];
        }
    }
}

template<typename Type> void Sort<Type>::MergeSort(DataList<Type> &list){
    DataList<Type> temp(list.m_nMaxSize);
    temp.m_ncurrentsize = list.m_ncurrentsize;
    int len = 1;
    while (len < list.m_ncurrentsize){
        Merge(list, temp, len);
        len *= 2;
        Merge(temp, list, len);
        len *= 2;
    }
}

template<typename Type> void Sort<Type>::RadixSort(DataList<int> &list, int m, int d){
    LinkQueue<int> *queue = new LinkQueue<int>[d];
    int power = 1;
    for (int i=0; i<m; i++){
        if (i){
            power = power * d;
        }
        for (int j=0; j<list.m_ncurrentsize; j++){
            int k = (list.m_pvector[j].GetKey() / power) % d;
            queue[k].Append(list.m_pvector[j].GetKey());
        }

        for (int j=0,k=0; j<d; j++){
            while (!queue[j].IsEmpty()){
                list.m_pvector[k++].SetKey(queue[j].Delete());
            }
        }
    }
}

test.cpp

#include <iostream>

using namespace std;

#include "Sort.h"

int main(){
    int init[15]={1,3,5,7,4,2,8,0,6,9,29,13,25,11,32};
    DataList<int> data(init, 15);
    Sort<int> sort;
    data.Print();
    cout << endl << endl <<endl;
    sort.InsertSort(data);
    sort.BinaryInsertSort(data);
    sort.ShellSort(data);
    sort.BubbleSort(data);
    sort.QuickSort(data);
    sort.SelectSort(data);
    sort.HeapSort(data);
    sort.MergeSort(data);
    sort.RadixSort(data, 2, 10);
data.Print();

    return 0;
}

时间： 2024-08-29 11:01:59

排序的相关文章

DataGrid同时具有分页和排序功能及注意点

datagrid|分页|排序当DataGrid同时具有分页和排序功能时应注意在重新绑定数据源时,MyDataGrid.CurrentPageIndex=0;下面给实现以上功能的原码,也就不多缀了aspx中包含有DataGrid和控制其数据源变化的dropdownlistDataGrid代码 <asp:datagrid id="MyDataGrid" runat="server" BorderColor="#CCCCCC" Font-Siz

用好Excel 2007的筛选和排序功能

很多人在用上Excel 2007之后可能都会惊叹于Excel 2007功能的强大,对于普通用户来说,Excel 2007最为强大的便是其数据分析能力.如果只是使用表格来记录一些简单的数据,那么使用Word 2007的表格功能就可以完成,完全没有必要请Excel 2007这位数据分析大师出马.不过数据分析也是一件说着容易做起来难的事情,这里就学习一下,如何利用筛选和排序功能,从最基本的数据分析工作做起. 筛选! 给数据"过筛子" 股市终于大涨啦,郁闷已久的股民终于看到曙光了!在众多被&q

PHP 四种基本排序算法的代码实现(1)

许多人都说算法是程序的核心,算法的好坏决定了程序的质量.作为一个初级phper,虽然很少接触到算法方面的东西.但是对于基本的排序算法还是应该掌握的,它是程序开发的必备工具.这里介绍冒泡排序,插入排序,选择排序,快速排序四种基本算法,分析一下算法的思路. 前提:分别用冒泡排序法,快速排序法,选择排序法,插入排序法将下面数组中的值按照从小到大的顺序进行排序. $arr(1,43,54,62,21,66,32,78,36,76,39); 1. 冒泡排序思路分析:在要排序的一组数中,对当前还未排好的序

PHP中使用DBM作为数据库（包括排序）

排序|数据|数据库在众多CGI语言中,PHP以其简单,快速的优点开始逐渐成长,使用PHP开发程序的人也越来越多,而一般PHP用的数据库就两种:文本以及MYSQL.文本数据库读.写速度慢,当数据到达一定量时就会大大的降低速度乃至崩溃!而MYSQL虽然速度快,功能强大,因为一般的免费空间都不支持MYSQL,因为一般的免费空间都不支持MYSQL(有主机的朋友就不要往下看了) 今天笔者介绍的是DBM数据库,DBM是柏克莱大学发展的文件/文本型数据库,在BSD系统中已经安装完毕,即使没有安装,在PHP4

link中使用动态算子实现排序的机制是什么，怎么样能优化？

问题描述 link中使用动态算子实现排序的机制是什么,怎么样能优化? link中使用动态算子实现排序的机制是什么,怎么样能优化? 解决方案使用dynamic其实是运行时反射,要想效率高,用查询表达式,google MakeMemberAccess LINQ

[数据结构] 选择排序

选择排序常用的选择排序方法有简单选择排序和堆排序,这里只说简单选择排序,堆排序后面再说. 简单选择排序设所排序序列的记录个数为n,i 取 1,2,-,n-1 . 从所有n-i+1个记录(Ri,Ri+1,-,Rn)中找出排序码最小(或最大)的记录,与第i个记录交换.执行n-1趟后就完成了记录序列的排序. 以排序数组{3,2,1,4,6,5}为例简单选择排序性能在简单选择排序过程中,所需移动记录的次数比较少.最好情况下,即待排序记录初始状态就已经是正序排列了,则不需要移动记录. 最坏

js史上最简单的数组合并去重排序

<!DOCTYPE html> <html> <head> <meta charset="UTF-8"> <title></title> <script type="text/javascript" src="js/jquery-2.1.4.js"></script> <script type="text/javascript"

排序算法之直接插入排序

直接插入排序前面学过了冒泡排序和简单选择排序后,我们现在开始学习一下直接插入排序. 概念: 直接插入排序的基本操作就是:将一个记录插入到已经排好序的有序表中,从而得到一个新的.记录数量增1的有序表. 代码如下: /**直接插入排序*/ void insertSort(int a[],int aLength) { int i,j,temp; for (i=1; i<aLength; i++) { temp = a[i]; for (j=i-1; j>=0; j--) { if (a[j]<

POJ 1106 极角排序

题意给出一些点片段圆心为t半径为r的半圆最大能覆盖多少个点. 首先在输入的时候把距离大于半径的点筛出去.剩余点通过极角排序然后枚举半圆的一条边通过该点能覆盖的点数取最大值就可以了. #include <iostream> #include<cstdio> #include<algorithm> using namespace std; struct point { int x,y; }; int Direction(point a,point b,point c) {

排序-asp.net repeater 绑定数据后怎么改变显示的顺序

问题描述 asp.net repeater 绑定数据后怎么改变显示的顺序 <ul style=" margin-left:20px"> <asp:Repeater ID="rep_data" runat="server"> <ItemTemplate> <li ><p ><span><%# Eval("data").ToString()%>: