数据结构实验四排序南京邮电大学

### 南京邮电大学 数据结构 实验四 排序 算法 实验报告 示例

#### 实验目的
理解并掌握多种排序算法的工作原理及其C语言实现方法，包括但不限于快速排序、冒泡排序、插入排序等。通过编程实践加深对不同排序算法的时间复杂度和空间复杂度的理解。

#### 实验内容概述
本次实验旨在让学生熟悉几种常见的内部排序算法，并能够编写相应的程序来验证这些算法的有效性和效率。学生需完成至少两种不同的排序算法的编码工作，并对比分析其性能差异。

#### 问题描述
给定一组随机整数序列作为输入数据集，分别采用选定的排序算法对其进行升序排列处理。记录每种算法执行前后数组的状态变化情况以及所耗费时间开销。

#### 算法说明
以下是部分常用排序算法简介：

- **快速排序 (Quick Sort)**
快速排序是一种基于分治策略的高效排序算法。它选取一个基准元素，将待排序列划分为两部分——小于等于基准值的部分位于左侧，大于基准值的部分置于右侧，之后递归地对这两部分继续施行相同的操作直到整个列表有序[^1]。

  void quickSort(int arr[], int low, int high) {
      if (low < high) {
          /* pi is partitioning index */
          int pi = partition(arr, low, high);
          
          // Recursively sort elements before and after partition
          quickSort(arr, low, pi - 1);
          quickSort(arr, pi + 1, high);
      }
  }

  int partition(int arr[], int low, int high) {
      int pivot = arr[high];    // Pivot element from the end of array.
      int i = (low - 1);        // Index of smaller element.

      for (int j = low; j <= high - 1; j++) {
          // If current element is smaller than or equal to pivot
          if (arr[j] <= pivot) {
              i++;                  // Increment index of smaller element
              swap(&arr[i], &arr[j]);
          }
      }
      swap(&arr[i + 1], &arr[high]);
      return (i + 1);
  }

  void swap(int* a, int* b) {
      int t = *a;
      *a = *b;
      *b = t;
  }

- **冒泡排序 (Bubble Sort)**
冒泡排序是最简单的交换类排序方法之一。该算法重复遍历要排序的数值列表，在每次遍历时依次比较相邻两个元素大小关系，如果前者大于后者则互换位置，如此这般直至没有任何一对数字需要交换为止，则表示已完成全部排序过程.

  void bubbleSort(int arr[], int n) {
      int i, j;
      bool swapped;
      for (i = 0; i < n - 1; i++) {
          swapped = false;
          for (j = 0; j < n - i - 1; j++) {
              if (arr[j] > arr[j + 1]) {
                  swap(&arr[j], &arr[j + 1]);
                  swapped = true;
              }
          }
          // IF no two elements were swapped by inner loop, then break
          if (!swapped)
              break;
      }
  }

#### 实验代码示例
针对上述提到的不同类型的排序算法，可以构建测试函数来进行实际效果展示。这里提供了一个完整的框架用于加载初始数据、调用指定排序逻辑并对最终结果进行输出显示。

#include <stdio.h>
#include <stdlib.h>

// ... 上述定义过的quickSort(), bubbleSort() 和其他辅助函数 ...

void loadDataFromFile(const char* filename, int data[], int maxSize, int* sizePtr);

int main(void){
    const char FILENAME[] = "input.txt";
    int testData[MAX_SIZE];
    int dataSize;

    printf("Loading test data...\n");
    loadDataFromFile(FILENAME, testData, MAX_SIZE, &dataSize);

    printf("\nOriginal Data:\n");
    printArray(testData, dataSize);

    clock_t start, end;
    double cpu_time_used;

    // Choose sorting algorithm here...
    start = clock();
    quickSort(testData, 0, dataSize - 1);
    end = clock();

    cpu_time_used = ((double)(end-start)) / CLOCKS_PER_SEC;
    
    printf("\nSorted Data using Quick Sort Algorithm:\n");
    printArray(testData, dataSize);
    printf("Time taken: %f seconds\n", cpu_time_used);

    return EXIT_SUCCESS;
}

#### 程序运行示例
当一切准备就绪后，编译并运行这段代码将会读取名为`input.txt`的数据文件中的原始数据，应用所选排序算法（此处为快速排序），最后打印出排序后的结果连同耗时信息一起呈现出来。

对于可能出现的人为制造错误信息的情况，可以在代码中加入异常检测机制，比如检查输入参数合法性、防止越界访问等问题的发生。