直接插入排序array

### 描述直接插入排序算法

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

#### 直接插入排序的工作原理

假设有一个无序数组 `arr`，长度为 `n`。直接插入排序会遍历整个数组，每次取一个元素，并将其插入到前面已经排好序的部分中的适当位置上。为了给新元素腾出空间，可能需要移动其他元素的位置。

具体来说：

- 从未排序部分取出第一个元素作为待插入项；
- 将其与前边所有已排序过的元素依次比较；
- 如果当前元素大于等于待插入项，则将这些较大的元素向右移位；
- 找到合适位置后，把待插入项放入此位置；

重复上述过程直到处理完所有的记录为止。

以下是 Python 实现的例子:

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
            
        arr[j + 1] = key
    
    return arr

这段代码展示了如何利用循环结构来完成直接插入排序的操作逻辑。它能够有效地对小型子数组进行优化排序操作。

相关问题

1.学习直接插入排序的排序思想，直接插入排序属于插入排序的一种，理解为什么插入排序算法不是全局有序的。 2.利用直接插入排序算法解决排序问题，要求输入为排序表有10个元素，其关键字序列为（9，8，7，6，5，4，3，2，1，0），输出为关键字从小到大排序的序列。

1. **直接插入排序**的思想非常直观，它的基本步骤是每次从未排序的部分选择一个元素，然后将其插入到已排序序列的正确位置。这里的关键在于"直接"，即对于每一个元素，我们从后向前查找已排序的序列，找到合适的位置就将该元素插入。所以，即使开始时数组是无序的，每一次操作都会使当前位置及其后续的子序列保持有序。

插入排序之所以不是全局有序的，是因为它的过程是局部化的：每一次只关注未排序部分的第一个元素，直到整个序列都被处理过。因此，在最坏的情况下，当输入数据完全逆序时，需要进行n(n-1)/2次比较和移动操作，效率较低。

2. **解决排序问题示例：**
假设我们有一个包含10个元素的数组，其初始顺序为(9, 8, 7, 6, 5, 4, 3, 2, 1, 0)。使用直接插入排序，我们可以逐步地进行以下步骤：

- 第1步：假设第一个元素9已经排序，不需要移动。
- 第2步：将8与已排序的9比较，因为8小于9，交换它们的位置，得到(8, 9, 7, 6, 5, 4, 3, 2, 1, 0)。
- ...重复此过程，直到所有元素都有序。

这里是一个简单的Java代码实现，用于对给定的列表进行直接插入排序：

public class InsertionSort {
    public void sort(int[] arr) {
        for (int i = 1; i < arr.length; 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;
        }
    }

    // 测试用例
    public static void main(String[] args) {
        int[] unsortedArray = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
        InsertionSort sorter = new InsertionSort();
        sorter.sort(unsortedArray);
        System.out.println("Sorted array: " + Arrays.toString(unsortedArray));
    }
}

运行这段代码，你会看到输出为`[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]`，这就是按照从小到大的顺序排列的结果。

假设待排序数据是整型。编写C++程序，实现以下功能： (1)实现选择排序（直接选择排序）、插入排序（直接插入排序）和交换排序（快速排序、冒泡排序） (2)对于(1)实现的插入排序（直接插入排序）和交换排序（快速排序、冒泡排序），分别输出每一趟（遍）的结果和最终结果，并应用它对上面的数据序列进行排序。 (3) 输入或给定若干个已经有序或逆序的线性表，分别利用选择排序（直接选择排序）、插入排序（直接插入排序）和交换排序（快速排序、冒泡排序）、检验实际结果（运行时间和比较、移动记录次数）和理论结果的差异，并进行讨论各种方法的优劣。

以下是一个实现上述功能的C++程序：

#include <iostream>
#include <vector>
#include <ctime>
#include <cstdlib>

using namespace std;

// 选择排序
void selectionSort(vector<int>& arr) {
    int n = arr.size();
    for (int i = 0; i < n - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        swap(arr[i], arr[minIndex]);
    }
}

