广东省网站备案要多久,德国著名的外贸公司地址,天津营销网站建设公司,5g影讯5g天线在线观看免费视频选择排序介绍
选择排序#xff08;Selection Sort#xff09;是一种简单的比较排序算法#xff0c;它的工作原理如下#xff1a; 分区: 将待排序的数组分成两个部分#xff0c;一个部分是已排序的子数组#xff0c;另一个部分是未排序的子数组。初始时#xff0c;已排序…选择排序介绍
选择排序Selection Sort是一种简单的比较排序算法它的工作原理如下 分区: 将待排序的数组分成两个部分一个部分是已排序的子数组另一个部分是未排序的子数组。初始时已排序的子数组为空而未排序的子数组包含整个数组。 选择最小值: 从未排序的子数组中找到最小或最大根据排序顺序而定的元素。 交换: 将找到的最小值与未排序子数组的第一个元素交换将其放入已排序的子数组的末尾。 重复: 重复上述步骤依次选择未排序子数组中的下一个最小值放入已排序的子数组中直到未排序子数组为空。 完成: 当未排序子数组为空时整个数组已经排序完成。
选择排序的特点
它的实现非常简单容易理解。它的时间复杂度为O(n^2)其中n是待排序数组的长度这使得它在大型数据集上的性能相对较差。由于它交换的次数相对较少所以在某些情况下它可能比其他简单排序算法如冒泡排序略快。
虽然选择排序在实际应用中不如高级排序算法如快速排序或归并排序高效但它在理解排序算法的工作原理时很有用通常用于教学或小型数据集的排序。
与其他排序算法比较
下面是对选择排序、冒泡排序、快速排序和归并排序的比较使用表格形式呈现
排序算法平均时间复杂度最坏情况时间复杂度稳定性额外空间主要优点主要缺点选择排序O(n^2)O(n^2)不稳定相同元素的相对位置可能会改变O(1)简单易懂适用于小型数据集性能较差不适用于大型数据集冒泡排序O(n^2)O(n^2)稳定相同元素的相对位置不会改变O(1)简单易懂适用于小型数据集性能较差不适用于大型数据集快速排序O(n*log(n))O(n^2)不稳定相同元素的相对位置可能会改变O(log(n))平均情况下性能优秀适用于大型数据集最坏情况下性能较差归并排序O(n*log(n))O(n*log(n))稳定 相同元素的相对位置不会改变O(n)稳定且性能稳定适用于大型数据集需要额外空间递归实现可能占用栈空间
c实现
#includeiostream
using namespace std;const int MAXN10001;
int main(){int n8,k,i,j;float temp,a[MAXN];a[1]10;a[2]6;a[3]7;a[4]1;a[5]2;a[6]16;a[7]18,a[8]9;for(i1;in;i){ki;for(ji1;jn;j){if(a[j]a[k]){kj;}}if(k!i){temp a[i];a[i] a[k];a[k]temp;}}for(i1;in;i){couta[i] ;}return 0;
}java实现
public class SelectionSort {public static void selectionSort(float[] arr) {int n arr.length;for (int i 0; i n; i) {int minIndex i;for (int j i 1; j n; j) {if (arr[j] arr[minIndex]) {minIndex j;}}if (minIndex ! i) {float temp arr[i];arr[i] arr[minIndex];arr[minIndex] temp;}}}public static void main(String[] args) {float[] a {10, 6, 7, 1, 2, 16, 18, 9};selectionSort(a);for (float num : a) {System.out.print(num );}}
}
python 实现
def selection_sort(arr):n len(arr)for i in range(n):min_index ifor j in range(i 1, n):if arr[j] arr[min_index]:min_index jif min_index ! i:arr[i], arr[min_index] arr[min_index], arr[i]return arrif __name__ __main__:a [10, 6, 7, 1, 2, 16, 18, 9]sorted_a selection_sort(a)print(sorted_a)
