冒泡排序的基本思想是通过对无序序列中的相邻元素进行“比较”和“交换”，从而实现关键字较小的元素向“一头”漂浮，而较大的元素向“另一头”下沉。
1.冒泡排序
冒泡排序的每一次外层循环都会将一个最小(大)的元素交换到指定的有序位置，并且外层的循环最多只会进行n-1次。
（1）代码如下：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
//bubbleSort.h #include <vector> using namespace std; void bubbleSort(vector<int> &vec) { //数组元素个数 vector<int>::size_type vecSize = vec.size(); if (vecSize == 0) return; unsigned i, j; //外层循环次数为元素个数-1 for(i = 0; i < vecSize-1; ++i){ //相邻的元素间比较，比较的次数与i有关，因为数组尾已经有i个元素有序了所以不需要再对它们比较 for(j = 0; j < vecSize-1-i; ++j){ //若前一个元素大于后一个元素 if(vec[j] > vec[j+1]) //则交换之，使得较大的元素慢慢的沉下去 swap(vec[j], vec[j+1]); } } } |
其中几点在编程中需要注意的是：
1）循环次数：外层循环最多进行n-1次。一般情况下，整个冒泡排序只需要进行k（1<=k<n）次，排序结束的条件是“在某一趟排序过程中没有进行元素交换的操作”，上面的代码没有考虑这点，进行n-1趟排序。
2）内存循环的次数是随着尾部有序元素个数i的增加而减小的。
3）该方法在内层循环时，是将一个最大的元素“沉”到数组的尾部。相应的也可以修改，将其最小的元素“浮”到数组的头部：
|
1 2 3 4 5 |
for(i = 0; i < vecSize-1; ++i){ for(j = vecSize-1; j > i; --j){ if(vec[j] < vec[j-1]) swap(vec[j], vec[j-1]); } |
两种方法的本质是一样的，相邻元素之间进行比较，并确定一个最大或最小的元素到指定的有序位置。
（2）冒泡排序的时间复杂度为O(n^2)，排序过程中只需要一个辅助空间，故空间复杂度为O(1）。冒泡排序是一种稳定的排序方法。
（3）示例
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
#include "bubbleSort.h" #include <iostream> #include <vector> using namespace std; int main() { //bubble sort vector<int> vec1 = {3, 4, 0, 3, 2, 1, 19, 91, 5, 12, 29}; bubbleSort(vec1); cout << "After sorted: " << endl; for (auto &i : vec1) cout << i << " "; cout << endl; return 0; } |
输出：
|
1 2 |
After sorted: 0 1 2 3 3 4 5 12 19 29 91 |
2.选择排序
选择排序的思想是每次从序列中找出一个最小的，放到第一个位置；在从剩下的序列中找出最小的，放到第二个位置，以此类推。
和冒泡排序有点类似，都是在一次排序后把最小的元素放到最前面。不同的是，冒泡排序是对相邻的元素间比较；而选择排序则是对整体的比较选择。
（1）代码如下：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
//selectSort.h #include <vector> using namespace std; void selectSort(vector<int> &vec) { //数组元素个数 vector<int>::size_type vecSize = vec.size(); if (vecSize == 0) return; //minIndex表示一趟排序中，最小的元素的位置 vector<int>::size_type i, j, minIndex; //外层循环，进行元素个数-1次 for(i = 0; i < vecSize-1; ++i){ //首先假设第一个元素就是最小的元素 minIndex = i; //从j开始，挨个和"最小的"元素比较 for(j = i+1; j < vecSize; ++j){ //如果找到比“最小的元素”还要小的元素，令该元素为"最小" if (vec[j] < vec[minIndex]) minIndex = j; } //一趟循环结束后，若找到了比i还要小的元素，则交换之 if (minIndex != i) swap(vec[i], vec[minIndex]); } } |
其中几点在编程中需要注意：
1）内层for循环，结束的条件是j < vecSize而不是j < vecSize -1。可以带特值考虑容易想明白。
2）外层循环每一次都会更新一个minIndex为元素i，然后i后面的元素在挨个与之比较，确定这一趟排序最终的minIndex。
（2）选择排序可以看成是冒泡排序的优化，因为选择排序只有在确定了最小数的前提下才进行交换，大大减少了交换的次数。选择排序的时间复杂度为O(n^2)，选择排序是在原纪录空间上通过纪录的交换进行的，只在交换纪录时需要用一个辅助工作变量，因此空间复杂度为O(1)。
（3）示例
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
#include "selectSort.h" #include <iostream> #include <vector> using namespace std; int main() { //select sort vector<int> vec2 = {3, 4, 0, 3, 2, 1, 19, 91, 5, 12, 29}; selectSort(vec2); cout << "After sorted: " << endl; for (auto &i : vec2) cout << i << " "; cout << endl; return 0; } |
输出：
|
1 2 |
After sorted: 0 1 2 3 3 4 5 12 19 29 91 |
3.插入排序
插入排序的基本操作是将当前无序序列区R[i..n]中的记录R[i]，插入到有序序列区R[1..i-1]中，使有序序列的长度增1。
（1）代码如下
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
//insertSort.h #include <vector> using namespace std; void insertSort(vector<int> &vec) { //数组中元素个数 vector<int>::size_type vecSize = vec.size(); if (vecSize == 0) return; vector<int>::size_type i, j; int key; //外层循环元素个数-1次，一次确定一个元素key for (i = 1; i < vecSize; ++i){ //假定第一个元素vec[0]有序，下面判断key=vec[1]是否比vec[0]小 key = vec[i]; //若key比前一个元素vec[j-1]小，则前一个元素向后移动一位，此时若j仍低于0，再判断vec[j-2]是否比key小，若小，则再向后移动一位 for (j = i; j > 0 && key < vec[j-1]; --j){ vec[j] = vec[j-1]; } //直到比较完有序序列或找到比key大的元素时停止，将key插入j位置 vec[j] = key; } } |
其中几点在编程需要注意：
1）外层仍然是循环元素个数-1次，但是i是从1开始，而不是0。
2）每次循环，从无序序列中取出第一个元素i，插入到有序序列[0..i-1]中。
3）内存循环的条件是j>0&&key<vec[j-1]。
（2）插入排序的时间复杂度为O(n^2)，空间复杂度为O(1)。插入排序是稳定的排序方法。
（3）示例
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
#include "insertSort.h" #include <iostream> #include <vector> using namespace std; int main() { //insert sort vector<int> vec3 = {3, 4, 0, 3, 2, 1, 19, 91, 5, 12, 29}; insertSort(vec3); cout << "After sorted: " << endl; for (auto &i : vec3) cout << i << " "; cout << endl; return 0; } |
输出：
|
1 2 |
After sorted: 0 1 2 3 3 4 5 12 19 29 91 |