数据结构选择排序C++

选择排序是一种简单直观的排序算法，其基本思想是每次选择待排序数组中最小（或最大）的元素，放到已排序数组的末尾（或开头）。具体实现如下：

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

其中，n表示待排序数组的长度。在实现过程中，我们使用两个循环，外层循环控制已排序数组的范围，内层循环用于查找未排序数组中最小元素的下标。在内层循环结束后，将未排序数组中最小元素与已排序数组的末尾元素进行交换，即可完成一次选择排序。

需要注意的是，选择排序的时间复杂度为O(n^2)，不适用于大规模数据的排序。

相关问题

数据结构快速排序c++

好的，下面是快速排序的C++代码实现：

#include <iostream>
using namespace std;

// 交换函数
void swap(int& a, int& b){
    int temp = a;
    a = b;
    b = temp;
}

// 快速排序函数
void quickSort(int arr[], int left, int right){
    if(left >= right)
        return;

    int i = left, j = right, pivot = arr[left];
    while(i < j){
        while(i < j && arr[j] >= pivot)
            j--;
        while(i < j && arr[i] <= pivot)
            i++;
        if(i < j)
            swap(arr[i], arr[j]);
    }

    arr[left] = arr[i];
    arr[i] = pivot;
    quickSort(arr, left, i-1);
    quickSort(arr, i+1, right);
}

int main(){
    int arr[] = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3};
    int size = sizeof(arr) / sizeof(arr[0]);

    quickSort(arr, 0, size-1);

    for(int i=0; i<size; i++)
        cout << arr[i] << " ";

    return 0;
}

这个快速排序算法的时间复杂度为O(nlogn)，并且是一种使用分治策略的排序算法。

数据结构折半插入排序c++

以下是C++实现的折半插入排序代码：

void binaryInsertSort(int arr[], int len) {
    for (int i = 1; i < len; i++) {
        int temp = arr[i];
        int left = 0, right = i - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (arr[mid] > temp) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        for (int j = i - 1; j >= left; j--) {
            arr[j + 1] = arr[j];
        }
        arr[left] = temp;
    }
}

折半插入排序的基本思想是：将一个元素插入到已经排好序的数组中，仍然保持有序。与直接插入排序不同的是，折半插入排序使用二分查找来寻找插入位置，从而减少了比较次数，提高了排序效率。