/* 冒泡排序 插入排序 二路插入排序 希尔排序 快速排序 选择排序 归并排序 堆排序算法的 C/C++实现。 作者:feosun 日期:2008年10月12日 参考资料:数据结构(C语言版) 清华大学出版社 */ #include <iostream>
using namespace std;
// 交换两个数的值 void swap(
int &a,
int &b)
{
int tmp;
tmp=a;
a=b;
b=tmp;
}
// 屏幕输出数组 void display(
int array[],
int len)
{
cout<<"the result is:"<<endl;
for (
int i = 0 ;i < len;i++ )
{
cout<<array[i]<<" ";
}
cout<<endl;
}
/* 冒泡排序 算法思想:将被排序的记录数组R[1..n]垂直排列,每个记录R[i]看作是重量为R[i].key的气泡。 根据轻气泡不能在重气泡之下的原则,从下往上扫描数组 R:凡扫描到违反本原则的 轻气泡,就使其向上"飘浮"。如此反复进行,直到最后任何两个气泡都是轻者在上, 重者在下为止。 时间复杂度 o(n^2) 空间复杂度 o(1) 比较次数 n(n+1)/2 */ void bubble_sort(
int array[],
int len)
{
for (
int i = len-1 ;i >= 0;i-- )
{
for(
int j = 0;j < i;j++)
if(array[j] > array[j+1])
swap(array[j],array[j+1]);
}
}
/* 直接插入排序 算法思想:把n个待排序的元素看成为一个有序表和一个无序表,开始时有序表中只包含一个元 素,无序表中包含有n-1个元素,排序过程中每次从无序表中取出第一个元素,将它 插入到有序表中的适当位置,使之成为新的有序表,重复n-1次可完成排序过程。 时间复杂度 o(n^2) 空间复杂度 o(1) 比较次数 n(n+1)/2 */ void insert_sort(
int array[],
int len)
{
int tmp,i,j;
for(i = 1;i < len;i++)
{
if (array[i] < array[i-1])
{
tmp = array[i];
array[i] = array[i-1];
// 插入到相应位置 for (j = i-2;j >= 0;j--)
{
// 往后移 if (array[j] > tmp )
array[j+1] = array[j];
else {
array[j+1] = tmp;
break;
}
}
if(j == -1)
array[j+1] = tmp;
}
}
}
/* 2-路插入排序 算法思想:增加一个辅助空间d,把r[1]赋值给d[1],并将d[1]看成是排好序后处于中间 位置的记录。然后从r[2]开始依次插入到d[1]之前或之后的有序序列中。 时间复杂度 o(n^2) 空间复杂度 o(1) 比较次数 n(n+1)/2 */ void bi_insert_sort(
int array[],
int len)
{
int* arr_d = (
int *)malloc(
sizeof(
int) * len);
arr_d[0] = array[0];
int head = 0,tail = 0;
for (
int i = 1;i < len; i++ )
{
if (array[i] > arr_d[0])
{
int j;
for ( j= tail;j>0;j--)
{
if (array[i] < arr_d[j])
arr_d[j+1] = arr_d[j];
else break;
}
arr_d[j+1] = array[i];
tail += 1;
}
else {
if (head ==0)
{
arr_d[len-1] = array[i];
head =len-1;
}
else {
int j;
for (j = head;j <= len-1;j++)
{
if (array[i] > arr_d[j])
arr_d[j-1] = arr_d[j];
else break;
}
arr_d[j-1] = array[i];
head -= 1;
}
}
}
for (
int i = 0;i < len; i++)
{
int pos = (i + head );
if(pos >= len) pos -= len;
array[i] = arr_d[pos];
}
free(arr_d);
}
/* 希尔排序 算法思想:先将整个待排序记录分割成若干子序列分别进行直接插入排 序,待整个序列中的记录基本有序时,再对全体记录进行一 次直接插入排序 时间复杂度 o(n^2) 空间复杂度 o(1) 比较次数 ? */ void shell_insert(
int array[],
int d,
int len)
{
int tmp,j;
for (
int i = d;i < len;i++)
{
if(array[i] < array[i-d])
{
tmp = array[i];
j = i - d;
do {
array[j+d] = array[j];
j = j - d;
}
while (j >= 0 && tmp < array[j]);
array[j+d] = tmp;
}
}
}
void shell_sort(
int array[],
int len)
{
int inc = len;
do {
inc = inc/2;
shell_insert(array,inc,len);
}
while (inc > 1);
}
/* 快速排序 算法思想:将原问题分解为若干个规模更小但结构与原问题相似的子问题。递 归地解这些子问题,然后将这些子问题的解组合成为原问题的解。 时间复杂度 o(nlogn) 空间复杂度 o(logn) 比较次数 ? */ int partition(
int array[],
int low,
int high)
{
int pivotkey = array[low];
while (low < high)
{
while(low < high && array[high] >= pivotkey)
--high;
swap(array[low],array[high]);
while(low < high && array[low] <= pivotkey)
++low;
swap(array[low],array[high]);
}
array[low] = pivotkey;
return low;
}
void quick_sort(
int array[],
int low,
int high)
{
if (low < high)
{
int pivotloc = partition(array,low,high);
quick_sort(array,low,pivotloc-1);
quick_sort(array,pivotloc+1,high);
}
}
/* 直接选择排序 算法思想:每一趟在n-i+1个记录中选取关键字最小的记录作为有序序列中的第i个记录 时间复杂度 o(n^2) 空间复杂度 o(1) ? 比较次数 n(n+1)/2 */ int SelectMinKey(
int array[],
int iPos,
int len)
{
int ret = 0;
for (
int i = iPos; i < len; i++)
{
if (array[ret] > array[i])
{
ret = i;
}
}
return ret;
}
void select_sort(
int array[],
int len)
{
for (
int i = 0; i < len; i++)
{
int j = SelectMinKey(array,i,len);
if (i != j)
{
swap(array[i],array[j]);
}
}
}
/* 归并排序 算法思想:设两个有序的子文件(相当于输入堆)放在同一向量中相邻的位置上:R[low..m],R[m+1..high],先 将它们合并到一个局部的暂存向量R1(相当于输出堆)中,待合并完成后将R1复制回R[low..high]中。 时间复杂度 o(nlogn) 空间复杂度 o(n) 比较次数 ? */ void merge(
int array[],
int i,
int m,
int n)
{
int j,k;
int iStart = i, iEnd = n;
int arrayDest[256];
for ( j = m + 1,k = i; i <= m && j <= n; ++k)
{
if (array[i] < array[j])
arrayDest[k] = array[i++];
else arrayDest[k] = array[j++];
}
if (i <= m)
for (;k <= n; k++,i++)
arrayDest[k] = array[i];
if(j <= n)
for (;k <= n; k++,j++)
arrayDest[k] = array[j];
for(j = iStart; j <= iEnd; j++)
array[j] = arrayDest[j];
}
void merge_sort(
int array[],
int s,
int t)
{
int m;
if (s < t)
{
m = (s + t )/2;
merge_sort(array,s,m);
merge_sort(array,m+1,t);
merge(array,s,m,t);
}
}
/* 堆排序 算法思想:堆排序(Heap Sort)是指利用堆(heaps)这种数据结构来构造的一种排序算法。 堆是一个近似完全二叉树结构,并同时满足堆属性:即子节点的键值或索引总是 小于(或者大于)它的父节点。 时间复杂度 o(nlogn) 空间复杂度 o(1) 比较次数 较多 */ void heap_adjust(
int array[],
int i,
int len)
{
int rc = array[i];
for(
int j = 2 * i; j <len; j *= 2)
{
if(j < len && array[j] < array[j+1]) j++;
if(rc >= array[j])
break;
array[i] = array[j]; i = j;
}
array[i] = rc;
}
void heap_sort(
int array[],
int len)
{
int i;
for(i = (len-1)/2; i >= 0; i--)
heap_adjust(array,i,len);
for( i = (len-1); i > 0; i--)
{
swap(array[0],array[i]);
// 弹出最大值,重新对i-1个元素建堆 heap_adjust(array,0,i-1);
}
}
int main() {
int array[] = {45,56,76,234,1,34,23,2,3,55,88,100};
int len =
sizeof(array)/
sizeof(
int);
// bubble_sort(array,len); // 冒泡排序 /* insert_sort(array,len); */ // 插入排序 /* bi_insert_sort(array,len); */ // 二路插入排序 /* shell_sort(array,len); */ // 希尔排序 /* quick_sort(array,0,len-1); */ // 快速排序 /* select_sort(array,len); */ // 选择排序 /* merge_sort(array,0,len-1); */ // 归并排序 heap_sort(array,len);
// 堆排序 display(array,len);
return 0;
}