几种常见的排序-数据结构课程设计|数据结构课程设计
/*Name:排序Author:wujilinDescription:几种常见的排序方法Date: 19-07-06 15:41Copyright:wujilin*/
#include
#include#define M 11
void InsertSort(int a[])//插入排序{int i, j;
for (i = 2; i < M; i++){if(a[i] < a[i-1]){a[0] = a[i];a[i] = a[i-1];for (j = i - 2; j > 0 && a[j] > a[0]; j--){a[j+1] = a[j];}a[j+1] = a[0];}}
printf("进行插入排序:");for ( i = 1 ; i < M; i++){printf("%4d",a[i]);}printf("\n");}
void BinarySort(int a[])//折半排序{int i, j, m, low, high;
for (i = 2; i < M; i++){a[0] = a[i];low = 1;high = i - 1;
while (low <= high){m = (low + high)/2;if (a[0] > a[m]){low = m + 1;}else{high = m - 1;}}for ( j = i - 1; j > high ; j--){a[j+1] = a[j];}a[j+1] = a[0];}
printf("进行折半排序:");for (i = 1; i < M ; i++){printf("%4d",a[i]);}printf("\n");}
void Bubble(int a[])//冒泡排序{int i, j, temp;int flag = 1;
for ( i = 1; i < 10; i++){flag = 0;for (j = i + 1; j <= 10; j++){if (a[i] > a[j]){temp = a[i];a[i] = a[j];a[j] = temp;flag = 1;}}}
printf("进行起泡排序:");for ( i = 1; i <= 10; i++){printf("%4d", a[i]);}printf("\n");}
void HeapSort(int a[])//堆排序{int i;
for (i = (M-1)/2; i > 0 ; i--){HeapAdjust(a, i, M-1);}for (i = M - 1 ; i > 0 ; ){a[0] = a[i];a[i] = a[1];a[1] = a[0];i--;HeapAdjust(a, 1, i);}printf("进行堆排序:");for ( i = 1; i < M ; i++){printf("%4d", a[i]);}printf("\n");}
int HeapAdjust(int a[], int i, int n){int j, k;int flag = 1;
j = 2 * i;k = a[i];while (j <= n && flag == 1){if (j < n && a[j] < a[j+1]){j++;}if (k >= a[j]){flag = 0;}else{a[j/2] = a[j];j *= 2;}}a[j/2] = k;
return 0;}
void ShellSort(int a[])//希尔排序{int k, i, j, temp;
k = M-1/2;for (; k > 0; k--){for (i = k + 1; i <= 10; i++){j = i - k;while (j > 0){if (a[j] > a[i]){temp = a[j];a[j] = a[i];a[i] = temp;}j = j - k;}}}
printf("进行希尔排序:");for ( i = 1; i < M; i++){printf("%4d",a[i]);}printf("\n");}
void MergeSort(int a[], int b[])//归并排序{int i = 1, j = 1, k = 0;int n, c[30];
Bubble(a);Bubble(b);
while (i < M && j < M)//这里循环语句要写清楚 一个if 对应一个else 否则编译器会搞晕 会出错{if (a[i] < b[j]){c[k++] = a[i++];}else if (a[i] > b[j]){c[k++] = b[j++];}else{c[k++] = a[i++];}}while (i < M){c[k++] = a[i++];}while (j < M){c[k++] = b[j++];}
n = k;
printf("进行归并排序:");for ( i = 0; i < n; i++){printf("%4d",c[i]);}printf("\n");}
int main(void){int a[M] = {0, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0};int b[M] = {0, 3, 11, 34, 13, 10, 19, 15, 14, 16, 18};int select, i;
printf("排序之前的元素为");for ( i = 1; i < M; i++){printf("%4d",a[i]);}printf("\n");printf("1: 进行插入排序\n");printf("2: 进行折半排序\n");printf("3: 进行冒泡排序\n");printf("4: 进行堆排序\n");printf("5: 进行希尔排序\n");printf("6: 进行归并排序\n");printf("请选择:");scanf("%d",&select);
switch(select){case 1:InsertSort(a);break;case 2:BinarySort(a);break;case 3:Bubble(a);break;case 4:HeapSort(a);break;case 5:ShellSort(a);break;case 6:MergeSort(a, b);break;default:break;}
system("pause");return 0;}Trackback: http://tb.blog.csdn.net/TrackBack.aspx?PostId=965288
