37.2° Blog

每一趟在待排序元素中选取关键字最小（或最大）的元素加入有序子序列中

1.简单选择排序

算法原理

• 每一趟在待排序元素中选取关键字最小的元素加入有序子序列中
• 必须进行总共n-1趟处理

性能

空间复杂度：O(1)

时间复杂度：O(n^2)

稳定性：不稳定

适用性：顺序表、链表都可以

代码

void selectSort(SqList& L)
{
    // 记录最小元素的位置
    int minIndex;
    // 共遍历 L.Length 次
    for (int i = 0; i < L.length; i++)
    {
        minIndex = i;
        // 选择最小元素
        for (int j = i + 1; j < L.length; j++)
        {
            if (L.data[j] < L.data[minIndex])
                minIndex = j;
        }
        // 交换元素
        if (minIndex != i)
        {
            int tmpElem = L.data[i];
            L.data[i] = L.data[minIndex];
            L.data[minIndex] = tmpElem;
        }
    }
}

2.堆排序