南京師范大學計電院數據結構課設—

1?排序算法

1.1 題目要求

編程實現希爾、快速、堆排序、歸并排序算法。要求首先隨機產生10000個數據存入磁盤文件，然后讀入數據文件，分別采用不同的排序方法進行排序并將結果存入文件中。

1.2 算法思想描述

1.2.1?隨機數生成

當需要生成一系列隨機數時，常常需要使用隨機函數。然而，傳統的rand()函數所生成的數據并不能被視為真正的隨機數，因其僅限于某個特定范圍內的值，并且在多次運行同一rand()函數時，所產生的隨機數序列是完全一致的，缺乏真正的隨機性。為此，我們需要借助srand()函數來設置rand()函數生成隨機數時的種子值，通過不同的種子值，我們可以獲得不同的隨機數序列。

為了實現更接近真正隨機數的序列生成，一種常見的做法是利用srand((int)time(NULL))的方式，即利用系統時鐘來產生隨機數種子。該方法將當前時間轉換為一個整數，并將其作為srand()函數的參數，以初始化隨機數生成器的種子值。由于時間的變化是無法預測的，因此每次程序運行時都會獲得一個不同的種子值，從而產生不同的隨機數序列。

圖1.1 隨機生成數示例代碼

1.2.2?希爾排序

希爾排序（Shell Sort）是一種基于插入排序的排序算法，它通過將待排序的元素按照一定的間隔分組，對每組進行插入排序，隨著間隔逐漸減小，最終使得整個序列達到有序狀態。

下面是希爾排序的基本思想和實現步驟：

選擇一個間隔序列（稱為增量序列），通常初始間隔為數組長度的一半，然后逐步縮小間隔直到為1。
對于每個間隔，將數組分成多個子序列，子序列的元素之間相隔間隔個位置。
對每個子序列進行插入排序，即將子序列中的元素按照插入排序的方式進行排序。
重復步驟2和步驟3，直到間隔為1時，進行最后一次插入排序。

圖1.2 希爾排序示例代碼

1.2.3?快速排序

快速排序（Quick Sort）是一種高效的排序算法，它采用分治法（Divide and Conquer）策略來排序一個數組。快速排序的基本思想是選擇一個基準元素（pivot），將數組分割成兩個子數組，其中一個子數組的元素都比基準元素小，另一個子數組的元素都比基準元素大，然后對這兩個子數組分別進行遞歸排序，最終將整個數組排序完成。

圖1.3 快速排序示例代碼

1.2.4?堆排序

堆排序（Heap Sort）是一種利用堆數據結構進行排序的算法。堆是一種完全二叉樹，具有以下性質：對于每個節點i，其父節點的值小于等于節點i的值（最大堆），或者父節點的值大于等于節點i的值（最小堆）。在堆排序中，我們使用最大堆來進行排序。

下面是堆排序的基本思想和實現步驟：

把無序數組構建成二叉堆。
循環刪除堆頂元素，移到集合尾部，調節堆產生新的堆頂。
當刪除一個最大堆的堆頂（并不是完全刪除，而是替換到最后面），經過自我調節，第二大的元素就會被交換上來，成為最大堆的新堆頂。由于這個特性，我們每一次刪除舊堆頂，調整后的新堆頂都是大小僅次于舊堆頂的節點。那么我們只要反復刪除堆頂，反復調節二叉堆，所得到的集合就成為了一個有序集合。

圖1.4 堆排序示例代碼

1.2.5?歸并排序

歸并排序（Merge Sort）是一種基于分治法（Divide and Conquer）的排序算法，它將待排序的數組逐步分割成較小的子數組，然后將這些子數組逐個合并，最終得到一個有序的數組。合并2個數組的稱為2路歸并，合并3個數組的稱為3路歸并，多路歸并。歸并排序是穩定的。

圖1.5 歸并排序示例代碼

1.3?程序設計

1.3.1 程序設計思路

圖1.6 程序設計思路圖

1.3.2?生成input.txt文件

先創建一個文件并打開，然后生成隨機數存儲到該文件中作為后續的輸入文件。

圖1.7 生成input.txt文件代碼

1.3.3?生成排序結果文件

首先完成文件的存入函數，再分別調用不同的排序算法完成排序再存入對應的文件中。

圖1.8將數據存入文件代碼

圖1.9 排序并存入文件代碼

