各種排序算法C++類實現
/***
- *
- *
- 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);
}
}
//////////////////////////////////////////////////////////////////// </pre>
openkk 
jopen 
quguiliang 
yanguz123