정렬 알고리즘 (2) 거품 정렬, 빠 른 정렬, 정렬 및 기수 정렬 MSD, LSD
20382 단어 데이터 구조
#include
#include
#include
#include
#include
//
using namespace std;
void pri(int *arr, size_t size)
{
for (size_t i = 0; i < size; ++i)
{
cout << arr[i] << " ";
}
cout << endl;
}
// : ,
void BubbleSort(int* array, size_t size)
{
assert(array);
for (size_t i = 0; i < size; ++i)
{
for (size_t j = 1; j < size - i; ++j)
{
if (array[j] < array[j - 1])
swap(array[j], array[j - 1]);
}
}
}
//////////////////////////////////////////////////////////////////////////////////////
// : key , key , ;
int QSort(int* array, size_t size, int left, int right)
{
int key = array[left];
while(left < right)
{ //key
while (left < right&&array[right] >= key)
--right;
swap(array[left], array[right]);
while ( left < right && array[left] <= key)
++left;
swap(array[left], array[right]);
}
return left;
}
void QuickSort(int* array, size_t size, int left, int right)
{
if (leftint pivotloc = QSort(array, size, left, right);
//
QuickSort(array, size, left, pivotloc - 1);
QuickSort(array, size, pivotloc + 1, right);
}
}
void QuickSort(int* array, size_t size)
{
assert(array);
QuickSort(array, size, 0, size-1);
}
//////////////////////////////////////////////////////////////////////
template<typename T>
void merge(T array[], int low, int mid, int high)
{
int k = 0;
// , ,
T* temp = new T[high - low + 1];
int lbegin = low;
int lend = mid;
int rbegin = mid + 1;
int rend = high;
// , ,
for (; lbegin <= lend && rbegin <= rend; ++k)
{
if (array[lbegin] <= array[rbegin])
{
temp[k] = array[lbegin++];
}
else
{
temp[k] = array[rbegin++];
}
}
if (lbegin <= lend) // ,
{
memcpy(temp + k, array + lbegin, (lend - lbegin + 1)*sizeof(T));
}
if (rbegin <= rend) // ,
{
memcpy(temp + k, array + rbegin, (rend - rbegin + 1)*sizeof(T));
}
memcpy(array + low, temp, (high - low + 1)*sizeof(T));//
delete[]temp;
}
template<typename T>
void merge_sort(T array[], unsigned int first, unsigned int last)
{
int mid = 0;
if (first//mid = (first+last)/2; /* */
mid = first + ((last - first) >> 1);
//mid = (first & last) + ((first ^ last) >> 1);
merge_sort(array, first, mid);
merge_sort(array, mid + 1, last);
merge(array, first, mid, last);
}
}
////////////////////LSD MSD ///////////////////////////
// n
int GetValue(int key, int n)
{
return (key / (int)pow(10, n - 1)) % 10;// pow double, double
}
int GetBit(int *arr,size_t size)//
{
assert(arr);
int ret = 1;
for (size_t i = 0; i < size; i++)
{
while (arr[i] / int(pow(10, ret)) > 0)
{
ret++;
}
}
return ret;
}
///////////////////////////////////////////////////////////////
// LSD
void RadixSortLSD(int *arr,size_t size)
{
assert(arr);
vector<queue<int> > v1(10);//10 ( )
int bit = GetBit(arr, size);
for (int i = 1; i <= bit; ++i)
{
for (size_t j = 0; j < size; ++j)
{
v1[ GetValue(arr[j], i) ].push(arr[j]);
}
for (size_t i = 0; i < size;)
{
for (int j = 0; j < 10; ++j)
{
while (!v1[j].empty())
{
arr[i] = v1[j].front();
v1[j].pop();
++i;
}
}
}
}
}
///////////////////////////////////////////
// MSD: , ;
void RadixMSD(int *arr, vector<int > &tmp, size_t size, int bit)
{
vector<queue<int> > v1(10);//10 ( )
for (size_t j = 0; j < size; ++j)
{
v1[GetValue(arr[j], bit)].push(arr[j]);
}
// tmp
for (size_t j = 0; j < 10; ++j)
{
tmp[j] = v1[j].size();
}
for (size_t i = 0; i < size;)
{
for (int j = 0; j < 10; ++j)
{
while (!v1[j].empty())
{
arr[i] = v1[j].front();
v1[j].pop();
++i;
}
}
}
}
void RadixSortMSD(int *arr, size_t size, int bit)
{
if ( bit > 0 && size > 0 )
{
vector<int> tmp(10);
RadixMSD(arr, tmp, size, bit);
for (size_t i = 0; i < 10; i++)
{
RadixSortMSD(arr, tmp[i], bit - 1);
arr += tmp[i];
}
}
return;
}
void RadixSortMSD(int *arr, size_t size)
{
assert(arr);
int bit = GetBit(arr, size);
RadixSortMSD(arr, size, bit);
}
테스트 함수
void test3()
{
int arr[] = { 1, 30, 21, 35, 99, 5, 21, 45, 18, 49, 25, 16, 100, 52, 8, 13 };
//BubbleSort(arr, sizeof(arr) / sizeof(int));
//pri(arr, sizeof(arr) / sizeof(int));
QuickSort(arr, sizeof(arr) / sizeof(int));
pri(arr, sizeof(arr) / sizeof(int));
}
void test4()
{
int array[] = { 1, 30, 21, 35, 99, 5, 21, 45, 18, 1, 30, 21, 35, 99, 5, 21, 45, 18, 49, 25, 16, 100, 52, 8, 13 };
pri(array, sizeof(array) / sizeof(int));
MergeSort(array, sizeof(array) / sizeof(int));
pri(array, sizeof(array) / sizeof(int));
int array1[] = { 99, 5, 21, 45, 18, 49, 21, 45, 18, 49, 25, 16, 100, 52, 8, 13 };
pri(array1, sizeof(array1) / sizeof(int));
Mergesort(array1, sizeof(array1) / sizeof(int));
pri(array1, sizeof(array1) / sizeof(int));
}
void test5()
{
int array[] = { 1, 30, 21, 35, 99, 5, 21, 10045, 18, 751, 1000, 216, 375, 25, 16, 100, 52, 8, 13 };
pri(array, sizeof(array) / sizeof(int));
RadixSortLSD(array, sizeof(array) / sizeof(int));
pri(array, sizeof(array) / sizeof(int));
int array1[] = { 3001, 3809, 2521, 9935, 2959, 5, 21, 10045, 18, 751, 1000, 216, 375, 25, 16, 100, 52, 8, 13 };
//int array1[] = { 19,18,17,15,14,13,16,12,11 };
pri(array1, sizeof(array1) / sizeof(int));
RadixSortMSD(array1, sizeof(array1) / sizeof(int));
pri(array1, sizeof(array1) / sizeof(int));
}
int main()
{
//test1();
//test2();
//test3();
//test4();
test5();
system("pause");
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.