闲来无事,于是把常用的排序算法自己写了一遍,也当做是复习一下。
/***************************************************************
* *
* *
* Date : 2012. 05. 03 *
* Author : 397090770 *
* Email : wyphao.2007@163.com *
* *
* *
***************************************************************/
#include <iostream>
#include <iomanip.h>
#define LEN 100 //排序数的个数
#define NUM 10 //每行输出的字数个数
using namespace std;
////////////////////////////////////////////////////////////////////
//树节点
template <class T>
class Node{
public:
Node *left;
Node *right;
T data;
Node() : left(NULL), right(NULL), data(NULL){}
~Node(){}
};
////////////////////////////////////////////////////////////////////
class Sort{
public:
Sort(){};
~Sort(){};
//快速排序
template <class T>
void QuickSort(T arr[], int low, int hight);
//选择排序
template <class T>
void SelectSort(T arr[], int len);
//冒泡排序
template <class T>
void BubbleSort(T arr[], int len);
//插入排序
template <class T>
void InsertSort(T arr[], int len);
//堆排序
template <class T>
void HeapSort(T arr[], int len);
//二叉排序树排序
template <class T>
void TreeSort(T arr[], int len);
private:
//快速排序中选择中心点
template <class T>
int Quick(T arr[], int left, int right);
//建立堆
template <class T>
void CreateHeap(T arr[], int root, int len);
//建立二叉排序树
template <class T>
Node<T>* BuildTree(Node<T>*root, T data);
//中序遍历二叉排序树
template <class T>
void InTree(Node<T> *root, T arr[]);
};
////////////////////////////////////////////////////////////////////
int main(){
Sort sort;
int *arr; //需要排序的数组
int width = 0; //最大数的位数,用于排列输出结果
int len = LEN; //用来求最大数的位数
arr = (int *)malloc(LEN * sizeof(int)); //分配空间
if(arr == NULL){ //空间分配失败
cout << "Malloc failed!" << endl;
exit(1);
}
srand(time(NULL)); //设置种子
for(int i = 0; i < LEN ;i++){ //随机生成数字
arr[i] = (rand() % (LEN * 10)) + 1;
}
//sort.SelectSort(arr, LEN);
sort.TreeSort(arr, LEN);
//求得最大数的位数,用于排列输出结果
while(len){
width++;
len /= 10;
}
for(int i = 0; i < LEN; i++){ //输出排序后的数字
cout << setw(width) << arr[i] << " ";
cout << fixed;
if((i + 1) % NUM == 0){ //每行输出的数字个数
cout << endl;
}
}
cout << endl;
return 0;
}
////////////////////////////////////////////////////////////////////
//快速排序
template <class T>
void Sort::QuickSort(T arr[], int low, int hight){
int pivot = -1;
if(low <= hight){
pivot = Quick(arr, low, hight);
QuickSort(arr, low, pivot - 1);
QuickSort(arr, pivot + 1, hight);
}
}
//返回中轴点的下标
template <class T>
int Sort::Quick(T arr[], int left, int right){
int i = left + 1, j = right;
int flag = left;
int temp;
while(i <= j){
while(i <= j && arr[i] < arr[flag]){
++i;
}
while(i <= j && arr[j] > arr[flag]){
--j;
}
if(i < j){
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
++i;
--j;
}
}
temp = arr[flag];
arr[flag] = arr[j];
arr[j] = temp;
return j;
}
////////////////////////////////////////////////////////////////////
//选择排序
template <class T>
void Sort::SelectSort(T arr[], int len){
int index;
T temp;
for(int i = 0; i < len - 1; i++){
index = i;
for(int j = i + 1; j < len; j++){
if(arr[index] > arr[j]){
index = j;
}
}
if(index != i){
temp = arr[index];
arr[index] = arr[i];
arr[i] = temp;
}
}
}
////////////////////////////////////////////////////////////////////
//冒泡排序
template <class T>
void Sort::BubbleSort(T arr[], int len){
T temp;
bool flags = true;
for(int i = len - 1; i > 0; i--){
if(flags){
flags = false;
for(int j = 0; j < i; j++){
if(arr[j] > arr[j + 1]){
flags = true;
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
for(int k = 0; k < LEN; k++){
cout << arr[k] << " ";
}
cout << endl;
}
}
}else{
break;
}
}
}
////////////////////////////////////////////////////////////////////
//插入排序
template <class T>
void Sort::InsertSort(T arr[], int len){
T temp;
int i, j;
for(i = 1; i < len; i++){
temp = arr[i];
for(j = i - 1; j >= 0; j--){
if(temp < arr[j]) {
arr[j + 1] = arr[j];
}else{
break;
}
}
arr[j + 1] = temp;
}
}
////////////////////////////////////////////////////////////////////
//堆排序
template <class T>
void Sort::HeapSort(T arr[], int len){
int i;
T buff;
T *temp = (T *)malloc(sizeof(T) * (len + 1));
if(temp == NULL){
cout << "Malloc Error!" << endl;
exit(1);
}
for(i = 1; i < len + 1; i++){ //复制数组,使得偏移从1开始,这样好计算左孩子和右孩子坐标
temp[i] = arr[i - 1];
}
//建立子堆
for(i = len / 2; i >= 1; i--){
CreateHeap(temp, i, len);
}
for(i = len - 1; i >= 1; i--){
buff = temp[1];
temp[1] = temp[i + 1];
temp[i + 1] = buff;
CreateHeap(temp, 1, i);
}
for(i = 1; i < len + 1; i++){
arr[i - 1] = temp[i];
}
}
//建立堆
template <class T>
void Sort::CreateHeap(T arr[], int root, int len){
int j = 2 * root; //root's left child, right (2 * root + 1)
T temp = arr[root];
bool flags = false;
while(j <= len && !flags){
if(j < len){
if(arr[j] < arr[j + 1]){ // Left child is less then right child
++j; // Move the index to the right child
}
}
if(temp < arr[j]){
arr[j / 2] = arr[j];
j *= 2;
}else{
flags = true;
}
}
arr[j / 2] = temp;
}
////////////////////////////////////////////////////////////////////
//二叉排序树排序
template <class T>
void Sort::TreeSort(T arr[], int len){
Node <T>*root = NULL;
for(int i = 0; i < len; i++){
root = BuildTree(root, arr[i]);
}
InTree(root, arr);
}
//建立二叉排序树
template <class T>
Node<T>* Sort::BuildTree(Node<T>*root, T data){
Node<T> *tempNode = root;
Node<T> *parentNode = NULL;
Node<T> *newNode = new Node<T>;
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
if(root == NULL){//空树的时候
return newNode;
}else{
while(tempNode != NULL){
parentNode = tempNode;
if(tempNode->data >= data){
tempNode = tempNode->left;
}else{
tempNode = tempNode->right;
}
}
if(parentNode->data >= data){
parentNode->left = newNode;
}else{
parentNode->right = newNode;
}
}
return root;
}
//中序遍历二叉排序树,将二叉树的节点存储在数组中
template <class T>
void Sort::InTree(Node<T> *root, T arr[]){
static int index = 0;
if(root != NULL){
InTree(root->left, arr);
arr[index++] = root->data;
InTree(root->right, arr);
}
}
////////////////////////////////////////////////////////////////////
分享到:
相关推荐
各种排序算法的C++模板类实现,完整的代码类,供大家参考。
C++模板类的形式实现了基本的数据结构和算法:交换算法、快排序、选择排序、归并排序、二叉树、AVL树、2-3树、双向链表、队列等。红黑树还没完成。
选择不同类型的数据类型,完成数组数据的排序操作,排序分别为单向冒泡排序,双向冒泡排序和快速排序。
爆肝整理!堪称全网最详细的十大常用经典排序算法总结!!! C++模板类实现,附带部分测试用例!!!
C++模板类实现的动态数组、双向循环链表、队列、栈等数据结构,以及基于迭代器的静态查找和排序算法,包括顺序查找、折半查找、简单选择排序(用于单向迭代器)、快速排序(双向迭代器)、堆排序(随机迭代器)。...
快速排序算法测试,操作符重载,模板应用. 在VS2005下调试通过
c++ STL模板实现简单排序及元素的交换实例 本实例实现的排序方法是在开发中常用的排序算法模式
一种支持类模版和函数模版的C++双向链表,实现了各种排序算法(排序原则可定制),包含学生信息的使用示例(VC 6.0、VS2008).
此文讨论平衡排序二叉树的实现算法, 重点解决平衡排序二叉树在插入、删除结点时的平衡化问题, 可作为演练教学之用也具 有实用价值。
我自己写的C++课设程序,二叉树类模版。 自认为是初学者的“杰作”。 包含二叉树的常用操作:前中后层遍历算法。
C++模板类实现的动态数组、双向循环链表、队列、栈等数据结构,以及基于迭代器的静态查找和排序算法,包括顺序查找、折半查找、简单选择排序(用于单向迭代器)、快速排序(双向迭代器)、堆排序(随机迭代器)
配套本人博文 C++中模板类继承的实现,在列表中实现了四种不同的排序算法
14.4.2 排序算法的下限 465 第15章 动态规划 467 15.1 算法思想 467 15.2 应用 469 15.2.1 0/1背包问题 469 15.2.2 图像压缩 471 15.2.3 矩阵乘法链 476 15.2.4 最短路径 480 15.2.5 网络的无交叉子集 483 15.2.6 ...
321页的程序,代码可以直接拷贝出来使用。太好的资料! 1、顺序表 1 Seqlist.h 1 Test.cpp 6 2、单链表 8 ListNode.h 8 ...18、排序 249 Data.h 249 QueueNode.h 255 LinkQueue.h 259 Sort.h 263 test.cpp 278
18.4.2 排序算法的下限 第19章 动态规划 19.1 算法思想 19.2 应用 19.2.1 0/1背包问题 19.2.2 矩阵乘法链 19.2.3 所有顶点对之间的最短路径 19.2.4 带有负值的单源最短路径 19.2.5 网组的无交叉子集 19.3 参考及推荐...
《数据结构与算法分析C++描述》 (第3版)是数据结构和算法分析的经典教材,书中使用主流的程序设计语言C++作为具体的实现语言。书的内容包括表、栈、队列、树、散列表、优先队列、排序、不相交集算法、图论算法、算法...
14.4.2 排序算法的下限 465 第15章 动态规划 467 15.1 算法思想 467 15.2 应用 469 15.2.1 0/1背包问题 469 15.2.2 图像压缩 471 15.2.3 矩阵乘法链 476 15.2.4 最短路径 480 15.2.5 网络的无交叉子集 483 15.2.6 ...
有一个模板类写出了快速排序,冒泡排序,插入排序,选择排序四种算法。用的是C++哦
压缩包里面包含多个目录,包含了多种查找算法、递归的示例、堆栈使用、队列、二叉树、各种排序算法、进制转换与位操作、链表的使用、C++模板类与模板函数、数组的使用、流与文件、素数与回文数、图论、指针的使用。...
*5.6 C++处理字符串的方法——字符串类与字符串变量 5.6.1 字符串变量的定义和引用 5.6.2 字符串变量的运算 5.6.3 字符串数组 5.6.4 字符串运算举例 习题 第6章 指针 6.1 指针的概念 6.2 变量与指针 6.2.1 定义...