//插入排序、冒泡排序、選擇排序、快速排序、堆排序、歸并排序
#include"stdio.h"
#include"stdlib.h"
#include"time.h"
#define M 1000
int shu[M]; //存放要排序的數組
int chang; //存放要排序的數組的長度
//-------------------------顯示輸出----------------------------
void show()
{
printf("\n排序後的數為:\n");
for (int i=1; i<=chang; i++)
printf("%d ", shu[i]);
printf("\n\n排序結束!\n");
}
//--------------------------插入排序-----------------------------
void cha_ru()
{
for (int i=2, j; i<=chang; i++)
if(shu[i] < shu[i-1])
{
shu[0] = shu[i]; //将待查找的數放入監視哨裡面
j = i - 1;
while(shu[0] < shu[j]) //尋找插入位置
{
shu[j+1] = shu[j];
j--;
}
shu[j+1] = shu[0]; //将元素插入
}
}
//--------------------------冒泡排序---------------------------
void mao_pao()
{
int change = 1; //标記一輪周遊後是否有元素進行交換
for (int i=1; i<=chang && change; i++)
{
change = 0;
for (int j=1; j<=chang-i; j++)
if(shu[j] > shu[j+1])
{
shu[0] = shu[j];
shu[j] = shu[j+1];
shu[j+1] = shu[0];
change = 1;
}
}
}
//--------------------------選擇排序----------------------------
void xuan_ze()
{
int min; //每次測試時最小的變量的代号
int temp;
for (int i=1; i<=chang; i++)
{
min = i; //shu[min]記錄最小的shu[i]
for (int j=i+1; j<=chang; j++)
if(shu[j] < shu[min])
min = j; //修改min
if(min != i) //若min!=i 則将shu[min]與shu[i]進行交換
{
temp = shu[min];
shu[min] = shu[i];
shu[i] = temp;
}
}
}
//--------------------------快速排序------------------------------
int kuaisu_pass(int low, int high)//快速排序過程
{
int x = shu[low];
while(low < high)
{
while(low<high && shu[high]>=x) //high從右到左找小于x的記錄
high--;
if(low < high) //找到小于x的記錄進行交換
{
shu[low] = shu[high];
low++;
}
while(low<high && shu[low]<=x) //low從左到右找大于x的記錄
low++;
if(low < high) //找到大于x的記錄進行交換
{
shu[high] = shu[low];
high--;
}
}
shu[low] = x;
return low;
}
void kuai_su(int low, int high) //快速排序主函數
{
int pos;
if(low < high)
{
pos = kuaisu_pass(low, high);
kuai_su(low,pos-1);
kuai_su(pos+1,high);
}
}
//----------------------------堆排序------------------------------
void chong_jian_dui(int k, int m) //重建堆
{
int x = shu[k]; //暫存“根”記錄
int i = k;
int j = 2 * k;
int finished = 0;
while (j<=m && !finished)
{
if(j<m && shu[j]<shu[j+1]) //若存在右子樹,且右子樹根的關鍵字大,則延右分支“篩選"
j = j + 1;
if(x > shu[j]) //篩選完畢
finished = 1;
else
{
shu[i] = shu[j];
i = j;
j = 2 * i;
}
}
shu[i] = x; //将shu[k]填到恰當的位置
}
void jian_dui() //建堆
{
int n = chang;
for (int i=n/2; i>=1; i--) //自第【n/2】個記錄開始進行篩選建堆
chong_jian_dui(i,n);
}
void dui() //堆排序主函數
{
int n = chang; //将要排序的數存儲到N中
int temp;
jian_dui(); //将堆建立
for (int i=n; i>=2; i--) //将堆頂記錄和堆中的最後一個記錄交換
{
temp = shu[1];
shu[1] = shu[i];
shu[i] = temp;
chong_jian_dui(1,i-1); //進行調整,使得shu[1]到shu[i-1]變成堆
}
}
//--------------------------歸并排序-------------------------------
void gui_bing_way(int temp1[], int temp2[], int begin, int half, int end)//二路歸并過程
{
for (int j=half+1,k=begin; begin<=half && j<=end; k++)
{ //将temp2[]中的記錄由小到大地并入temp1[]中
if (temp2[begin] < temp2[j])
temp1[k] = temp2[begin++];
else
temp1[k] = temp2[j++];
}
for(; begin<=half;begin++, k++) //将剩餘的temp2[begin...half]複制到到temp1[]中
temp1[k] = temp2[begin];
for(; j<=end; j++, k++) //将剩餘的temp2[j....end]複制到temp1[]中
temp1[k] = temp2[j];
}
void gui_bing(int temp1[],int temp2[],int begin, int end) //歸并排序
{
int half;
if(begin == end)
temp2[begin] = temp1[begin];
else
{
half = (begin + end) / 2; //将temp2[begin...end]平分為temp2[begin...half]和temp2[half+1....end]
gui_bing(temp1,temp2,begin,half); //遞歸将temp2[begin...half] 歸并
gui_bing(temp1,temp2,half+1,end); //遞歸将temp2[half+1...end] 歸并
gui_bing_way(temp1,temp2,begin,half,end); //将temp2[begin..half]和temp2[half+1..end]歸并到temp1[begin..end]中
}
for (int i=1; i<=chang; i++) //将歸并後的數存入temp2[]中
temp2[i] = temp1[i];
}
//------------------------------主函數-----------------------------
int main()
{
int temp_shu[M];
int choise; //排序方式的選擇
int temp = 1;
printf("請輸入要排序的随機數的個數:");
scanf("%d", &chang);
srand((unsigned)time(NULL));
for (int i=1; i<=chang; i++)
shu[i] = rand()%1000;
printf("随即數的初始狀态為:\n");
for (i=1; i<=chang; i++) //将随機數存儲到temp_shu[]中,并顯示
{
temp_shu[i] = shu[i];
printf("%d ", shu[i]);
}
printf("\n\n請選擇要排序的方式:\n1.插入排序\n2.冒泡排序\n3.選擇排序\n4.快速排序\n5.堆排序\n6.歸并排序\n請選擇:");
scanf("%d", &choise);
while(temp)
{
switch(choise)
{
case 1: //插入排序
cha_ru();
temp = 0;
break;
case 2: //冒泡排序
mao_pao();
temp = 0;
break;
case 3: //選擇排序
xuan_ze();
temp = 0;
break;
case 4: //快速排序
kuai_su(1,chang);
temp = 0;
break;
case 5: //堆排序
dui();
temp = 0;
break;
case 6: //歸并排序
gui_bing(shu,temp_shu,1,chang);
temp = 0;
break;
default: //其他錯誤輸入
printf("輸入錯誤,請重新輸入!\n");
printf("\n請選擇要排序的方式:\n1.插入排序\n2.冒泡排序\n3.選擇排序\n4.快速排序\n5.堆排序\n6.歸并排序\n");
scanf("%d", &choise);
break;
}
}
show(); //顯示輸出
return 0;
}
歡迎大家轉載,如有轉載請注明文章來自: http://blog.csdn.net/q345852047