以下所有示例和说明都以升序为例。
本文图示借用了：http://blog.csdn.net/bjyfb/article/details/7513509
一、插入排序
1.直接插入排序
图示：
代码：
#include<stdio.h>
int list[100];
void insertsort(int n) {
int i,j;
for(i=2; i<=n; i++) {
if(list[i] < list[i-1]) {
list[0] = list[i];
for(j=i-1; list[j]>list[0]; j--)
list[j+1] = list[j];
list[j+1] = list[0];
}
for(int p=1; p<=n; p++)
printf("%d ",list[p]);
printf("\n");
}
}
int main() {
int n;
scanf("%d",&n);
int i;
for(i=1; i<=n; i++) {
scanf("%d",&list[i]);
}
printf("排序过程：\n");
insertsort(n);
}
输出示例：
2.折半插入排序
代码：
#include<stdio.h>
int list[100];
void binsertsort(int n) {
int i,j,low,high,mid;
for(i=2; i<=n; i++) {
list[0] = list[i];
low = 1; high = i-1;
while(low <= high) {
mid = (low + high) / 2;
if(list[0] > list[mid])
low = mid + 1;
else
high = mid - 1;
}
for(j=i; j>low; j--)
list[j] = list[j-1];
list[low] = list[0];
for(j=1; j<=n; j++)
printf("%d ",list[j]);
printf("\n");
}
}
int main() {
int n;
scanf("%d",&n);
int i;
for(i=1; i<=n; i++)
scanf("%d",&list[i]);
printf("排序过程：\n");
binsertsort(n);
}
输出示例：
3.希尔排序
图示：
代码：
#include<stdio.h>
int list[100];
void shellsort(int n) {
int k = n / 2;
while(k > 0) {
int i,j;
for(i=k+1; i<=n; i++) { //此过程实际上为直接插入排序
if(list[i] < list[i-k]) {
list[0] = list[i];
for(j=i-k; j>0&&list[j]>list[0]; j=j-k) {
list[j+k] = list[j];
}
list[j+k] = list[0];
}
}
k = k / 2;
for(i=1; i<=n; i++)
printf("%d ",list[i]);
printf("\n");
}
}
int main() {
int n;
scanf("%d",&n);
int i;
for(i=1; i<=n; i++) {
scanf("%d",&list[i]);
}
printf("排序过程：\n");
shellsort(n);
}
输出示例：
二、选择排序
1、简单选择排序
图示：
代码：
#include<stdio.h>
#include<stdlib.h>
int L[500];
int SelectMinKey(int s,int n)
{
int min=L[s],k=s,i;
for(i=s+1;i<=n;i++)
if(L[i]<min)
{
min=L[i];
k=i;
}
return k;
}
void SelectSort(int n)
{
int i,j,t;
for(i=1;i<n;i++)
{
j=SelectMinKey(i,n);
if(i!=j)
{
t=L[i];L[i]=L[j];L[j]=t;
}
for(j=1;j<=n;j++)
printf("%d ",L[j]);
printf("\n");
}
}
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&L[i]);
printf("排序过程：\n");
SelectSort(n);
}
输出示例：
2、堆排序
图示：
代码：
#include<stdio.h>
int list[100];
void heapadjust(int s, int n)
{
list[0] = list[s];
for(int i=s*2; i<=n; i=i*2)
{
if(i<n && list[i+1]>list[i]) //找出两个孩子中大的一个的下标
i++;
if(list[0] >= list[i]) //若待插入结点比所有孩子都大，则不用再往下找了
break;
list[s] = list[i]; //父节点与大的孩子交换位置
s = i;
}
list[s] = list[0];
}
void heapsort(int n)
{
int i,j;
for(i=n/2; i>0; i--) //建立大顶堆
heapadjust(i,n);
printf("初始化后大顶堆：\n");
for(i=1; i<=n; i++)
printf("%d ",list[i]);
printf("\n");
printf("排序过程：\n");
for(i=n; i>1; i--){
//取出堆顶，为最大数
int temp = list[1];
list[1] = list[i];
list[i] = temp;
//重新调整剩下的i-1个数
heapadjust(1,i-1);
for(j=1; j<=n; j++)
printf("%d ",list[j]);
printf("\n");
}
}
int main()
{
int n;
scanf("%d",&n);
int i;
for(i=1; i<=n; i++)
scanf("%d",&list[i]);
heapsort(n);
}
输出示例：
三、交换排序
1、冒泡排序
图示：
代码：
#include<stdio.h>
int list[100];
void bubblesort(int n)
{
int i=1,j,lastchanged;//lastchanged用于减少遍历次数
while(i<n)
{
lastchanged = n;
for(j=n; j>i; j--)
{
if(list[j] < list[j-1])
{
int temp = list[j];
list[j] = list[j-1];
list[j-1] = temp;
lastchanged = j; //lastchanged记录最后一次交换的位置，它后面的数已有序，所以下次只需从这个位置开始遍历
}
}
i = lastchanged;
for(j=1; j<=n; j++)
printf("%d ", list[j]);
printf("\n");
}
}
int main()
{
int n;
scanf("%d",&n);
int i;
for(i=1; i<=n; i++)
scanf("%d",&list[i]);
printf("排序过程：\n");
bubblesort(n);
}
输出示例：
2、快速排序
图示：
代码：
#include<stdio.h>
#include<math.h>
int n;
int L[100];
int Partition(int low, int high) {
L[0] = L[low];
while(low < high) {
while(low < high && L[high] >= L[0])
high--;
L[low] = L[high];
while(low < high && L[low] < L[0])
low++;
L[high] = L[low];
}
L[low] = L[0];
for(int i=1; i<=n; i++)
printf("%d ",L[i]);
printf("\n");
return low;
}
void QSort(int low, int high) {
if(low >= high)
return;
int p = Partition(low, high);
QSort(low,p);
QSort(p+1,high);
}
int main() {
scanf("%d",&n);
for(int i=1; i<=n; i++)
scanf("%d",&L[i]);
printf("排序过程:\n");
QSort(1,n);
}
输出示例：
AFRDNOP.jpg)
3、归并排序
代码：
#include<stdio.h>
int n,L[100],t[100];
void mergepass(int s, int m, int r) {
int k=0;
int i,j;
for(i=s,j=m+1;i<=m && j<=r;k++) {
if(L[i] < L[j])
t[k] = L[i++];
else
t[k] = L[j++];
}
while(i<=m)
t[k++] = L[i++];
while(j<=r)
t[k++] = L[j++];
for(i=0; i<k; i++)
L[i+s] = t[i];
}
void mergesort() {
int s = 1;
int i = 0;
while(s < n) {
while(i+s*2-1<n) {
mergepass(i,i+s-1,i+s*2-1);
i = i + s * 2;
}
if(i + s < n)
mergepass(i,i+s-1,n-1);
s = s * 2;
i = 0;
for(int j=0;j<n;j++)
printf("%d ",L[j]);
printf("\n");
}
}
int main() {
scanf("%d",&n);
int i;
for(i=0; i<n; i++)
scanf("%d",&L[i]);
printf("排序过程:\n");
mergesort();
}
输出示例：
四、各种排序总结比较：
