计科一二班数据结构《实验十报告》参考答案

/*--------------------------------------------------------------------
代码功能：                                                             *
                                       *
   1.简单插入排序算法                            *
   2.希尔排序算法                              *
   3.冒泡排序算法                              *
   4.冒泡排序的改进算法                           *
   5.快速排序                                                         *
 --------------------------------------------------------------------- 
作者:令狐荣豪
时间：2019/6/5
----------------------------------------------------------------------*/
#include<stdio.h>
/*--------------------------------------------------------------------*/
/*====================================================================
函数功能：简单插入排序
函数接口：数组和长度
======================================================================*/
void Insertion_Sort(int a[],int n)
{
  int i, j, get;
  for (i = 1; i < n; i++)
  {
    get = a[i];
    for (j = i - 1; j >= 0 && a[j] > get; j--)
    {
      a[j + 1] = a[j];
    }
    a[j + 1] = get;
  }
}
/*===============================================================
函数功能：希尔排序
函数接口：数组和长度
=================================================================*/
void ShellSort(int a[],int n)
{
  int d, i, j,get;
  for (d = n / 2; d >= 1; d = d / 2)
  {
    for (i = d; i <n; i++)
    {
      get = a[i];
      for (j = i - d; j >= 0 && a[j] > get; j -= d)
        a[j + d] = a[j];
    }
    a[j + d] = get;
  }
}
/*===============================================================
函数功能：冒泡排序
函数接口：数组和长度
=================================================================*/
void Bubble(int a[], int len)
{
  int i, j, temp;
  for (i = 0; i < len - 1; i++)
  {
    for (j = len - 1; j > i; j--)
      if (a[j] < a[j - 1])
      {
        temp = a[j - 1];
        a[j - 1] = a[j];
        a[j] = temp;
      }
  }
}
/*===============================================================
函数功能：改进版冒泡
函数接口：数组和长度
=================================================================*/
void Bubble_Sort(int a[], int sz)
{
  int i, j;
  int flag = 1;  //添加标志位
  for (i = 0; i < sz - 1; i++)  //控制比较的趟数
  {
    flag = 1;
    for (j = 0; j < sz - 1 - i; j++)  //控制每趟比较的次数
    {
      if (a[j] > a[j + 1])  //升序排列
      {
        int tmp = a[j];
        a[j] = a[j + 1];
        a[j + 1] = tmp;
        flag = 0;
      }
    }
    if (flag == 1) break;
  }
}
/*===============================================================
函数功能：Swap函数
函数接口：交换数值
=================================================================*/
void Swap(int *a, int *b)
{
  int temp;
  temp = *a;
  *a = *b;
  *b = temp;
  return;
}
/*===============================================================
函数功能：快速排序
函数接口：数组，长度，起始点，终点
================================================================*/
void Quick_Sort(int array[], int maxlen, int begin, int end)
{
  int i, j;
  if (begin < end)
  {
    i = begin + 1;  // 将array[begin]作为基准数，因此从array[begin+1]开始与基准数比较！
    j = end;        // array[end]是数组的最后一位
    while (i < j)
    {
      if (array[i] > array[begin])  // 如果比较的数组元素大于基准数，则交换位置。
      {
        Swap(&array[i], &array[j]);  // 交换两个数
        j--;
      }
      else
      {
        i++;  // 将数组向后移一位，继续与基准数比较。
      }
    }
    if (array[i] >= array[begin])  // 这里必须要取等“>=”，否则数组元素由相同的值时，会出现错误！
    {
      i--;
    }
    Swap(&array[begin], &array[i]);  // 交换array[i]与array[begin]
    Quick_Sort(array, maxlen, begin, i);
    Quick_Sort(array, maxlen, j, end);
  }
}
/*====================================================================*/
/*====================================================================*/
/*====================================================================*/
int main()
{
  int i, n, a[100];
  printf("请输入元素个数:\n");
  scanf("%d", &n);
  printf("\n请输入待排序的元素，空格分隔:\n");
  for (i = 0; i < n; i++)
    scanf("%d", &a[i]);
  printf("排序后:\n");
/*--------------------------------------------------------------------*/
  Insertion_Sort(a, n);
  for (i = 0; i < n; i++)
    printf("%d", a[i]);
  printf("\n");
/*--------------------------------------------------------------------*/
  ShellSort(a, n);
  for (i = 0; i < n; i++)
    printf("%d", a[i]);
  printf("\n");
/*--------------------------------------------------------------------*/
  Bubble(a, n);
  for (i = 0; i < n; i++)
    printf("%d", a[i]);
  printf("\n");
/*--------------------------------------------------------------------*/
  Bubble_Sort(a, n);
  for (i = 0; i < n; i++)
    printf("%d", a[i]);
  printf("\n");
/*--------------------------------------------------------------------*/
  Quick_Sort(a, n, 0, n-1);
  for (i = 0; i < n; i++)
    printf("%d", a[i]);
  printf("\n");
/*--------------------------------------------------------------------*/
  return 0;
}