堆排序：
void HeapAdjust(int *arraydata,int rootnode,int len)
{
int j;
int t;
while(*rootnode+<len)
{
j=*rootnode+;
if ((j+)<len) //基右子树存在,则比较左右子树的大小
{
if(arraydata[j]<arraydata[j+]) //若左子树小于右子树，则调整为右子树于其双亲结点比较
{
j++;
}
}
if (arraydata[rootnode]<arraydata[j]) //若双亲结点小于兄弟结点，则进行交换
{
t=arraydata[rootnode];
arraydata[rootnode]=arraydata[j];
arraydata[j]=t;
rootnode=j; //堆被破坏，需要重新调整
}
else
break;
}
}
void HeapSort(int *data,int n)
{
int t,i;
int j;
for (i=n/-;i>=;i--)
{
HeapAdjust(data,i,n);
} for (int k=;k<n;k++)// 输出原始数据树建的堆数据
{
cout<<data[k]<<" ";
}
cout<<endl; for(i=n-;i>;i--)
{
t=data[];
data[]=data[i];
data[i]=t; for (int i=;i<n;i++) //输出交换后的数据，即将根结构的数据放到最后，使其成为有序序列
{
cout<<data[i]<<" ";
}
cout<<endl; HeapAdjust(data,,i); //将前i个数据重新构成堆 for (int i=;i<n;i++) //输出堆数据
{
cout<<data[i]<<" ";
}
cout<<endl;
}
}
int main(int argc,char* argv)
{
int b[]={,,,,,,,};
n=sizeof (b)/sizeof(b[]); for (int i=;i<n;i++)
{
cout<<b[i]<<",";
}
cout<<endl; HeapSort(b,n); for (int i=;i<n;i++)
{
cout<<b[i]<<",";
}
cout<<endl; return ;
}
参考资料：
void mybubble(int *a,int n)
{
if (NULL==a&&n<=)
{
printf("parameter error!\n");
} int i,j;
int temp;
for(i=;i<n-;i++) //控制外层循环，n个数需要n-1次
for(j=n-;j>=i;j--) //从后往前比较
//for(j=0;j<n-1-i;j++)//从前往后比较，控制内情循环，每次比较n-1-i次
{
if (a[j]>a[j+])//如果前一个数大于后一个数，则交换
{
temp=a[j];
a[j]=a[j+];
a[j+]=temp;
} } display(a,n); }
#include <stdio.h>
/* 选择排序
插入排序
冒泡排序
希尔排序
堆排序
快速排序 */
////////////////////////////////////////////////////////
void SelectSort(int *a,int n)
{
int i,j;
int temp=;
int flag=; for (i=;i<n-;i++)
{
temp=a[i]; //暂存要比较的数
flag=i; //记录temp中存放数据的标号
for (j=i+;j<n;j++)//从i+1到n间的数据进行操作
{
if (a[j]<temp) //找出比a[i]中小的数据
{
temp=a[j];
flag=j;
}
} if (flag!=i)//将最小的数放入a[i]中
{
a[flag]=a[i];
a[i]=temp;
}
}
} /////////////////////////////////////////////////////
void InsertSort(int *a,int n)
{
int i,j;
int temp;
for (i=;i<n;i++)
{
temp=a[i]; //暂存当前比较的数
for (j=i-;j>=;j--)//从i-1到0间的数据进行操作
{
if (temp<a[j]) //检查是否有插入的可能
{
a[j+]=a[j];
}
else
break;
} a[j+]=temp;//最后插入
}
} //////////////////////////////////////////////////
void BubbleSort(int *a,int n)
{
int i,j;
int temp;
for (i=;i<n-;++i)
{
for (j=n-;j>i;--j)//从n-1到i，即从前到后，将最小的值放到前面
{
if (a[j]<a[j-])
{
temp=a[j];
a[j]=a[j-];
a[j-]=temp;
}
}
}
} /////////////////////////////////////////////////////
void ShellSort(int *a,int n)
{
int i,j;
int step;
int temp; for (step=n/;step>;step=step/) //第k趟排序
{
for (i=step;i<n;i++)
{
temp=a[i];
for (j=i-step;j>=;j-=step)
{
if (temp<a[j])
{
a[j+step]=a[j];
}
else
break;
}
a[j+step]=temp;
}
} }
/////////////////////////////////////////////////
void AdjustMinHeap(int *a,int pos,int len)
{
int temp;
int child; for (temp=a[pos];*pos+<=len;pos=child)
{
child=*pos+;
if (child<len&&a[child]>a[child+])
{
child++;
}
if (a[child]<temp)
{
a[pos]=a[child];
}
else
break;
}
a[pos]=temp;
} void MinHeapSort(int *a,int len)
{
int i;
int temp;
for (i=len/-;i>=;i--)
{
AdjustMinHeap(a,i,len-);
}
for (i=len-;i>=;i--)
{
temp=a[];
a[]=a[i];
a[i]=temp;
AdjustMinHeap(a,,i-);
}
} void AdjustMaxHeap(int *a,int pos,int len)//生成大根堆
{
while((*pos+)<len)
{
int m=*pos+;
if((*pos+)<len)
{
if(a[*pos+]<a[*pos+])
m=*pos+;
}
if (a[pos]<a[m]) //堆被破坏，需要调整
{
int tempData=a[pos]; //交换数据
a[pos]=a[m];
a[m]=tempData; pos=m;
}
else
break; //堆未破坏，无需调整
}
} void MaxHeapSort(int *a,int len)
{
int i=; for (i=len/-;i>=;i--) //将数组建成大根堆
{
AdjustMaxHeap(a,i,len);
} for (i=len-;i>;i--)
{
int temp=a[]; //与最后一个记录交换
a[]=a[i];
a[i]=temp; AdjustMaxHeap(a,,i);//重新将数据调整为大根堆
}
}
//////////////////////////////////////////////////
void QuickSort(int *a,int left,int right)
{
int i,j,temp;
i=left;
j=right;
temp=a[left];
if (left>right)
{
return;
} while(i!=j)
{
while(a[j]>=temp&&j>i)
{
j--;
} if (j>i) //将大值放于后面
{
a[i++]=a[j];
} while (a[i]<=temp&&j>i)
{
i++;
} if(j>i) //将小值放于前面
{
a[j--]=a[i]; }
} a[i]=temp;
QuickSort(a,left,i-);
QuickSort(a,i+,right);
} ////////////////////////////////////////////////
int main()
{ int i=;
int a[]={,,,,,,};
int len=sizeof(a)/sizeof(a[]); for(i=;i<len;i++)
printf("%d ",a[i]);
printf("\n"); // SelectSort(a,len);
// BubbleSort(a,len);
// InsertSort(a,len);
// ShellSort(a,len);
// MinHeapSort(a,len);
// MaxHeapSort(a,len);
QuickSort(a,,len-); for(i=;i<len;i++)
printf("%d ",a[i]);
printf("\n"); return ;
}
#include <iostream> using namespace std; void display(int a[],int len)
{
for(int i=;i<len;i++)
{
printf("%d ",a[i]);
}
printf("\n"); } //插入排序
void insert(int *a,int n)
{
int i,j,temp; for(i=;i<;i++) /*外循环控制趟数，n个数从第2个数开始到最后共进行n-1次插入*/
{
temp=a[i]; /*将待插入数暂存于变量t中*/
for( j=i- ; j>= && temp<a[j] ; j-- ) /*在有序序列（下标0 ~ i-1）中寻找插入位置*/
a[j+]=a[j]; /*若未找到插入位置，则当前元素后移一个位置*/
a[j+]=temp; /*找到插入位置，完成插入*/
}
display(a,n);
}
//希尔排序
void shellSort(int a[],int len)
{
int step;
int i,j;
int temp;
for(step=len/; step>;step/=) //用来控制步长,最后递减到1
{
// i从第step开始排列，应为插入排序的第一个元素
// 可以先不动，从第二个开始排序
for(i=step;i<len;i++)
{
temp = a[i];
for(j=i-step;(j>= && temp < a[j]);j-=step)
{
a[j+step] = a[j];
}
a[j+step] = temp; //将第一个位置填上
} }
display(a,len);
}
//选择排序
void choise(int *a,int n)
{
int i,j,k,temp;
for(i=;i<n-;i++) /*外循环控制趟数，n个数选n-1趟*/
{
k=i; /*假设当前趟的第一个数为最值,记在k中 */
for(j=i+;j<n;j++) /*从下一个数到最后一个数之间找最值*/
if(a[k]>a[j]) /*若其后有比最值更大的*/
k=j; /*则将其下标记在k中*/ if(i!=k) /*若k不为最初的i值，说明在其后找到比其更大的数*/
{ /*则交换最值和当前序列的第一个数*/
temp=a[i];
a[i]=a[k];
a[k]=temp;
}
}
display(a,n);
}
//堆排序
/*假设节点i的左右子树都是最大堆，操作使节点i的子树变成最大堆*/
void maxHeap(int A[],int len,int i)
{
int l,r,large,temp;
l=*i;
r=*i+;
large=i;
if(l<len)
{
if(A[l]>A[i])
{
large=l;
}
}
if(r<len)
{
if(A[r]>A[large])
{
large=r;
}
} if(large!=i)
{
temp=A[large];
A[large]=A[i];
A[i]=temp;
maxHeap(A,len,large);
}
} /*建立大根堆*/
void buildMaxHeap(int A[],int len)
{
int i;
for(i=len/-;i>=;i--)
maxHeap(A,len,i);
} /*堆排序*/
void maxHeapSort(int A[],int len)
{
int i,temp;
buildMaxHeap(A,len);
printf("建立大跟堆\n");
for(i=;i<len;i++)
printf("%d ",A[i]);
printf("\n"); for(i=len;i>;i--)
{
temp=A[];
A[]=A[i-];
A[i-]=temp;
printf("%d ",A[i-]);
buildMaxHeap(A,i-);
}
printf("\n");
}
//冒泡排序
void bubble(int *a,int n) /*定义两个参数：数组首地址与数组大小*/
{
int i,j,temp;
for(i=;i<n-;i++) /*外循环控制排序趟数，n个数排n-1趟 */
for(j=;j<n--i;j++) /*内循环每次比较的次数，第i次比较n-i次*/
if(a[j]>a[j+]) //相信元素比较，逆序则交换
{
temp=a[j];
a[j]=a[j+];
a[j+]=temp;
}
display(a,n);
}
//快速排序
void quick_sort(int *arr, int begin, int end)
{
char pivot = arr[begin];
int i,j;
i = begin;
j = end;
while(i < j)
{
while(arr[j] >= pivot && i < j)
j --;
arr[i] = arr[j];
while(arr[i] <= pivot && i < j)
i ++;
arr[j] = arr[i];
}
arr[i] = pivot;
if( i- > begin)
quick_sort(arr, begin, i - );
if( end > i + )
quick_sort(arr, i + , end); //display(arr,end+1);
}
//基数排序
#define GET_MASK_VALUE(x, mask, shift) (((x) & mask) >> (shift))
int find_max(int array[], int len, int mask, int shift)
{
int i = ;
int max = GET_MASK_VALUE(array[i], mask, shift); for (i = ; i < len; i++) {
if (GET_MASK_VALUE(array[i], mask, shift) > max)
max = GET_MASK_VALUE(array[i], mask, shift);
} return max;
} void count_sort(int array[], int sort[], int len, int mask, int shift)
{
int i, max;
int *temp = NULL; max = find_max(array, len, mask, shift); printf("mask:%-8x shift:%d\n", mask, shift); temp = (int *)malloc((max + )* sizeof(int));
if (temp == NULL) {
return;
} memset(temp, , sizeof(int) * (max + )); for (i = ; i < len; i++) {
temp[GET_MASK_VALUE(array[i], mask, shift)]++;
} for (i = ; i <= max; i++) {
temp[i] += temp[i-];
} for (i = (len - ); i >= ; i--) {
sort[temp[GET_MASK_VALUE(array[i], mask, shift)]-] = array[i];
temp[GET_MASK_VALUE(array[i], mask, shift)]--;
}
} void radix_sort(int array[], int len, int digit_bits, int bit_width)
{
int i = ;
int *sort = NULL;
int cycles = , shift = ;
unsigned int mask = ;
unsigned int initmask = ( << bit_width) - ; sort = (int *)malloc(sizeof(int) * len);
if (sort == NULL)
return; memset(sort, , sizeof(int) * len); cycles = digit_bits / bit_width; for (i = ; i < cycles; i++) {
mask = initmask << (i * bit_width);
shift = i * bit_width;
count_sort(array, sort, len, mask, shift);
memcpy(array, sort, sizeof(int) * len);
} return;
} void main(void)
{ const int Asize=;
printf("------------插入排序-----------------------\n");
int a[]={,,,,,,,,};
display(a,);
insert(a,); printf("------------希尔排序-------------------------\n");
int b[]={,,,,,,,,};
display(b,);
shellSort(b,); printf("------------冒泡排序-------------------------\n");
int c[]={,,,,,,,,};
display(c,);
bubble(c,); printf("------------快速排序-------------------------\n");
int d[]={,,,,,,,,};
display(d,);
quick_sort(d,,);
display(d,); printf("------------选择排序------------------------\n");
int e[]={,,,,,,,,};
display(e,);
choise(e,); printf("------------堆排序-------------------------\n");
int f[]={,,,,,,,,};
display(f,);
maxHeapSort(f,);
display(f,); printf("------------基数排序---------------------\n");
int g[]={,,,,,,,,};
display(g,);
radix_sort(g,,sizeof(int)*,);
display(g,); }
一、冒泡法：
基本思想：如果有n个数，则要进行n-1趟比较。在第1趟比较中要进行n-1次相邻元素的两两比较，在第j趟比较中要进行n-j次两两比较。比较的顺序从前往后，经过一趟比较后，将最值沉底（换到最后一个元素位置），最大值沉底为升序，最小值沉底为降序。
相邻元素两两比较，每趟将最值沉底即可确定一个数在结果的位置，确定元素位置的顺序是从后往前，其余元素可能作相对位置的调整。可以进行升序或降序排序。
源代码：
void bubble(int *a,int n) /*定义两个参数：数组首地址与数组大小*/
{
int i,j,temp;
for(i=;i<n-;i++) /*外循环控制排序趟数，n个数排n-1趟 */
for(j=;j<n--i;j++) /*内循环每次比较的次数，第i次比较n-i次*/
if(a[j]>a[j+]) //相信元素比较，逆序则交换
{
temp=a[j];
a[j]=a[j+];
a[j+]=temp;
}
}
优点：稳定，比较次数已知；
缺点：慢，每次只能移动相邻两个数据，移动数据的次数多。
二、选择排序
基本思想：每趟选出一个最值和无序序列的第一个数交换，n个数共选n-1趟。第i趟假设i为最值下标，然后将最值和i+1至最后一个数比较，找出最值的下标，若最值下标不为初设值，则将最值元素和下标为i的元素交换。
每趟是选出一个最值确定其在结果序列中的位置，确定元素的位置是从前往后，而每趟最多进行一次交换，其余元素的相对位置不变。可进行降序排序或升序排序。
定义外部n-1次循环，假设第一个为最值，放在参数中，在从下一个数以后找最值若后面有比前面假设的最值更大的就放在k中，然后在对k进行分析。若k部位最初的i值。也就是假设的i不是最值，那么就交换最值和当前序列的第一个数
测试代码：
void choise(int *a,int n)
{
int i,j,k,temp;
for(i=;i<n-;i++) /*外循环控制趟数，n个数选n-1趟*/
{
k=i; /*假设当前趟的第一个数为最值,记在k中 */
for(j=i+;j<n;j++) /*从下一个数到最后一个数之间找最值*/
if(a[k]>a[j]) /*若其后有比最值更大的*/
k=j; /*则将其下标记在k中*/ if(i!=k) /*若k不为最初的i值，说明在其后找到比其更大的数*/
{ /*则交换最值和当前序列的第一个数*/
temp=a[i];
a[i]=a[k];
a[k]=temp;
}
}
}
优点：稳定，比较次数与冒泡排序一样，数据移动次数比冒泡排序少；
缺点：相对之下还是慢。
三、插入排序
基本思想：将序列分为有序序列和无序列，依次从无序序列中取出元素值插入到有序序列的合适位置。初始是有序序列中只有第一个数，其余n-1个数组成无序序列，则n个数需进n-1次插入。寻找在有序序列中插入位置可以从有序序列的最后一个数往前找，在未找到插入点之前可以同时向后移动元素，为插入元素准备空间。
每趟从无序序列中取出第一个数插入到有序序列的合适位置，元素的最终位置在最后一趟插入后才能确定位置。也可是先用循环查找插入位置（可从前往后或从后往前），再将插入位置之后的元素（有序列中）逐个后移一个位置，最后完成插入。该算法的特点是在寻找插入位置的同时完成元素的移动。因为元素的移动必须从后往前，则可将两个操作结合在一起完成，提高算法效率。仍可进行升序或降序排序。
算法实现：假设待排序的元素有n个，对应的关键字分别是a1,a2,..an，因为第1个元素是有序的，所以从第2个元素开始，将a2与a1进行比较，如果a2<a1，则将a2插入到a1之前；否则，说明已经有序，不需要移动a2,这样有序的元素个数变为2.然后将a3与a1和a2进行比较，确定a3的位置。首先将a3与a2进行比较，如果a3>=a2,则说明a1 a2,a3已经是有序排序。如果a3<a2，则继续将a3与a1比较，如果a3<a1，则将a3插入到a1之前，否则，将a3插入到a1与a2之间，即完成了a1,a2,a3的排列。依次类推，直到最后一个关键字an插入到n-1个有序排列。
测试代码：
void insert(int *a,int n)
{
int i,j,temp; for(i=;i<;i++) /*外循环控制趟数，n个数从第2个数开始到最后共进行n-1次插入*/
{
temp=a[i]; /*将待插入数暂存于变量t中*/
for( j=i- ; j>= && temp<a[j] ; j-- ) /*在有序序列（下标0 ~ i-1）中寻找插入位置*/
a[j+]=a[j]; /*若未找到插入位置，则当前元素后移一个位置*/
a[j+]=temp; /*找到插入位置，完成插入*/
} }
优点：稳定，快；
缺点：比较次数不一定，比较次数越少，插入点后的数据移动越多，特别是当数据总量庞大的时候，但用链表可以解决这个问题。
四、快速排序
基本思想：
测试代码：
优点：极快，数据移动少；
缺点：不稳定。