7 가지 정렬 알고리즘 은 삽입 정렬, 힐 정렬, 선택 정렬, 거품 정렬, 병합 정렬, 빠 른 정렬, 쌓 기 정렬 을 포함한다.
main.cpp
#include "allSort.h"
#include "allSort.cpp"
using namespace std;
int main()
{
// int
int a[]={3,2,6,7,1,9};
allSort<int> iTest;
iTest.insertSort(a,6);
cout << "int , :" << flush;
iTest.printArray(a,6);
cout << "============================" << endl;
/* iTest.selectSort(a,6);
cout << "int , :" << flush;
iTest.printArray(a,6);
cout << "============================" << endl;
iTest.bubbleSort(a,6);
cout << "int , :" << flush;
iTest.printArray(a,6);
cout << "============================" << endl;
iTest.mergeSort(a,6);
cout << "int , :" << flush;
iTest.printArray(a,6);
cout << "============================" << endl;
iTest.quickSort(a,6);
cout << "int , :" << flush;
iTest.printArray(a,6);
cout << "============================" << endl;
iTest.heapSort(a,6);
cout << "int , :" << flush;
iTest.printArray(a,6);
cout << "============================" << endl;*/
iTest.shellSort(a,6);
cout << "int , :" << flush;
iTest.printArray(a,6);
cout << "============================" << endl;
// char
/* char b[]={'3','2','6','7','1','9'};
allSort<char> cTest;
cTest.insertSort(b,6);
cout << "char , :" << flush;
cTest.printArray(b,6);
cout << "============================" << endl;
cTest.selectSort(b,6);
cout << "char , :" << flush;
cTest.printArray(b,6);
cout << "============================" << endl;
cTest.bubbleSort(b,6);
cout << "char , :" << flush;
cTest.printArray(b,6);
cout << "============================" << endl;
cTest.mergeSort(b,6);
cout << "char , :" << flush;
cTest.printArray(b,6);
cout << "============================" << endl;
cTest.quickSort(b,6);
cout << "char , :" << flush;
cTest.printArray(b,6);
cout << "============================" << endl;*/
return 0;
}
allSort.h
/*
* =============================================================================
* Version: 0.1 (August 23, 2013)
* Author: Shanshan Guan ([email protected]), Harbin Institute of Technology Shenzhen Graduate School
*
* =============================================================================
* Copyright (c) 2013. Shanshan Guan ([email protected]).
* =============================================================================
* Introduction.
* , : 、 、 、 、 、 、
*
* =============================================================================*/
#ifndef ALLSORT_H_H_H___
#define ALLSORT_H_H_H___
#include <iostream>
using namespace std;
template <class T>
class allSort
{
public:
//
void insertSort(T a[],int n);//n is the size of array;
//
void shellSort(T a[],int n);
void shellInsert(T a[],int inc,int n);
//
void selectSort(T a[],int n);
//
void bubbleSort(T a[],int n);
//
void mergeSort(T a[],int n);
void recursionMerge(T a[],int first,int last,T temp[]);
void mergeArray(T a[],int first,int mid,int last,T temp[]);
//
void quickSort(T a[],int n);
void QuickSort(T a[],int low,int high);
//
void heapSort(T a[],int n);
void createMinHeap(T a[],int n);
void filterMinHeap(T a[],int start,int n);
void createMaxHeap(T a[],int n);
void filterMaxHeap(T a[],int start,int n);
//
void printArray(T a[],int n);
};
#endif
allSort.cpp
#include "allSort.h"
using namespace std;
template <class T> void allSort<T>::insertSort(T a[],int n)
{
if (a==NULL || n<=0)
{
cout << " !" << endl;
return ;
}
T flag;//
int j = 0;
for(int i=1;i<n;++i)
{
flag = a[i];
for(j=i-1;j>=0;j--)
{
if(flag<a[j])
{
a[j+1]=a[j];
}
else
break;
}
a[j+1]=flag;
}
}
template <class T> void allSort<T>::shellSort(T a[],int n)
{
if (a==NULL || n<=0)
{
cout << " !" << endl;
return ;
}
int inc = n/2;
for(;inc>0;inc/=2)
{
shellInsert(a,inc,n);
}
}
template <class T> void allSort<T>::shellInsert(T a[],int inc,int n)
{
int j;
T flag;
for(int i=inc;i<n;i++)
{
flag = a[i];
for(j=i-inc;j>=0;j-=inc)
{
if(flag<a[j])
{
a[j+inc]=a[j];
}
else
{
break;
}
}
a[j+inc]=flag;
/* j = i;// ,
while(j>=0 && a[j-inc]>flag)
{
a[j]=a[j-inc];
j-=inc;
}
a[j]=flag;// j<0 , */
}
}
template <class T> void allSort<T>::selectSort(T a[],int n)
{
if (a==NULL || n<=0)
{
cout << " !" << endl;
return ;
}
int min = -1;
T temp;
//i=n-1 , i<n-1
for(int i=0;i<n-1;++i)
{
min=i;
for(int j=i+1;j<n;++j)
{
if(a[min]>a[j])
{
min = j;
}
}
if(min!=i)
{
temp = a[i];
a[i] = a[min];
a[min] = temp;
}
}
}
template <class T> void allSort<T>::bubbleSort(T a[],int n)
{
if (a==NULL || n<=0)
{
cout << " !" << endl;
return ;
}
int i = 0;
int j = 0;
bool change=true;
T temp;
//
for (i=n-1;i>0&&change;--i)
{
change=false;
for (j=0;j<i;j++)
{
if(a[j]>a[j+1])
{
temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
change = true;
}
}
}
}
template <class T> void allSort<T>::mergeSort(T a[],int n)
{
if (a==NULL || n<=0)
{
cout << " !" << endl;
return ;
}
int first = 0;
int last = n-1;
T * temp = new T[n];
recursionMerge(a,first,last,temp);
}
template <class T> void allSort<T>::recursionMerge(T a[],int first,int last,T temp[])
{
int mid = (first+last)/2;
if(first<last)
{
recursionMerge(a,first,mid,temp);
recursionMerge(a,mid+1,last,temp);
mergeArray(a,first,mid,last,temp);
}
}
template <class T> void allSort<T>::mergeArray(T a[],int first,int mid,int last,T temp[])
{
int i = first;
int j = mid+1;
int m = mid;
int n = last;
int k = 0;
while(i<=m&&j<=n)
{
if(a[i]<a[j])
temp[k++] = a[i++];
else
temp[k++] = a[j++];
}
while(i<=m)
{
temp[k++] = a[i++];
}
while(j<=n)
{
temp[k++] = a[j++];
}
for (int index = 0; index < k; ++index)
{
a[first+index]=temp[index];
}
}
template <class T> void allSort<T>::quickSort(T a[],int n)
{
if (a==NULL || n<=0)
{
cout << " !" << endl;
return ;
}
QuickSort(a,0,n-1);
}
template <class T> void allSort<T>::QuickSort(T a[],int low,int high)
{
int i = low;
int j = high;
int key = a[low];
while(low<high)
{
while(low<high && a[high]>=key)
--high;
a[low] = a[high];
while(low<high && a[low]<=key)
++low;
a[high] = a[low];
}
a[low] = key;
if(low<high)
{
QuickSort(a,i,low-1);
QuickSort(a,low+1,j);
}
}
template <class T> void allSort<T>::heapSort(T a[],int n)
{
if (a==NULL || n<=0)
{
cout << " !" << endl;
return ;
}
int size;
// createMinHeap(a,n);
createMaxHeap(a,n);
for(size=n-1;size>0;size--)
{
swap(a[0],a[size]);
// filterMinHeap(a,0,size);
filterMaxHeap(a,0,size);
}
}
template <class T> void allSort<T>::createMinHeap(T a[],int n)
{
// (n-2)/2? (n-1)/2; ,
int start = (n-2)/2;
for (start = (n-2)/2; start >=0; start--)
{
filterMinHeap(a,start,n);
}
}
template <class T> void allSort<T>::createMaxHeap(T a[],int n)
{
// (n-2)/2? (n-1)/2; ,
int start = (n-2)/2;
for (start = (n-2)/2; start >=0; start--)
{
filterMaxHeap(a,start,n);
}
}
// , ,
template <class T> void allSort<T>::filterMinHeap(T a[],int start, int n)
{
int i=start;
int j=2*i+1;
T temp = a[i];
while(j<n)
{
if(j+1<n && a[j]>a[j+1])
++j;
if(a[j]>temp)
break;
else
{
a[i] = a[j];
i=j;
j=2*i+1;
}
a[i]=temp;
}
}
// , ,
template <class T> void allSort<T>::filterMaxHeap(T a[],int node,int n)
{
int left = 2*node+1;
int right = 2*node+2;
int largest = node;
if (left<n && a[left]>a[node])
largest = left;
if (right<n && a[right]>a[largest])
largest = right;
if (largest!=node)
{
swap(a[largest],a[node]);
filterMaxHeap(a,largest,n);
}
}
template <class T> void allSort<T>::printArray(T a[],int n)
{
for(int i=0;i<n;++i)
cout << a[i] << " " << flush;
cout << endl;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.