算法介绍
简单选择排序的工作方式突出"选择"二字，每次从待排序数据中选择符合条件的元素放在已排序元素末尾。对于少量元素的排序，简单选择排序是一个有效的算法。
算法描述
第一次从待排序的数据元素中选出最小(或最大)的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小(大)元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。
动图演示
算法分析
时间复杂度：O(N2)
空间复杂度：O(1)
稳定性：不稳定
代码实现
// C++ void selectionSort(int a[], int length) { for (int i = 0; i < length - 1; ++i) { // 遍历序列 int minIndex = i; // 记录最小元素位置 // 遍历无序序列寻找最小元素 for (int j = i + 1; j < length; ++j) { if (a[j] < a[minIndex]) { // 更新最小元素下标 minIndex = j; } } // 将最小值放到已排序序列的末尾 int temp = a[i]; a[i] = a[minIndex]; a[minIndex] = temp; } }
算法优化
上面代码一次遍历只是找出未排序序列中的最小值，其实我们可以在遍历过程中同时找出最小值和最大值，并把每次找出的最大值按顺序放到每次排列数据的末尾。时间复杂度还是 O(N^2) ，只相对前面的减少了一半遍历次数。
// C++ void selectionSort(int a[], int length) { int left = 0; // 标记未排序序列左边界 int right = length - 1; // 标记未排序序列右边界 while (left < right) { // 遍历未排序序列 int minIndex = left; // 记录最小元素位置 int maxIndex = left; // 记录最大元素位置 // 遍历无序序列寻找最小和最大元素 for (int i = left + 1; i <= right; ++i) { if (a[i] < a[minIndex]) { // 更新最小元素下标 minIndex = i; } if (a[i] > a[maxIndex]) { // 更新最大元素下标 maxIndex = i; } } // 将最小值放到已排序序列的左末尾 int temp = a[left]; a[left] = a[minIndex]; a[minIndex] = temp; // 处理最大值为a[left]的特殊情况 if (maxIndex == left) { maxIndex = minIndex; } // 将最大值放到已排序序列的右末尾 temp = a[right]; a[right] = a[maxIndex]; a[maxIndex] = temp; // 修改未排序序列范围 ++left; --right; } // 将最小值放到已排序序列的左末尾 int temp = a[left]; a[left] = a[minIndex]; a[minIndex] = temp; // 处理最大值为a[left]的特殊情况 if (maxIndex == left) { maxIndex = minIndex; } // 将最大值放到已排序序列的右末尾 temp = a[right]; a[right] = a[maxIndex]; a[maxIndex] = temp; // 修改未排序序列范围 ++left; --right; } // 将最小值放到已排序序列的左末尾 int temp = a[left]; a[left] = a[minIndex]; a[minIndex] = temp; // 处理最大值为a[left]的特殊情况 if (maxIndex == left) { maxIndex = minIndex; } // 将最大值放到已排序序列的右末尾 temp = a[right]; a[right] = a[maxIndex]; a[maxIndex] = temp; // 修改未排序序列范围 ++left; --right; }
参考
数据结构与算法分析(Java语言描述)
数据结构(C语言版)
————————————————
版权声明：本文为CSDN博主「Acx7」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
