快速排序
#include <iostream>
using namespace std; void swap(int num[], int i, int j)
{
int temp = num[i];
num[i] = num[j];
num[j] = temp;
} int partition(int num[], int left, int right)
{
int key = left;
int value = num[key];
while (left < right)
{
while (left < right && num[right] >= value)right--;
while (left < right && num[left] <= value)left++;
swap(num, right, left);
}
swap(num, key, left);
return left;
} void QuickSort(int num[], int begin, int end)
{
if (begin < end)
{
int middle = partition(num, begin, end);
QuickSort(num, begin, middle - );
QuickSort(num, middle + , end);
}
} int main()
{
int num[];
int n = ;
while (cin >> n)
{
for (int i = ; i < n; i++)
{
int temp = ;
cin >> temp;
num[i] = temp;
}
QuickSort(num, , n - );
for (int i = ; i < n; i++)
cout << num[i] << " ";
cout << endl;
}
return ;
}
归并排序
#include <iostream>
using namespace std; void Merge(int *from, int *to, int begin, int middle, int end)
{
int i = begin;
int j = middle + ;
int k = i;
while (i <= middle && j <= end)
{
if (from[i] < from[j])
to[k++] = from[i++];
else to[k++] = from[j++];
}
while (i <= middle) to[k++] = from[i++];
while (j <= end) to[k++] = from[j++];
} void MergePass(int *from, int *to, int end, int h)
{
int i = ;
while (i <= end - * h + )
{
Merge(from, to, i, i + h - , i + * h - );
i += * h;
}
if (i < end - h + )
Merge(from, to, i, i + h - , end);
else
for (int k = i; k <= end; k++)
{
to[k] = from[k];
}
} void MergeSort(int *from, int *to, int begin, int end)
{
int h = ;
while (h <= end)
{
MergePass(from, to, end, h);
h = * h;
MergePass(to, from, end, h);
h = * h;
}
} int main() {
int num[];
int num2[];
int n = ;
while (cin >> n)
{
for (int i = ; i < n; i++)
{
int temp = ;
cin >> temp;
num[i] = temp;
}
MergeSort(num, num2, , n - );
for (int i = ; i < n; i++)
cout << num[i] << " ";
cout << endl;
}
return ;
}
堆排序
#include <stdio.h> void HeapAdjust(int *num, int s, int length)
{
int temp = num[s];
int child = * s + ;
while (child < length)
{
if (child + < length && num[child] < num[child + ])
child++;
if (num[s] < num[child])
{
num[s] = num[child];
num[child] = temp;
s = child;
child = * s + ;
}
else
break;
}
} void buildingHeap(int *num, int length)
{
for (int i = (length - ) / ; i >= ; --i)
HeapAdjust(num, i, length);
} void HeapSort(int *num, int length)
{
buildingHeap(num, length);
for (int i = length - ; i > ; --i)
{
int temp = num[];
num[] = num[i];
num[i] = temp;
HeapAdjust(num, , i);
}
} void print(int num[], int n) {
for (int i = ; i < n; i++) {
printf("%d ", num[i]);
}
printf("\n");
} int main()
{
int num[];
int n = ;
while (scanf("%d", &n) != EOF)
{
for (int i = ; i < n; i++)
scanf("%d", &num[i]);
HeapSort(num, n);
print(num, n);
}
return ;
}