冒泡排序:
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
void swap(int *a,int i,int j)
{
int temp = a[i];
a[i] = a[j];
a[j] = temp;
};
void BubbleSort(int *a, int n)
{
int i,j;
bool flag = true;
for(i=0;i<n-1&&flag;i++)
{
flag = false;
for(j=n-2;j>=i;j--)
{
if(a[j]>a[j+1])
{
swap(a,j,j+1);
flag = true;
}
}
}
};
int main()
{
int i = 0;
int a[13] = {5,4,9,8,7,6,3,0,1,2,15,24,100};
BubbleSort(a,13);
for(;i<13;i++)
{
printf("%d ",a[i]);
}
printf("\n");
system("pause");
return 0;
}
簡單選擇排序:
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
void swap(int *a,int i,int j)
{
int temp = a[i];
a[i] = a[j];
a[j] = temp;
};
void SelectSort(int *a, int n)
{
int i,j;
int min;
for(i=0;i<n-1;i++)
{
min = i;
for(j=i+1;j<n;j++)
{
if(a[j] < a[min])
{
min = j;
}
}
if(min != i)
{
swap(a,i,min);
}
}
};
int main()
{
int i = 0;
int a[13] = {5,4,9,8,7,6,3,0,1,2,15,24,100};
SelectSort(a,13);
for(;i<13;i++)
{
printf("%d ",a[i]);
}
printf("\n");
system("pause");
return 0;
}
直接插入排序：
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
void swap(int *a,int i,int j)
{
int temp = a[i];
a[i] = a[j];
a[j] = temp;
};
void InsertSort(int *a, int n)
{
int i,j;
int temp;
for(i=1;i<n;i++)
{
if(a[i]<a[i-1])
{
temp = a[i];
for(j=i-1;a[j]>temp&&j>=0;j--)
{
a[j+1] = a[j];
}
a[j+1] = temp;
}
}
};
int main()
{
int i = 0;
int a[13] = {5,4,9,8,7,6,3,0,1,2,15,24,100};
InsertSort(a,13);
for(;i<13;i++)
{
printf("%d ",a[i]);
}
printf("\n");
system("pause");
return 0;
}
希爾排序不穩定）：
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
void swap(int *a,int i,int j)
{
int temp = a[i];
a[i] = a[j];
a[j] = temp;
};
void ShellSort(int *a, int n)
{
int i,j;
int increment = n-1;
int temp;
do
{
increment = increment/3 +1;
for(i=increment;i<n;i++)
{
if(a[i] < a[i-increment])
{
temp = a[i];
for(j=i-increment;j>=0&&a[j]>temp;j-=increment)
{
a[j+increment] = a[j];
}
a[j+increment] = temp;
}
}
}while(increment>1);
};
int main()
{
int i = 0;
int a[13] = {5,4,9,8,7,6,3,0,1,2,15,24,100};
ShellSort(a,13);
printf("\n");
system("pause");
return 0;
}
堆排序：不穩定）
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
//調整最大堆
void AdjustHeap(int *a,int s,int m)
{
int temp = a[s];
int i;
for(i=2*s+1;i<=m;i=i*2+1)
{
if(i<m&&a[i]<a[i+1])
{
i++;
}
if(temp>=a[i])
{
break;
}
else
{
a[s] = a[i];
s = i;
}
}
a[s] = temp;
}
void HeapSort(int *a, int n)
{
//首先將待排序的數組構成最大堆
int i,j;
for(i=(n-2)/2;i>=0;i--)
{
AdjustHeap(a,i,n-1);
}
//交換首尾數字，重新調整堆
for(i=n-1;i>0;i--)
{
swap(a,0,i);
AdjustHeap(a,0,i-1);
}
};
int main()
{
int i = 0;
int a[13] = {5,4,9,8,7,6,3,0,1,2,15,24,100};
HeapSort(a,13);
for(;i<13;i++)
{
printf("%d ",a[i]);
}
printf("\n");
system("pause");
return 0;
}
歸並排序遞歸實現）
//歸並數組
void Merge(int *a,int s,int m, int h)
{
int i,j,t;
i = s;
j = m+1;
int temp[100];
t = i;
for(;i<=m && j<=h;t++)
{
if(a[i]<a[j])
{
temp[t] = a[i];
i++;
}
else
{
temp[t] = a[j];
j++;
}
}
if(i<=m)
{
for(;i<=m;i++)
{
temp[t] = a[i];
t++;
}
}
if(j<=h)
{
for(;j<=h;j++)
{
temp[t] = a[j];
t++;
}
}
//最後將排好序的數組復制回原數組
for(i=s;i<=h;i++)
{
a[i] = temp[i];
}
}
void MergeSort(int *a, int s,int h)
{
if(s == h)
return;
else
{
int m = (s+h)/2;
MergeSort(a,s,m);
MergeSort(a,m+1,h);
Merge(a,s,m,h);
}
};
int main()
{
int i = 0;
int a[13] = {5,4,9,8,7,6,3,0,1,2,15,24,100};
MergeSort(a,0,12);
for(;i<13;i++)
{
printf("%d ",a[i]);
}
printf("\n");
system("pause");
return 0;
}
歸並排序非遞歸實現）:
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <malloc.h>
void swap(int *a,int i,int j)
{
int temp = a[i];
a[i] = a[j];
a[j] = temp;
};
//將a[] 中 間隔為k的序列歸並
void MergePass(int *a,int k,int n)
{
int i,j;
i = 0;
while(i+2*k-1<n)
{
Merge(a,i,i+k-1,i+2*k-1);
i = i+2*k;
}
if(i+k-1<n-1) //剩余一個半
{
Merge(a,i,i+k-1,n-1);
}
else //剩余一個或半個
{
for(j=i;j<n;j++)
{
a[j] = a[j];
}
}
}
//非遞歸實現
void MergeSort(int *a, int n)
{
int k = 1;
while(k<n){
MergePass(a,k,n);
k = k*2;
}
};
int main()
{
int i = 0;
int a[14] = {5,4,9,8,7,6,3,0,1,2,15,24,100,21};
MergeSort(a,14);
for(;i<14;i++)
{
printf("%d ",a[i]);
}
printf("\n");
system("pause");
return 0;
}
快速排序：不穩定）
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <malloc.h>
//三數取中法
int Partition(int *a,int low,int high)
{
int i,j;
int pivotKey;
int m = (low+high)/2;
if(a[low] > a[high])
{
swap(a,low,high);
}
if(a[m] > a[high])
{
swap(a,m,high);
}
if(a[low] < a[m])
{
swap(a,low,m);
}
//經過上面反復交換，第一個數字成為了三個數字鐘的中間數字
pivotKey = a[low];
while(low < high)
{
while(low<high && a[high]>pivotKey)
high--;
a[low] = a[high];
while(low<high && a[low]<pivotKey)
low++;
a[high] = a[low];
}
a[low] = pivotKey;
return low;
}
void QuickSort(int *a, int low, int high)
{
int pivot;
if(low < high)
{
pivot = Partition(a,low,high);
QuickSort(a,low,pivot-1);
QuickSort(a,pivot+1,high);
}
};
int main()
{
int i = 0;
int a[14] = {5,4,9,8,7,6,3,0,1,2,15,24,100,21};
QuickSort(a,0,13);
for(;i<14;i++)
{
printf("%d ",a[i]);
}
printf("\n");
system("pause");
return 0;
}本文出自 “年少輕狂” 博客，請務必保留此出處http://shpshao.blog.51cto.com/1931202/1297449
