数据结构(8.4_1)——简单选择排序

简单选择排序

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

 

 

 

 

 

 

 

代码实现 

//简单选择排序
void SelectSort(int A[], int n) {for (int i = 0; i < n - 1; i++) {//一共进行n-1趟int min = i;//记录最小元素位置for (int j = i + 1; j < n; j++)//在A[i...n-1中选择最小的元素）if (A[j] < A[min])min = j;//更新最小元素位置if (min != i)Swap(A[i], A[min]);//封装的swap()函数共移动元素3次}
}
void Swap(int& a, int& b) {int temp = a;a = b;b = temp;
}

算法性能分析

空间复杂度：O(1)

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

 

稳定性：不稳定 

适用性：既可以用于顺序表也可以用于链表 

总结