选择排序和Java实现、C++ vector 模板类实现

选择排序，Selection sort。工作原理是：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。

无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候，数据规模越小越好。

算法步骤

    首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。

    再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。

    重复第二步，直到所有元素均排序完毕。
 

Java实现

public class SelectionSort {public static void main(String[] args) {int[] arr={7,13,2,45,5,33,12,9};System.out.println("not sort：");for(int num:arr){System.out.print(num+" ");} for(int i = 0; i < arr.length - 1; i++){int k = i;for(int j = k + 1; j < arr.length; j++){if(arr[j] < arr[k]){ k = j;}}if(i != k){int temp = arr[i];arr[i] = arr[k];arr[k] = temp;} }System.out.println();System.out.println("sort：");for(int num:arr){System.out.print(num+" ");}}}

完全按算法原理，实现它可能用2个数组，一个未排序序列，一个已排序序列；

实际只用一个数组；注意外层循环是从0到数组长度，内层循环的起始值每次是变的；这样算法说的未排序序列和已排序序列是用的一个数组；

如果在编译时出现 编码GBK的不可映射字符 错误；一种解决方法是javac时加上如上图 UTF-8 参数；

C++ vector 模板类实现

#include <iostream>#include<vector>using namespace std;template<typename T> void selection_sort(std::vector<T>& arr) {for (int i = 0; i < arr.size() - 1; i++) {int min = i;for (int j = i + 1; j < arr.size(); j++)if (arr[j] < arr[min])min = j;std::swap(arr[i], arr[min]);}}int main() {int a[] = { 61, 17, 29, 22, 34, 60, 72, 21, 50, 1, 62 };vector<int>arr(a,a+11);selection_sort(arr);for (int i = 0; i < 11; i++)cout << arr[i] << ' ';cout << endl;return 0;}

此模板类可支持各种数据类型；

总结

以上是生活随笔为你收集整理的选择排序和Java实现、C++ vector 模板类实现的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。