一、希尔排序
基本有序
#include <stdio.h>
void InsertSort(int k[],int n)
{
int i,j,temp;
int gap = n;
do
{
gap = gap/3+1;
for(i=gap;i<n;i++)
{
if(k[i]<k[i-gap])
{
temp = k[i];
for(j=i-gap;k[j]>temp;j-=gap)
{
k[j+gap] = k[j];
}
k[j+gap] = temp;
}
}
}while(gap>1);
}
int main()
{
int i,a[10]= {5,2,6,0,3,9,1,7,4,8};
InsertSort(a,10);
printf("排序后的结果是：\n");
for(i=0;i<10;i++)
{
printf("%d\t",a[i]);
}
printf("\n\n");
return 0;
}二、堆排序
根结点一定是堆中所有结点最大或者最小者，如果按照层序遍历的方式给结点从1开始编号，则结点之间满足如下关系：
Ki>=K2i , Ki>=K2i+1 或 Ki< = K2i Ki<= K2i+1 ( i< = i<=[n/2])
. 下标i 与 2i 和2i+1 是双亲和子女关系
. 那么把大顶堆和小顶堆用层序遍历存入数组，则一定满足上面的表达式。
堆排序（Heap Sort）就是利用堆进行排序的算法，它的基本思想是：
——将待排序的序列构造成一个大顶堆（或小顶堆）。
——此时，整个序列的最大值就是堆顶的根结点。将它移走（就是将其与堆数组的末尾元素交换，此时末尾元素就是最大值）。
——然后将剩余的n-1个序列重新构造成一个堆，这样就会得到n个元素中的次大值。
——如此反复执行，便能得到一个有序序列。
#include <stdio.h>
void swap(int k[],int i,int j)
{
int temp;
temp = k[i];
k[i] = k[j];
k[j] = temp;
}
void HeapAdjust(int k[],int s,int n)
{
int i,temp;
temp = k[s];
for(i=2*s;i<=n;i*=2)
{
if(i < n && k[i] < k[i+1])
{
i++;
}
if(temp >= k[i])
{
break;
}
k[s] = k[i];
s = i;
}
k[s] = temp;
}
void HeapSort(int k[], int n)
{
int i;
for(i = n/2;i>0;i--)
{
HeapAdjust(k,i,n);
}
for(i= n;i>1;i--)
{
swap(k,1,i);
HeapAdjust(k,1,i-1);
}
}
int main()
{
int i,a[10]= {5,2,6,0,3,9,1,7,4,8};
HeapSort(a,10);
printf("排序后的结果是：\n");
for(i=0;i<10;i++)
{
printf("%d\t",a[i]);
}
printf("\n\n");
return 0;
}三、归并排序
归并排序（Merge Sort）就是利用归并的思想实现的排序方法。它的原理是假设初始序列有n个记录，则可以看成是n个记录，则可以看成n个有序的子序列，每个子序列的长度为1，然后两两归并，得到n/2个长度为2或1的有序子序列；依次往复。
#include <stdio.h>
#define MAXSIZE 10
void merging(int *list1,int list1_size, int *list2,int list2_size)
{
int j,k,i;
int temp[MAXSIZE];
i = j = k = 0;
while( i< list1_size && j < list2_size)
{
if(list1[i]<list2[j])
{
temp[k++] = list1[i++];
}
else
{
temp[k++] = list2[j++];
}
}
while(i < list1_size)
{
temp[k++] = list1[i++];
}
while(j < list2_size)
{
temp[k++] = list2[j++];
}
for(int m =0;m < (list1_size + list2_size);m++)
{
list1[m] = temp[m];
}
}
void MergeSort(int k[],int n)
{
if(n>1)
{
int *list1 = k;
int list1_size = n/2;
int *list2 = k + n/2;
int list2_size = n - list1_size;
MergeSort(list1,list1_size);
MergeSort(list2,list2_size);
merging(list1,list1_size,list2,list2_size);
}
}
int main()
{
int i,a[10]={5,2,6,0,3,9,1,7,4,8};
MergeSort(a,10);
printf("排序后的结果：\n");
for(i=0;i<10;i++)
{
printf("%d\t",a[i]);
}
printf("\n\n");
return 0;
}三、快速排序
#include <stdio.h>
void swap(int k[],int low,int high)
{
int temp;
temp = k[low];
k[low] = k[high];
k[high] = temp;
}
int Partition(int k[],int low,int high)
{
int point;
point = k[low];
while(low < high)
{
while(low < high && k[high] >= point)
{
high--;
}
while(low < high && k[low] <= point)
{
low++;
}
}
}
void Qsort(int k[],int low,int high)
{
int point;
if(low < high)
{
point = Partition(k,low,high);
Qsort(k,low,point - 1);
Qsort(k,point+1,high);
}
}
void QuickSort(int k[],int n)
{
Qsort(k,0,n-1);
}
int main()
{
int i,a[10] = {5,2,6,8,3,9,1,7,4,8};\
QuickSort(a,10);
printf("排序后的结果：");
for(i=0;i<10;i++)
{
printf("%d",a[i]);
}
printf("\n\n");
return 0;
}