// 直接插入排序
void insertionSort(vector<int>& arr) {
    int n = arr.size();
    for (int i = 1; i < n; i++) {
        int temp = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > temp) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = temp;
    }
}

// 快速排序
void quickSort(vector<int>& arr, int left, int right) {
    if (left >= right) {
        return;
    }
    int pivot = arr[left];
    int l = left, r = right;
    while (l < r) {
        while (l < r && arr[r] >= pivot) {
            r--;
        }
        arr[l] = arr[r];
        while (l < r && arr[l] <= pivot) {
            l++;
        }
        arr[r] = arr[l];
    }
    arr[l] = pivot;
    quickSort(arr, left, l - 1);
    quickSort(arr, l + 1, right);
}

// 冒泡排序
void bubbleSort(vector<int>& arr) {
    int n = arr.size();
    for (int i = 0; i < n - 1; i++) {
        bool flag = false;
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr[j], arr[j + 1]);
                flag = true;
            }
        }
        if (!flag) {
            break;
        }
    }
}

// 打印数组
void printArray(vector<int> arr) {
    int n = arr.size();
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

// 生成随机数组
void generateRandomArray(vector<int>& arr, int n) {
    srand((unsigned)time(NULL));
    for (int i = 0; i < n; i++) {
        arr.push_back(rand() % n + 1);
    }
}

// 生成有序数组
void generateSortedArray(vector<int>& arr, int n) {
    for (int i = 1; i <= n; i++) {
        arr.push_back(i);
    }
}

// 生成逆序数组
void generateInvertedArray(vector<int>& arr, int n) {
    for (int i = n; i >= 1; i--) {
        arr.push_back(i);
    }
}

int main() {
    vector<int> arr1, arr2, arr3, arr4;
    int n = 10; // 数组长度
    generateRandomArray(arr1, n);
    arr2 = arr1;
    arr3 = arr1;
    arr4 = arr1;

    // 选择排序
    cout << "Selection Sort:" << endl;
    selectionSort(arr1);
    printArray(arr1);

    // 直接插入排序
    cout << "Insertion Sort:" << endl;
    insertionSort(arr2);
    printArray(arr2);

    // 快速排序
    cout << "Quick Sort:" << endl;
    quickSort(arr3, 0, n - 1);
    printArray(arr3);

    // 冒泡排序
    cout << "Bubble Sort:" << endl;
    bubbleSort(arr4);
    printArray(arr4);

    // 对有序数组进行排序
    arr1.clear();
    generateSortedArray(arr1, n);
    arr2 = arr1;
    arr3 = arr1;
    arr4 = arr1;

    cout << "Sorted Array:" << endl;
    cout << "Selection Sort:" << endl;
    selectionSort(arr1);
    printArray(arr1);

    cout << "Insertion Sort:" << endl;
    insertionSort(arr2);
    printArray(arr2);

    cout << "Quick Sort:" << endl;
    quickSort(arr3, 0, n - 1);
    printArray(arr3);

    cout << "Bubble Sort:" << endl;
    bubbleSort(arr4);
    printArray(arr4);

    // 对逆序数组进行排序
    arr1.clear();
    generateInvertedArray(arr1, n);
    arr2 = arr1;
    arr3 = arr1;
    arr4 = arr1;

    cout << "Inverted Array:" << endl;
    cout << "Selection Sort:" << endl;
    selectionSort(arr1);
    printArray(arr1);

    cout << "Insertion Sort:" << endl;
    insertionSort(arr2);
    printArray(arr2);

    cout << "Quick Sort:" << endl;
    quickSort(arr3, 0, n - 1);
    printArray(arr3);

    cout << "Bubble Sort:" << endl;
    bubbleSort(arr4);
    printArray(arr4);

    return 0;
}

在程序中，我们实现了选择排序、直接插入排序、快速排序和冒泡排序。我们还实现了生成随机数组、有序数组和逆序数组的函数，并对这些数组进行了排序。在对有序数组和逆序数组进行排序时，我们可以比较实际运行时间和理论结果的差异，并讨论各种排序算法的优劣。