数据结构实验 排序2

### 数据结构实验中的排序算法

#### 插入排序
插入排序是一种简单直观的排序方法。该算法通过构建有序序列，对于未排序的数据，在已排序序列中从后向前扫描，找到相应位置并插入[^1]。

void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; ++i) {
        int key = arr[i];
        int j = i - 1;
        
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

#### 冒泡排序
冒泡排序重复遍历要排序列表，依次比较相邻元素，如果顺序错误则交换它们的位置。这个过程会持续到整个列表变得有序为止。

void bubbleSort(int arr[], int n) {
    bool swapped;
    do {
        swapped = false;
        for (int i = 0; i < n - 1; ++i) {
            if (arr[i] > arr[i + 1]) {
                std::swap(arr[i], arr[i + 1]);
                swapped = true;
            }
        }
    } while (swapped);
}

#### 快速排序
快速排序采用分治策略来把一个序列分为较小和较大的两个子序列，然后递归地排序这两个子序列。存在多种实现方式，包括Hoare版本、挖坑法以及前后指针法等[^2]。

// 使用Hoare分区方案
int partition(int arr[], int low, int high) {
    int pivot = arr[(low + high) / 2];
    while (true) {
        while (arr[low] < pivot) low++;
        while (arr[high] > pivot) high--;
        if (low >= high) break;

        std::swap(arr[low++], arr[high--]);
    }

    return high;
}

void quickSort(int arr[], int left, int right) {
    if (left < right) {
        int pi = partition(arr, left, right);

        quickSort(arr, left, pi);
        quickSort(arr, pi + 1, right);
    }
}

#### 希尔排序
希尔排序是对直接插入排序的一种改进形式。它按照增量序列将待排序数组划分为若干个子表分别进行直接插入排序，随着增量逐渐减小直至为1完成最终排序[^3]。

void shellSort(int arr[], int size) {
    for (int gap = size / 2; gap > 0; gap /= 2) {
        for (int i = gap; i < size; i++) {
            int temp = arr[i];
            int j;
            for (j = i; j >= gap && arr[j - gap] > temp; j -= gap)
                arr[j] = arr[j - gap];

            arr[j] = temp;
        }
    }
}

这些代码片段展示了如何在实际编程环境中应用不同的排序技术。每种算法都有其特点和适用场景，了解它们的工作原理有助于更好地掌握数据结构课程的内容。