1.3.4完整代碼（C++）

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>// 生成隨機數并保存到文件
void generateRandomNumbers(const std::string& filename, int count) {std::ofstream file(filename);if (!file.is_open()) {std::cout << "無法打開文件：" << filename << std::endl;return;}else{std::cout << "生成成功"<<std::endl;}srand(time(NULL));for (int i = 0; i < count; ++i) {int num = rand() % 100000;  // 生成0到99999之間的隨機數file << num << std::endl;}file.close();
}// 從文件中讀取數據
std::vector<int> readNumbersFromFile(const std::string& filename) {std::vector<int> numbers;std::ifstream file(filename);if (!file.is_open()) {std::cout << "無法打開文件：" << filename << std::endl;return numbers;}int num;while (file >> num) {numbers.push_back(num);}file.close();return numbers;
}// 將數據存入文件
void writeNumbersToFile(const std::string& filename, const std::vector<int>& numbers) {std::ofstream file(filename);if (!file.is_open()) {std::cout << "無法打開文件：" << filename << std::endl;return;}else{std::cout << "存入成功"<<std::endl;}for (int num : numbers) {file << num << std::endl;}file.close();
}// 希爾排序
void shellSort(std::vector<int>& numbers) {int n = numbers.size();for (int gap = n / 2; gap > 0; gap /= 2) {for (int i = gap; i < n; ++i) {int temp = numbers[i];int j = i;while (j >= gap && numbers[j - gap] > temp) {numbers[j] = numbers[j - gap];j -= gap;}numbers[j] = temp;}}
}// 快速排序
void quickSort(std::vector<int>& numbers, int low, int high) {if (low < high) {int pivot = numbers[high];int i = low - 1;for (int j = low; j <= high - 1; ++j) {if (numbers[j] < pivot) {++i;std::swap(numbers[i], numbers[j]);}}std::swap(numbers[i + 1], numbers[high]);int partitionIndex = i + 1;quickSort(numbers, low, partitionIndex - 1);quickSort(numbers, partitionIndex + 1, high);}
}// 堆排序
void heapify(std::vector<int>& numbers, int n, int i) {int largest = i;int left = 2 * i + 1;int right = 2 * i + 2;if (left < n && numbers[left] > numbers[largest])largest = left;if (right < n && numbers[right] > numbers[largest])largest = right;if (largest != i) {std::swap(numbers[i], numbers[largest]);heapify(numbers, n, largest);}
}void heapSort(std::vector<int>& numbers) {int n = numbers.size();for (int i = n / 2 - 1; i >= 0; --i)heapify(numbers, n, i);for (int i = n - 1; i >= 0; --i) {std::swap(numbers[0], numbers[i]);heapify(numbers, i, 0);}
}// 歸并排序
void merge(std::vector<int>& numbers, int left, int middle, int right) {int n1 = middle - left + 1;int n2 = right - middle;std::vector<int> leftArr(n1);std::vector<int> rightArr(n2);for (int i = 0; i < n1; ++i)leftArr[i] = numbers[left + i];for (int j = 0; j < n2; ++j)rightArr[j] = numbers[middle + 1 + j];int i = 0, j = 0, k = left;while (i < n1 && j < n2) {if (leftArr[i] <= rightArr[j]) {numbers[k] = leftArr[i];++i;}else {numbers[k] = rightArr[j];++j;}++k;}while (i < n1) {numbers[k] = leftArr[i];++i;++k;}while (j < n2) {numbers[k] = rightArr[j];++j;++k;}
}void mergeSort(std::vector<int>& numbers, int left, int right) {if (left < right) {int middle = left + (right - left) / 2;mergeSort(numbers, left, middle);mergeSort(numbers, middle + 1, right);merge(numbers, left, middle, right);}
}int main() {// 生成隨機數并保存到文件generateRandomNumbers("input.txt", 10000);// 從文件中讀取數據std::vector<int> numbers = readNumbersFromFile("input.txt");// 復制數據用于各種排序算法std::vector<int> numbersShell = numbers;std::vector<int> numbersQuick = numbers;std::vector<int> numbersHeap = numbers;std::vector<int> numbersMerge = numbers;// 希爾排序shellSort(numbersShell);// 將結果存入文件writeNumbersToFile("shell_sorted.txt", numbersShell);// 快速排序quickSort(numbersQuick, 0, numbersQuick.size() - 1);// 將結果存入文件writeNumbersToFile("quick_sorted.txt", numbersQuick);// 堆排序heapSort(numbersHeap);// 將結果存入文件writeNumbersToFile("heap_sorted.txt", numbersHeap);// 歸并排序mergeSort(numbersMerge, 0, numbersMerge.size() - 1);// 將結果存入文件writeNumbersToFile("merge_sorted.txt", numbersMerge);return 0;
}