he he.Chờ các bạn
@Edit: Ưu tiên các bạn năm nhất, năm hai, chúng ta sẽ cùng làm cùng học
.CSort.h
- Code: Chọn hết
#pragma once
/*
*/
class CSort
{
public:
CSort(void);
~CSort(void);
template<class T>
void BubbleSort(T* _list,int n,bool increase );
template<class T>
void SelectionSort(T* _list,int n,bool increase );
template<class T>
void InsertionSort(T* _list,int n,bool increase);
template<class T>
void ShellSort(T* _list, int n,bool increase);
template<class T>
void HeapSort(T* _list, int n,bool increase);
template<class T>
void QuickSort(T* _list, int n,bool increase);
template<class T>
void RadixSort(T* _list, int n,bool increase);
template<class T>
void MergeSort(T* _list, int n,bool increase);
private:
template<class T>
void MergeSort_R(T* _list, int _begin, int _end, bool increase);
template<class T>
void MergeSort_M(T* _list, int _begin,int _end, bool increase);
template<class T>
void QuickSort_R(T* _list, int _begin, int _end, bool increase);
};
CSort::CSort()
{}
CSort::~CSort()
{}
/*
*/
template<class T>
void CSort::BubbleSort(T *_list, int n, bool increase)
{
}
template<class T>
void CSort::SelectionSort(T* _list,int n,bool increase )
{}
template<class T>
void CSort::InsertionSort(T* _list,int n,bool increase)
{}
template<class T>
void CSort::ShellSort(T* _list, int n,bool increase)
{}
template<class T>
void CSort::HeapSort(T* _list, int n,bool increase)
{}
template<class T>
void CSort::RadixSort(T* _list, int n,bool increase)
{
}
template<class T>
void CSort::QuickSort(T* _list, int n,bool increase)
{
if( n < 2 ) return;
QuickSort_R(_list, 0, n - 1, increase);
}
template<class T>
void CSort::QuickSort_R(T* _list, int _begin, int _end, bool increase)
{
int left = _begin;
int right = _end;
if( left >= right )
return ;
T midleValue = _list[(int)(left + right)/2];
while( left <= right)
{
if( increase == true)
{
while(_list[left] < midleValue )
++left;
while(_list[right] > midleValue )
--right;
}
else
{
while(_list[left] > midleValue )
++left;
while(_list[right] < midleValue )
--right;
}
if( left <= right )
{
if( left < right )
{
T tempValue = _list[left];
_list[left] = _list[right];
_list[right] = tempValue;
}
++left;
--right;
}
}
QuickSort_R(_list, _begin, right, increase);
QuickSort_R(_list, left, _end, increase);
}
/*
******************* Mô Tả Giải Thuật Merge Sort *************************
+ Merge Sort áp dụng giải thuật chia để trị để sắp xếp một danh sách
Giải Thuật :
+ Chia nhỏ dãy cần sắp xếp thành n dãy con khác nhau
+ Sắp xếp n dãy con theo thứ tự tăng (giảm)
+ Trộn n dãy con lại
Độ phức tạp O(nLg(n))
Ví Dụ:
Dãy Cần SX: a = 5,3,4,1,6
Chia thành 5 dãy gồm : 5 - 3 - 4 - 1 - 6
Trộn lần lượt : ( 3 - 5), ( 1 - 4 ), (6)
( 1 - 3 - 4- 5), (6)
( 1 - 3 - 4 - 5 - 6 )
Dãy đã sắp xếp : 1,3,4,5,6
*/
template<class T>
void CSort::MergeSort(T* _list, int n,bool increase)
{
if( n > 1 )
MergeSort_R(_list, 0, n - 1, increase);
}
/*
******************* Sắp Xếp Theo MergeSort ***************************
Giải Thuật:
+ Thực hiện việc sắp xếp các phần bằng đệ quy
+ Chia _list từ _begin đến _end thành 2 phần
+ Sắp xếp 2 phần này theo thứ tự increase
+ Sau đó trộn lại
Đối Số :
+ _list : Danh sách dữ liệu cần sắp xếp
+ n : Số phần tử
+ _begin: Chỉ mục bắt đầu xử lý trên _list
+ _end : Chỉ mục ngừng xử lý trên _list
+ increase: Sắp xếp tăng ?
*/
template<class T>
void CSort::MergeSort_R(T* _list,int _begin, int _end, bool increase)
{
if ( _end - _begin + 1 < 2) return;
int middle = (_begin + _end)/2;
MergeSort_R(_list, _begin, middle, increase);
MergeSort_R(_list, middle + 1, _end, increase);
MergeSort_M(_list, _begin, _end, increase);
}
template<class T>
void CSort::MergeSort_M(T* _list,int _begin,int _end, bool increase)
{
T* temp = new T[_end - _begin + 1];
// Trộn dữ liệu vào temp
int _index = 0;
int _indexPart1 = _begin;
int middle = (_end + _begin)/2;
int _indexPart2 = middle + 1;
while( _indexPart1 <= middle && _indexPart2 <= _end)
{
if( increase == true)
temp[_index++] = ( _list[ _indexPart1] < _list[ _indexPart2 ] ? _list[ _indexPart1++ ] : _list [ _indexPart2 ++ ]);
else
temp[_index++] = ( _list[ _indexPart1] < _list[ _indexPart2 ] ? _list[ _indexPart2++ ] : _list [ _indexPart1 ++ ]);
}
while( _indexPart1 <= middle)
temp[ _index++] = _list[ _indexPart1 ++];
while( _indexPart2 <= _end )
temp[ _index++] = _list[ _indexPart2 ++];
// copy dữ liệu từ temp vào _list
for(int i = 0; i < _end - _begin + 1; ++i)
{
_list[_begin + i] = temp[i];
}
}
Okie, vậy là ae bận rộn quá rồi. Kid sẽ cố gắng đưa hết ra template và bump chủ đề 1 thời gian. Hi vọng các bạn mới đến với lập trình C/C++, sinh viên năm 1,2 cùng tham gia để chúng ta có thể hoàn thành chuyên mục này.
