今天没事又看了一遍算法书的排序一章,所以就顺便把书上讲的自己写了一下,当做练习。
程序里包括了四种排序算法,分别是:插入排序,希尔排序,归并排序,快速排序。
主函数想用哪一种,就把函数指针指向那个算法。
-
#include <stdio.h>
-
-
void insert_sort(int A[],int left,int right);
-
void shell_sort(int A[],int left,int right);
-
void merge_sort(int A[],int left,int right);
-
void quick_sort(int A[],int left,int right);
-
-
void out(int A[],int left,int right)
-
{
-
int i;
-
for(i=left;i<=right;i++) {
-
printf("%d ",A[i]);
-
}
-
printf("\n");
-
}
-
-
int main(int argc,char *argv[])
-
{
-
void (*sort)(int *,int,int);
-
-
int A[10] = {2,6,8,12,23,19,15,21,6,13};
-
-
// sort = insert_sort;
-
// sort = shell_sort;
-
// sort = merge_sort;
-
sort = quick_sort;
-
-
sort(A,0,9);
-
-
out(A,0,9);
-
return 0;
-
}
-
-
//insert_sort
-
void insert_sort(int A[],int left,int right)
-
{
-
int i,j;
-
int tmp;
-
-
for(i=left+1;i<=right;i++) {
-
-
tmp = A[i];
-
-
for(j=i;j>0&&A[j-1]>tmp;j--) {
-
A[j] = A[j-1];
-
}
-
A[j] = tmp;
-
}
-
}
-
-
//shell_sort
-
void shell_sort(int A[],int left,int right)
-
{
-
int i,j,increment;
-
int tmp;
-
int n = right - left + 1;
-
-
for(increment=n/2;increment>0;increment/=2) {
-
for(i=increment;i<n;i++) {
-
tmp = A[i];
-
for(j=i;j>=increment;j-=increment) {
-
if(tmp<A[j-increment])
-
A[j] = A[j-increment];
-
else
-
break;
-
}
-
A[j] = tmp;
-
}
-
}
-
}
-
-
//merge_sort
-
int A_tmp[10];
-
-
void merge(int A[],int left,int center,int right)
-
{
-
int i=left,j=center+1,k=left;
-
-
while(i<=center&&j<=right) {
-
if(A[i]<A[j]) {
-
A_tmp[k++] = A[i++];
-
}
-
else {
-
A_tmp[k++] = A[j++];
-
}
-
}
-
-
while(i<=center) {
-
A_tmp[k++] = A[i++];
-
}
-
-
while(j<=right) {
-
A_tmp[k++] = A[j++];
-
}
-
-
for(i=left;i<=right;i++) {
-
A[i] = A_tmp[i];
-
}
-
}
-
-
void merge_sort(int A[],int left,int right)
-
{
-
int center;
-
-
if(left<right) {
-
center = (left + right)/2;
-
merge_sort(A,left,center);
-
merge_sort(A,center+1,right);
-
merge(A,left,center,right);
-
}
-
}
-
-
//quick_sort
-
#define cutoff 3
-
void swap(int *a,int *b)
-
{
-
int tmp = *a;
-
*a = *b;
-
*b = tmp;
-
}
-
-
void quick_sort(int A[],int left,int right)
-
{
-
int i,j,pivot,center;
-
-
if(left+cutoff<=right) {
-
center = (left+right)/2;
-
pivot = A[center];
-
swap(&A[center],&A[right]);
-
-
j = left;
-
-
for(i=left;i<=right-1;i++) {
-
if(A[i]<=A[right]) {
-
swap(&A[i],&A[j++]);
-
}
-
}
-
swap(&A[j],&A[right]);
-
-
quick_sort(A,left,j-1);
-
quick_sort(A,j+1,right);
-
}
-
else
-
insert_sort(A,left,right);
-
}
阅读(471) | 评论(0) | 转发(0) |