首页 > 代码库 > 排序算法——直接插入排序

排序算法——直接插入排序

2024-07-04 02:51:11   214人阅读

直接插入排序是一种实现较为简单的排序算法。

基本的思想是，从数组的第二个元素起，每次选取一个元素，与前面已经排序数组的元素比较，找到该元素的合适位置。

不多说，直接上代码。

#include <iostream>
#include <iomanip>
#include <ctime>
using namespace std;

const int arrSize = 16;

void InsertSort(int* arr, int size)
{
    int i = 0;
    int j = 0;
    int key = 0;

    for (j = 1; j != arrSize; ++j) {
        key = arr[j];
        i = j - 1;
        while (i >= 0 && arr[i] > key) {
            arr[i+1] = arr[i];
            --i;
        }
        arr[i+1] = key;
    }
}

int main()
{
    srand((unsigned int)time(NULL));
    int arr[arrSize];

    for (int index = 0; index != arrSize; ++index) {
        arr[index] = rand() % 1000;
    }

    InsertSort(arr, arrSize);

    for (int index = 0; index != arrSize; ++index) {
        cout << setw(4) << arr[index] << ‘ ‘;
        if ((index+1) % 4 == 0) {
            cout << endl;
        }
    }

    return 0;
}

 

直接插入排序的最坏情况下的时间复杂度是O(n2)，空间复杂度为O(1)。


联系
我们