#include <iostream>
using namespace std;
class listnode
{
public:
int elem;
listnode* next;
listnode()
{
next = 0;
}
};
class list
{
public:
listnode* head;
list()
{
head = NULL;
}
~list()
{
listnode* t = head;
while (t != 0)
{
listnode* tmp = t;
t = t->next;
delete tmp;
}
}
void insertElem(int elem)
{
listnode* node = new listnode();
node->elem = elem;
node->next = 0;
if (head == NULL)
{
head = node;
}
else
{
if (node->elem < head->elem)
{
node->next = head;
head = node;
}
else
{
listnode* prev = head;
listnode* t = head->next;
while (t != 0)
{
if (node->elem < t->elem)
{
prev->next = node;
node->next = t;
return ;
}
prev = t;
t = t->next;
}
prev->next = node;
}
}
}
void print_list()
{
listnode* t = head;
while (t)
{
cout << t->elem << " ";
t = t->next;
}
cout << endl;
}
};
void print_array(int* array, int size)
{
for (int i=0; i<size; i++)
cout << array[i] << " ";
cout << endl;
}
void bucket_sort(int* array, int size)
{
list* buckets = new list[10]; //假设分成10个区间
for (int i=0; i<10; i++)
buckets[i].head = NULL;
for (int i=0; i<size; i++)
{
int which_bucket = array[i] / 100;
buckets[which_bucket].insertElem(array[i]);
}
int m = 0;
for (int i=0; i<10; i++)
{
// copy back
listnode* t = buckets[i].head;
while (t != 0)
{
array[m] = t->elem;
t = t->next;
m++;
}
}
delete[] buckets;
}
void main()
{
int* array = 0;
int size;
cout << "input the size:";
cin >> size;
array = new int[size];
for (int i=0; i<size; i++)
{
array[i] = rand()%1000;
}
print_array(array, size);
bucket_sort(array, size);
print_array(array, size);
}
#include <iostream>
using namespace std;
void print_array(int* array, int size)
{
for (int i=0; i<size; i++)
cout << array[i] << " ";
cout << endl;
}
// 比逐个比较每两个省去一次比较时间
void get_min_max(int* array, int size, int& min, int& max)
{
min = max = array[0];
int minIdx = 0, maxIdx = 0;
for (int i=0; i<size-1; i+=2)
{
if (array[i] < array[i+1]) // 一次比较
{
minIdx = i;
maxIdx = i+1;
}
else
{
minIdx = i+1;
maxIdx = i;
}
if (array[minIdx] < min) // 二次比较
min = array[minIdx];
if (array[maxIdx] > max) // 三次比较
max = array[maxIdx];
}
if (size % 2 != 0)
{
if (array[size-1] < min)
min = array[size-1];
if (array[size-1] > max)
max = array[size-1];
}
}
void main()
{
int* array = 0;
int size;
cout << "input the size:";
cin >> size;
array = new int[size];
for (int i=0; i<size; i++)
array[i] = rand()%1000;
print_array(array, size);
int min, max;
get_min_max(array, size, min, max);
cout << "min:" << min << " max:" << max << endl;
}
#include <iostream>
using namespace std;
void print_array(int* array, int size)
{
for (int i=0; i<size; i++)
cout << array[i] << " ";
cout << endl;
}
// a modified version of quick sort.
int partition(int* array, int low, int high, int digit)
{
int x = array[high] % (digit * 10) / digit;
int i, j;
i = low - 1;
for (j=low; j<=high-1; j++)
{
if ((array[j] % (digit * 10) / digit) <= x)
{
i++;
swap(array[i], array[j]);
}
}
swap(array[i+1], array[high]);
return i+1;
}
void quick_sort_impl(int* array, int low, int high, int digit)
{
if (low < high)
{
int q = partition(array, low, high, digit);
quick_sort_impl(array, low, q-1, digit);
quick_sort_impl(array, q+1, high, digit);
}
}
void quick_sort(int* array, int size, int digit)
{
quick_sort_impl(array, 0, size-1, digit);
}
void radix_sort(int* array, int size, int digits)
{
// 从低位到高位依次排序
int mul = 1;
for (int i=0; i<digits; i++)
{
quick_sort(array, size, mul);
mul *= 10;
}
}
void main()
{
int* array = 0;
int size = 0;
cout << "Input the size:";
cin >> size;
array = new int[size];
for (int i=0; i<size; i++)
{
array[i] = rand()%9999;
}
print_array(array, size);
radix_sort(array, size, 4);
print_array(array, size);
}
#include <iostream>
using namespace std;
void print_array(int* array, int size)
{
for (int i=0; i<size; i++)
cout << array[i] << " ";
cout << endl;
}
int partition(int* array, int low, int high)
{
int x = array[high];
int i, j;
i = low - 1;
for (j=low; j<=high-1; j++)
{
if (array[j] <= x)
{
i++;
swap(array[i], array[j]);
}
}
swap(array[i+1], array[high]);
return i+1;
}
void quick_sort_impl(int* array, int low, int high)
{
if (low < high)
{
int q = partition(array, low, high);
quick_sort_impl(array, low, q-1);
quick_sort_impl(array, q+1, high);
}
}
void quick_sort(int* array, int size)
{
quick_sort_impl(array, 0, size-1);
}
void main()
{
int* array;
int size;
cin >> size;
array = new int[size];
for (int i=0; i<size; i++)
array[i] = rand()%100;
print_array(array, size);
quick_sort(array, size);
print_array(array, size);
}
#include <iostream>
using namespace std;
void print_array(int* array, int size)
{
for (int i=0; i<size; i++)
cout << array[i] << " ";
cout << endl;
}
void count_sort(int* array, int size, int range)
{
int* counts = new int[range];
int* sorted = new int[size];
int i;
memset(counts, 0, sizeof(int) * range);
// first, count the elements
for (i=0; i<size; i++)
{
counts[array[i]]++;
}
print_array(counts, range);
// now the counts stores all the counts of every element
// calculate the position of the element
for (i=1; i<range; i++)
{
counts[i] = counts[i] + counts[i-1];
}
print_array(counts, range);
// put the elements in the right position to the sorted array
for (i=0; i<size; i++)
{
sorted[counts[array[i]]-1] = array[i];
counts[array[i]]--;
}
// copy back to the original
memcpy(array, sorted, sizeof(int) * size);
delete[] sorted;
delete[] counts;
}
void main()
{
int* array;
int size;
int range;
cout << "input the size of array:";
cin >> size;
cout << "input the max elements of array:";
cin >> range;
array = new int[size];
// make sure the data are all in the range
for (int i=0; i<size; i++)
{
array[i] = rand()%range;
}
print_array(array, size);
count_sort(array, size, range);
print_array(array, size);
delete[] array;
}
#include <iostream>
using namespace std;
void print_array(int* array, int size);
void build_heap(int* array, int size);
void swap(int& a, int& b);
void heapify(int* array, int node, int size);
void heap_sort(int* array, int size);
void main()
{
int* array;
int size;
cin >> size;
array = new int[size];
for (int i=0; i<size; i++)
array[i] = rand()%100;
print_array(array, size);
build_heap(array, size);
print_array(array, size);
heap_sort(array, size);
print_array(array, size);
}
void print_array(int* array, int size)
{
for (int i=0; i<size; i++)
cout << array[i] << " ";
cout << endl;
}
// build a heap
void build_heap(int* array, int size)
{
int parent = size / 2 - 1;
for(parent = size / 2 - 1; parent >=0; parent--)
{
heapify(array, parent, size);
}
}
void swap(int& a, int& b)
{
int t = a;
a = b;
b = t;
}
// make a parent node's value greater than its children
void heapify(int* array, int node, int size)
{
// is it a leaf?
if (node > size / 2 - 1)
return ;
int left_child = node * 2 + 1;
int right_child = left_child + 1;
int max = node;
if (left_child < size && array[left_child] > array[max])
max = left_child;
if (right_child < size && array[right_child] > array[max])
max = right_child;
// if exchanged, it may affects the 'heap attribute' of its children
if (max != node)
{
swap(array[node], array[max]);
heapify(array, max, size);
}
}
// sort. first, build a heap, than, extract the top node.
void heap_sort(int* array, int size)
{
build_heap(array, size);
for (int i=size-1; i>0; i--)
{
swap(array[i], array[0]);
heapify(array, 0, i);
}
}
