冒泡排序
#include <iostream.h>
template <class T>
void bubblesort(T *p, int n)
{
for(int i=0;i<n;i++)
cout<<p[i]<<" "; //output the value before sort
cout<<endl;
int flag=1,count=0;
for(int i=0;(i<n-1)&&flag;i++)//attention the condition of loop
{
count++;//count the number of loop
flag=0;
for(int j=0;j<n-1-i;j++)//attention the condition of loop
if(p[j]>p[j+1])
{
T temp;
temp=p[j];
p[j]=p[j+1];
p[j+1]=temp;
flag=1;
}
}
cout<<count<<endl;
}
template <class T>
void print(T *arr, int n)
{
for(int i=0;i<n;i++)
cout<<arr[i]<<" ";
cout<<endl;
}
int main()
{
int arr[4]={42,52,55,68};
int iarr[5];
for(int i=0;i<5;i++)
{
iarr[i]=rand()%100;
}
bubblesort(iarr,5);
cout<<endl;
print(iarr,5);
}
插入排序
#include <iostream.h>
template <class T>
void insertsort(T *p, int n)
{
for(int i=0;i<n;i++)//output the values before sort
cout<<p[i]<<" ";
cout<<endl;
int count=0;
for(int j=1;j<n;j++)
{
T temp=p[j];
while(j>0&&(temp<p[j-1]))
{p[j]=p[--j];
//count++;
}
p[j]=temp;
}
}
template <class T>
void print(T *arr, int n)
{
for(int i=0;i<n;i++)
cout<<arr[i]<<" ";
cout<<endl;
}
int main()
{
int arr[4]={42,52,55,68};
int iarr[5];
for(int i=0;i<5;i++)
{
iarr[i]=rand()%100;
}
insertsort(iarr,5);
cout<<endl;
print(iarr,5);
}
选择排序
#include <iostream.h>
template <class T>
void selectsort(T *p, int n)
{
for(int i=0;i<n;i++)//output the values before sort
cout<<p[i]<<" ";
cout<<endl;
int count=0;
for(int j=0;j<n-1;j++)
{
int h=j;
for(int k=j+1;k<n;k++)
{if(p[h]>p[k])
h=k;
count++;
}
if(h!=j)
{
T temp=p[h];
p[h]=p[j];
p[j]=temp;
}
}
cout<<"the count= "<<count<<endl;
}
template <class T>
void print(T *arr, int n)
{
for(int i=0;i<n;i++)
cout<<arr[i]<<" ";
cout<<endl;
}
int main()
{
int arr[4]={42,52,55,68};
int iarr[5];
for(int i=0;i<5;i++)
{
iarr[i]=rand()%100;
}
selectsort(iarr,5);
cout<<endl;
print(iarr,5);
}
快速排序
**********quick sort**********
#include
template
void q_sort(T*, int, int);
template
void quick_sort(T numbers[], int array_size)
{
q_sort(numbers, 0, array_size - 1);
}
template
void q_sort(T numbers[], int left, int right)
{
int pivot, l_hold, r_hold;
l_hold = left;
r_hold = right;
pivot = numbers[left];
while (left < right)
{
while ((numbers[right] >= pivot) && (left < right))
right--;
if (left != right)
{
numbers[left] = numbers[right];
left++;
}
while ((numbers[left] <= pivot) && (left < right))
left++;
if (left != right)
{
numbers[right] = numbers[left];
right--;
}
}
numbers[left] = pivot;
pivot = left;
left = l_hold;
right = r_hold;
if (left < pivot)
q_sort(numbers, left, pivot-1);
if (right > pivot)
q_sort(numbers, pivot+1, right);
}
int main()
{
int number[5]={23,345,768,34,12};
quick_sort(number,5);
for(int i=0;i<5;i++)
cout<cout<return 0;
}
********merge sort**********
The merge sort is slightly faster than the heap sort for larger sets, but it requires twice the memory of the heap sort because of the second array. This additional memory requirement makes it unattractive for most purposes - the quick sort is a better choice most of the time and the heap sort is a better choice for very large sets.
Like the quick sort, the merge sort is recursive which can make it a bad choice for applications that run on machines with limited memory.
Source Code
Below is the basic merge sort algorithm.
template
void mergeSort(T numbers[], T temp[], int array_size)
{
m_sort(numbers, temp, 0, array_size - 1);
}
template
void m_sort(T numbers[], T temp[], int left, int right)
{
int mid;
if (right > left)
{
mid = (right + left) / 2;
m_sort(numbers, temp, left, mid);
m_sort(numbers, temp, mid+1, right);
merge(numbers, temp, left, mid+1, right);
}
}
template
void merge(T numbers[], T temp[], int left, int mid, int right)
{
int i, left_end, num_elements, tmp_pos;
left_end = mid - 1;
tmp_pos = left;
num_elements = right - left + 1;
while ((left <= left_end) && (mid <= right))
{
if (numbers[left] <= numbers[mid])
{
temp[tmp_pos] = numbers[left];
tmp_pos = tmp_pos + 1;
left = left +1;
}
else
{
temp[tmp_pos] = numbers[mid];
tmp_pos = tmp_pos + 1;
mid = mid + 1;
}
}
while (left <= left_end)
{
temp[tmp_pos] = numbers[left];
left = left + 1;
tmp_pos = tmp_pos + 1;
}
while (mid <= right)
{
temp[tmp_pos] = numbers[mid];
mid = mid + 1;
tmp_pos = tmp_pos + 1;
}
for (i=0; i <= num_elements; i++)
{
numbers[right] = temp[right];
right = right - 1;
}
}
*********heap sort************
Pros: In-place and non-recursive, making it a good choice for extremely large data sets.
Cons: Slower than the merge and quick sorts.
As mentioned above, the heap sort is slower than the merge and quick sorts but doesn't use multiple arrays or massive recursion like they do. This makes it a good choice for really large sets, but most modern computers have enough memory and processing power to handle the faster sorts unless over a million items are being sorted.
The "million item rule" is just a rule of thumb for common applications - high-end servers and workstations can probably safely handle sorting tens of millions of items with the quick or merge sorts. But if you're working on a common user-level application, there's always going to be some yahoo who tries to run it on junk machine older than the programmer who wrote it, so better safe than sorry.
Source Code
Below is the basic heap sort algorithm. The siftDown() function builds and reconstructs the heap.
void heapSort(int numbers[], int array_size)
{
int i, temp;
//build the heap and sort the front half
for (i = (array_size / 2)-1; i >= 0; i--)
siftDown(numbers, i, array_size);
for (i = array_size-1; i >1; i--)
{
//swap the first element and the last element, the first element is the largest
temp = numbers[0];
numbers[0] = numbers[i];
numbers[i] = temp;
//recursive the build heap function
siftDown(numbers, 0, i-1);
}
}
void siftDown(int numbers[], int root, int bottom)
{
int done, maxChild, temp;
done = 0;
while ((root*2 <= bottom) && (!done))
{
if (root*2 == bottom)
maxChild = root * 2;
//root*2+1>=bottom check the scope of the array, otherwise, it may overflow
else if ((numbers[root * 2] > numbers[root * 2 + 1])|((root*2+1)>=bottom))
maxChild = root * 2;
else
//the follow three line's function is equavilent to 'root*2+1>=bottom'
// if((root*2+1)>=bottom)
// maxChild = root * 2;
// else
maxChild = root * 2 + 1;
if (numbers[root] < numbers[maxChild])
{
temp = numbers[root];
numbers[root] = numbers[maxChild];
numbers[maxChild] = temp;
root = maxChild;
}
else
done = 1;
}
}
|
