C/C++选择排序与冒泡排序

主要是最近又看了一眼回忆一下，所以就写下来，首先我们要明确这两个算法共同的排序思想，时间复杂度也都是O(n^2)，选择与冒泡的区别。 1、我们打个比方，1,2,3,4,5,6,8,7,9,10；是一个无序序列，假如按照从大到小排序，我们的排序思想就是，先O(n)遍历一轮，把其中最大值放到序列的最左边，然后截取一位，实际序列为10,1,2,3,4,5,6,8,7,9，我们要会截取子序列，也就是1,2,3,4,5,6,8,7,9，从这里面找到最大的9放入左边，以此类型，就排序好了，我说的是冒泡与选择共有的思想，我们现在细节一点说。

void bubble_sort(int arr[], int len) {
        int i, j, temp;
        for (i = 0; i < len - 1; i++)
                for (j = 0; j < len - 1 - i; j++)
                        if (arr[j] > arr[j + 1]) {
                                temp = arr[j];
                                arr[j] = arr[j + 1];
                                arr[j + 1] = temp;
                        }
}

//选择
	template<typename T>//从小到大升序
	void selectSort(T arr[], int len) {
		for (int i = 0; i < len; i++) {
			int min = i;
			for (int j = i + 1; j < len; j++) {
				if (arr[j] < arr[min]) {
					min = j;
				}
			}
			if (min != i) {
				std::swap(arr[min], arr[i]);
			}
		}
	}

选择排序的思想不同在于它是改进的冒泡排序，冒泡排序需要一轮一轮的交换,比如1 2 3 4，要把4与3交换比较交换，再于2比较交换，再与1比较交换....每一轮交换的复杂度是O(n)，选择排序就不会这样交换，只会交换一次，放到需要的位置，选择排序让它变为常数项，每轮交换只需要O(1)，虽然依旧有改进空间，但是不管是选择还是冒泡，在最坏的情况下依旧是O(n^2)，理解即可。

最后说一句，序列中字找到最大的，然后找第二大的，以此类推，就完成了排序，记住中心思想就行