クイックソート、集計ソート、改善されたソート
クイックソート、集計ソート、改善されたソート
クイックソート&&集計ソート
改善された集計ソートアルゴリズム
[転入][アルゴリズム設計と分析]集計ソートと高速ソートの平均時間の比較(C++)(https://blog.csdn.net/a120790391/article/details/80712917)
集計ソートおよび改善(https://blog.csdn.net/wangchao701123/article/details/81266734?depth_1-utm_source=distribute.pc_relevant.none-task&utm_source=distribute.pc_relevant.none-task)
クイックソート&&集計ソート
#include
#include
using namespace std;
//
int Split(int a[], int low, int high)
{
int i = low, temp;
if (a[low] < a[(low + high) / 2])
{
if (a[low] < a[high])
{
if (a[(low + high) / 2] < a[high])
{
temp = a[(low + high) / 2];
a[(low + high) / 2] = a[low];
a[low] = temp;
}
else
{
temp = a[high];
a[high] = a[low];
a[low] = temp;
}
}
}
else
{
if (a[(low + high) / 2] < a[high])
{
if (a[low] > a[high])
{
temp = a[high];
a[high] = a[low];
a[low] = temp;
}
}
else
{
temp = a[(low + high) / 2];
a[(low + high) / 2] = a[low];
a[low] = temp;
}
}
for (int j = low + 1; j <= high; j++)
{
if (a[j] < a[low])
{
i++;
if (i != j)
{
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
}
temp = a[i];
a[i] = a[low];
a[low] = temp;
return i;
}
//
void QuickSort(int a[], int low, int high) {
if (low < high) {
int w = Split(a, low, high);
QuickSort(a, low, w - 1);
QuickSort(a, w + 1, high);
}
}
//
void merge(int a[], int first, int mid, int end, int c[])
{
int pbotton = first;
int f = first, m = mid;
while (f < mid && m <= end)
if (a[f] < a[m])
c[pbotton++] = a[f++];
else
c[pbotton++] = a[m++];
if (f == mid)
while (m <= end)
c[pbotton++] = a[m++];
else
while (f < mid)
c[pbotton++] = a[f++];
for (int i = first; i <= end; i++)
a[i] = c[i];
}
//
void mergeSort(int a[], int low, int high, int c[])
{
if (low < high)
{
mergeSort(a, low, (low + high) / 2, c);
mergeSort(a, (low + high) / 2 + 1, high, c);
merge(a, low, (low + high) / 2 + 1, high, c);
}
}
int main()
{
int random = 5000, j = 1;
int* merge_array, * quick_array, * c;
clock_t start, end, start1, end1;
srand((int((NULL))));
cout << " \t \t " << endl;
while (j <= 10)
{
merge_array = new int[random * j];
quick_array = new int[random * j];
c = new int[random * j];
for (int i = 0; i < random * j; i++)
{
merge_array[i] = rand();
quick_array[i] = merge_array[i];
}
start = clock();
mergeSort(merge_array, 0, random * j - 1, c);
end = clock();
delete[]merge_array;
start1 = clock();
QuickSort(quick_array, 0, random * j - 1);
end1 = clock();
delete[]quick_array;
delete[]c;
cout << random * j << "\t\t" << static_cast<double>(end - start) / CLOCKS_PER_SEC * 1000 << "ms\t\t";
cout << static_cast<double>(end1 - start1) / CLOCKS_PER_SEC * 1000 << "ms" << endl;
j++;
}
return 0;
}
改善された集計ソートアルゴリズム
#include
#include
#include
using namespace std;
//
template<typename T>
void __Merge(T arr[], int l, int mid, int r)
{
T* arr1 = new T[r - l + 1];
int k = 0, i = l, j = mid + 1;
for (; k < r - l + 1 && i <= mid && j <= r; k++)
{
if (arr[i] >= arr[j])
arr1[k] = arr[j++];
else
arr1[k] = arr[i++];
}
while (i <= mid)
arr1[k++] = arr[i++];
while (j <= r)
arr1[k++] = arr[j++];
for (int m = 0; m < r - l + 1; m++)
{
arr[m + l] = arr1[m];
}
delete[] arr1;
}
//
template<typename T>
void InsertionSort(T arr[], int l, int r)
{
for (int i = l + 1; i <= r; i++)
{
// 3
T temp = arr[i];
int j = i;// temp
for (; j > l&& arr[j - 1] > temp; j--)
{
arr[j] = arr[j - 1];
}
arr[j] = temp;
}
}
template<typename T>
void __MergeSort(T arr[], int l, int r)
{
if (r - l <= 15)
{
InsertionSort(arr, l, r);
return;
}
int mid = l + (r - l) / 2;
__MergeSort(arr, l, mid);
__MergeSort(arr, mid + 1, r);
if (arr[mid] > arr[mid + 1])
__Merge(arr, l, mid, r);
}
template<typename T>
void MergeSort(T arr[], int n)
{
__MergeSort(arr, 0,n-1);
}
int main()
{
int random = 5000, j = 1;
int* merge_array, * c;
clock_t start, end;
srand((int((NULL))));
cout << " \t " << endl;
while (j <= 10)
{
merge_array = new int[random * j];
c = new int[random * j];
for (int i = 0; i < random * j; i++)
{
merge_array[i] = rand();
}
start = clock();
MergeSort(merge_array,random * j - 1);
end = clock();
delete[]merge_array;
delete[]c;
cout << random * j << "\t\t" << static_cast<double>(end - start) / CLOCKS_PER_SEC * 1000 << "ms\t\t"<<endl;
j++;
}
return 0;
}
[転入][アルゴリズム設計と分析]集計ソートと高速ソートの平均時間の比較(C++)(https://blog.csdn.net/a120790391/article/details/80712917)
集計ソートおよび改善(https://blog.csdn.net/wangchao701123/article/details/81266734?depth_1-utm_source=distribute.pc_relevant.none-task&utm_source=distribute.pc_relevant.none-task)