数据结构内排序笔记

好的，我可以为您提供关于数据结构内排序的笔记。

内排序是指在排序过程中，所有待排序的数据元素全部存放在内存中进行排序。常见的内排序算法有冒泡排序、插入排序、选择排序、快速排序、归并排序等。

1. 冒泡排序

冒泡排序是一种交换排序。它的基本思想是：通过交换相邻两个元素的位置，把大的元素往后面移动，小的元素往前面移动，从而实现排序的目的。

代码实现：

void bubble_sort(int arr[], int len) {
    for (int i = 0; i < len - 1; i++) {
        for (int j = 0; j < len - i - 1; j++) {
            if (arr[j] > arr[j+1]) {
                swap(arr[j], arr[j+1]);
            }
        }
    }
}

2. 插入排序

插入排序是一种插入排序。它的基本思想是：将待排序的元素插入到已经排好序的序列中，从而得到一个新的、更大的有序序列。

代码实现：

void insertion_sort(int arr[], int len) {
    int i, j, tmp;
    for (i = 1; i < len; i++) {
        tmp = arr[i];
        for (j = i; j > 0 && arr[j-1] > tmp; j--) {
            arr[j] = arr[j-1];
        }
        arr[j] = tmp;
    }
}

3. 选择排序

选择排序是一种选择排序。它的基本思想是：每次从待排序的序列中选择一个最小的元素，放到已经排好序的序列的末尾，直到所有元素都排好序。

代码实现：

void selection_sort(int arr[], int len) {
    int i, j, min_idx;
    for (i = 0; i < len - 1; i++) {
        min_idx = i;
        for (j = i + 1; j < len; j++) {
            if (arr[j] < arr[min_idx]) {
                min_idx = j;
            }
        }
        swap(arr[i], arr[min_idx]);
    }
}

4. 快速排序

快速排序是一种分治排序。它的基本思想是：通过一趟排序将待排序序列分割成独立的两部分，其中一部分的所有元素都比另一部分的元素小，然后再对这两部分分别进行排序，直到整个序列排好序为止。

代码实现：

void quick_sort(int arr[], int l, int r) {
    if (l < r) {
        int i = l, j = r, x = arr[l];
        while (i < j) {
            while (i < j && arr[j] >= x) j--;
            if (i < j) arr[i++] = arr[j];
            while (i < j && arr[i] < x) i++;
            if (i < j) arr[j--] = arr[i];
        }
        arr[i] = x;
        quick_sort(arr, l, i-1);
        quick_sort(arr, i+1, r);
    }
}

5. 归并排序

归并排序是一种分治排序。它的基本思想是：将待排序序列分成若干个子序列，每个子序列都是有序的，然后再将子序列合并成一个有序序列。

代码实现：

void merge(int arr[], int l, int m, int r) {
    int i, j, k;
    int n1 = m - l + 1;
    int n2 = r - m;

    int L[n1], R[n2];

    for (i = 0; i < n1; i++) L[i] = arr[l + i];
    for (j = 0; j < n2; j++) R[j] = arr[m + 1 + j];

    i = 0;
    j = 0;
    k = l;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k++] = L[i++];
        } else {
            arr[k++] = R[j++];
        }
    }

    while (i < n1) {
        arr[k++] = L[i++];
    }

    while (j < n2) {
        arr[k++] = R[j++];
    }
}

void merge_sort(int arr[], int l, int r) {
    if (l < r) {
        int m = (l + r) / 2;
        merge_sort(arr, l, m);
        merge_sort(arr, m+1, r);
        merge(arr, l, m, r);
    }
}

以上是内排序的几种常见算法。需要注意的是，不同的算法在不同的数据情况下，其效率也会有所不同。