冒泡排序

测试例子：5 2 1 6 4 7 9 0 8 3

思路： 冒泡排序通过从开始位置的元素两两比较后面的元素，找到最大值，放到数组的最后面。每次找到最大值，就将数组大小减1 比较的两个数，如果前面的数比后面的数据大，就交换两个数，如果前面的数比较小，就不交换两个数。 （比较的思路容易和选择排序混淆）时间复杂度： 平均：O(n^2) 每遍历一次数组，只能确定一个数的正确位置，因此n个元素，一共是n^2次遍历 最好：O(n) 本身有序，遍历了一次稳定性： 稳定。 前后两个值相等的情况下不交换位置，因此相等的值的相对位置没有发生改变。 void BubbleSort(int arr[], int size) { int flag = 0; //优化标记，如果本身有序，就不会修改flag的值 for (int i = 0; i < size; i++) { for (int j = 0; j < size - i -1; j++) { if (arr[j] > arr[j + 1]) { flag = 1; int tmp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = tmp; } } if (flag == 0) return ; } }

---

选择排序

例子： 5 2 1 6 4 7 9 0 8 3

思路：每遍历一趟就找到当前数组中的最大值，交换数组最后一个位置的值和这个最大值。 每遍历一趟，就将数组的大小减1

时间复杂度： 平均：O(n^2) 最好，最坏：O(n^2)

稳定性： 不稳定。

优化版本：每遍历一遍，找到最大值和最小值，分别放到数组两端。每遍历一趟，就将数组大小减2。 注意：先交换的是最大值和数组最后面的元素，因此有可能原本最后面的元素是最小值，所以当发生这种情况的时候，要将最小值的去处记录下来。 用下标来i，以及原数组长度size来控制当前有效数组的下标边界是什么。

void SelectSort(int arr[10],int size) { for (int i = 0; i < size; i++) { //max表示最大值所对应的下标 int max = 0; for (int j = 0; j < size - i; j++) { if (arr[max] < arr[j]) max = j; } //交换最大值和最后一个元素 int tmp = arr[max]; arr[max] = arr[size - 1 - i]; arr[size - 1 - i] = tmp; } return; } //下面是优化版本 void SelectSort2(int arr[10], int size) { for (int i = 0; i < size/2; i++) { //max表示最大值所对应的下标 int max = i; int min = i; for (int j = i; j < size - i; j++) { if (arr[max] < arr[j]) max = j; if (arr[min] > arr[j]) min = j; } //交换最大值和最后一个元素 int tmp = arr[max]; arr[max] = arr[size - 1 - i]; arr[size - 1 - i] = tmp; if (min == size - 1 - i) min = max; //交换最小值和第一个元素 tmp = arr[min]; arr[min] = arr[i]; arr[i] = tmp; } return; }