数据结构实验详解排序算法

### 数据结构实验：排序算法详解

#### 插入排序
插入排序是一种简单的排序方法，适用于较小规模的数据集。其基本思想是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

- **直接插入排序**
直接插入排序是最基础的形式之一。每次从未排序部分取出一个元素，将其插入到前面已经排好的数组中的适当位置[^3]。

void InsertSort(int a[], int n) {
    int i, j;
    for (i = 1; i < n; ++i) { // 默认第一个元素已经在正确的位置上
        if (a[i] < a[i - 1]) {
            int temp = a[i];
            for (j = i - 1; j >= 0 && temp < a[j]; --j)
                a[j + 1] = a[j];
            a[j + 1] = temp;
        }
    }
}

#### 快速排序
快速排序基于分治策略来工作。它选取一个基准数（pivot），将小于等于它的放在左边，大于它的放右边，之后分别对左右两部分重复上述过程直到整个列表被排序完成[^1]。

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    else:
        pivot = arr[len(arr) // 2]
        left = [x for x in arr if x < pivot]
        middle = [x for x in arr if x == pivot]
        right = [x for x in arr if x > pivot]

        return quick_sort(left) + middle + quick_sort(right)

#### 归并排序
归并排序也是一种典型的分治法应用实例。此算法首先把待排序列分成若干个小序列，各自独立地变成有序序列；接着逐步合并这些子序列，最终形成完整的有序列表[^2]。

void merge(vector<int>& nums, vector<int>& tmp, int l, int r, int mid){
    int i=l,j=mid+1,k=l;
    
    while(i<=mid&&j<=r){
        if(nums[i]<=nums[j]){
            tmp[k++]=nums[i++];
        }else{
            tmp[k++]=nums[j++];
        }
    }

    while(i<=mid){tmp[k++]=nums[i++];}
    while(j<=r){tmp[k++]=nums[j++];}

    copy(tmp.begin()+l,tmp.begin()+k,nums.begin()+l);
}

void mergesort(vector<int>& nums,vector<int>& tmp,int l,int r){
    if(l>=r)return;

    int mid=(l+r)/2;
    mergesort(nums,tmp,l,mid);
    mergesort(nums,tmp,mid+1,r);

    merge(nums,tmp,l,r,mid);
}