C言語でよく見られる並べ替え方法(挿入順序、ヒルの並べ替え、選択順序、積み上げ順序、泡の並べ替え、迅速な並べ替え)
並べ替えの挿入
void PrintArray(int* a, int n)
{
for (size_t i = 0; i < n; ++i)
{
printf("%d ", a[i]);
}
printf("
");
}
void InsertSort(int* a, int n)
{
// end 0 n-2
for (int i = 0; i < n - 1; ++i)
{
//
// [0,end] tmp,
int end = i;
int tmp = a[end + 1];
while (end >= 0)
{
if (a[end] > tmp)
{
a[end + 1] = a[end];
--end;
}
else
{
break;
}
}
a[end + 1] = tmp;
}
}
void TestInsertSort()
{
int a[] = { 3, 6, 2, 5, 7, 9, 8, 6, 1, 4 };
InsertSort(a, sizeof(a) / sizeof(int));
PrintArray(a, sizeof(a) / sizeof(int));
}
ヒルの並べ替え// :O(N^1.3) : ( , )
void ShellSort(int* a, int n)
{
// gap > 1
// gap == 1
int gap = n;
while (gap > 1)
{
// gap
gap = gap / 3 + 1; // +1 1
for (int i = 0; i < n - gap; ++i)
{
int end = i;
int tmp = a[end + gap];
while (end >= 0)
{
if (a[end] > tmp)
{
a[end + gap] = a[end];
end -= gap;
}
else
{
break;
}
}
a[end + gap] = tmp;
}
}
}
void TestShellSort()
{
int a[] = { 3, 6, 2, 5, 7, 9, 8, 6, 1, 4 };
ShellSort(a, sizeof(a) / sizeof(int));
PrintArray(a, sizeof(a) / sizeof(int));
}
並べ替えを選択void Swap(int* p1, int* p2)
{
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
// O(N*N)
void SelectSort(int* a, int n)
{
int begin = 0, end = n - 1;
while (begin < end)
{
// [begin, end] ,
int mini = begin, maxi = end;
for (int i = begin; i <= end; ++i)
{
if (a[i] > a[maxi])
maxi = i;
if (a[i] < a[mini])
mini = i;
}
Swap(&a[begin], &a[mini]);
//
if (begin == maxi)
maxi = mini;
Swap(&a[end], &a[maxi]);
//printf("[%d,%d]", begin, end);
//PrintArray(a, n);
++begin;
--end;
}
}
void TestSelectSort()
{
int a[] = { 3, 6, 2, 5, 7, 9, 8, 6, 1, 4 };
// int a[] = { 9, 6, 2, 5, 7, 3, 8, 6, 1, 4 };
SelectSort(a, sizeof(a) / sizeof(int));
PrintArray(a, sizeof(a) / sizeof(int));
}
積み上げ順序void AdjustDwon(int* a, int n, int root)
{
int parent = root;
int child = parent * 2 + 1;
while (child < n)
{
//
if (child+1 < n && a[child+1] > a[child])
{
++child;
}
// 1、 , ,
// 2、 ,
if (a[child] > a[parent])
{
Swap(&a[child], &a[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
// O(N*LogN)
void HeapSort(int* a, int n)
{
// ,
// O(N)
for (int i = (n-1-1)/2; i >= 0; --i)
{
AdjustDwon(a, n, i);
}
int end = n - 1;
while (end > 0)
{
//
Swap(&a[0], &a[end]);
//
AdjustDwon(a, end, 0);
--end;
}
}
void TestHeapSort()
{
int a[] = { 3, 6, 2, 5, 7, 9, 8, 6, 1, 4 };
// int a[] = { 9, 6, 2, 5, 7, 3, 8, 6, 1, 4 };
HeapSort(a, sizeof(a) / sizeof(int));
PrintArray(a, sizeof(a) / sizeof(int));
}
泡の並べ替えvoid BubbleSort(int* a, int n)
{
//
for (int end = n - 1; end > 0; --end)
{
int flag = 0;
for (int i = 0; i < end; ++i)
{
if (a[i] > a[i + 1])
{
Swap(&a[i], &a[i + 1]);
flag = 1;
}
}
if (flag == 0)
{
break;
}
}
}
void TestBubbleSort()
{
int a[] = { 3, 6, 2, 5, 7, 9, 8, 6, 1, 4 };
// int a[] = { 9, 6, 2, 5, 7, 3, 8, 6, 1, 4 };
BubbleSort(a, sizeof(a) / sizeof(int));
PrintArray(a, sizeof(a) / sizeof(int));
}
クイックソート// hoare
int HoareMethod(int* a, int begin, int end)
{
// end key, / begin key,
int key = a[end];
int keyindex = end;
while (begin < end)
{
// begin
while (begin < end && a[begin] <= key)
++begin;
// end
while (begin < end && a[end] >= key)
--end;
Swap(&a[begin], &a[end]);
}
Swap(&a[begin], &a[keyindex]);
return begin;
}
// hoare, , ,
int DigHoleMethod(int* a, int begin, int end)
{
int key = a[end];
while (begin < end)
{
//
while (begin < end && a[begin] <= key)
++begin;
a[end] = a[begin]; // , end
while (begin < end && a[end] >= key)
--end;
a[begin] = a[end]; // , begin
}
a[begin] = key;
return begin;
}
// ,
int PrevCurMethod(int* a, int begin, int end)
{
int prev = begin-1;
int cur = begin;
int key = a[end];
while (cur < end) // key
{
if (a[cur] < key && ++prev != cur)
Swap(&a[prev], &a[cur]);
++cur;
}
++prev;
Swap(&a[prev], &a[end]);
return prev;
}
void QuickSort(int* a, int begin, int end)
{
if (begin >= end)
return;
int keyindex = PrevCurMethod(a, begin, end);
// [begin, keyindex-1] key [keyindex+1,end]
QuickSort(a, begin, keyindex - 1);
QuickSort(a, keyindex+1, end);
}
void TestQuickSort()
{
int a[] = { 3, 3, 2, 5, 7, 9, 8, 6, 1, 5 };
QuickSort(a, 0, sizeof(a) / sizeof(int)-1);
PrintArray(a, sizeof(a) / sizeof(int));
}