冒泡、选择、插入排序算法小总结

冒泡排序：在排序的过程中总是小的数往前放，大数往后放，相当于气泡往上升（升序排列），所以称为冒泡排序。
思路：如果有 n 个数，则需要 n-1 趟比较（剩下一个数时不需要比较），在第一趟中进行n-1次两两比较，在第i趟需要进行n-i次两两比较，因此共需比较 (n-1)+(n-2)+...+(n-i)+...+1=n(n-1)/2 次。
<pre>
//冒泡法（升序排列）
int temp = 0; //中间变量
int sw = 0; //统计交换次数
int com = 0; //统计比较次数
for (int i = 0; i < N-1; i++){ //进行 N-1 趟比较
for (int j = 0; j < N-1 - i; j++){ //每趟中进行 N-i次比较
com++;
if (A[j] > A[j + 1]){ //相邻两个数进行比较
temp = A[j];
A[j] = A[j + 1];
A[j + 1] = temp; //交换相邻元素
//swap(A[j], A[j + 1]);
sw++;
}
}
}
cout << "\t比较次数为：" << com << endl;
cout << "\t交换次数为：" << sw << endl;
</pre>
结果：

冒泡排序法.png
稳定性：稳定排序是指数据中存在2个或者2个以上键值相等的元素时，这些元素在排序处理前后顺序不变。冒泡排序仅对数组中的相邻元素进行比较和置换，因此值相同的元素不会改变顺序，因此冒泡排序也属于一种稳定排序的算法。但是当比较条件改为
<pre>
A[j] >= A[j + 1]
</pre>
算法就会失去稳定性。
复杂度：假如数据总量为N，则冒泡排序需要进行N(N-1)/2次比较，也就是说冒泡排序在最换的情况下需要进行N(N-1)/2次比较运算，大多数时候，在计算复杂度时只留下对代数式影响最大的项，忽略常数项，因此算法的复杂度为O(N*N)。
PS：冒泡排序中的交换次数又称为反序数或逆序数，用来体现数据的错乱程度。

插入排序：插入排序就是依次取待排列数组的元素，将其插入到前面有序的数组中。它的工作原理可以用打扑克牌时排列手牌的方法类似：假如我现在要将手里的牌从小到大、从左到右进行排序，我需要将牌一张张抽出来，在前面I已排序的手牌中找到适当的位置进行插入，然后继续下一张。
思路：

插入排序.jpg
<pre>
//按顺序输出数组元素
void trace(int A[], int N){
for (int i = 0; i < N; i++) {
if (i > 0)
cout << " "; //相邻元素之间输出一个空格
cout << A[i];
}
cout << endl;
}
/插入排序
void insertionSort(int A[], int N){
int j, i, v;
for (i = 1; i < N; i++){
v = A[i];
j = i - 1;
while (j >= 0 && A[j]>v){
A[j + 1] = A[j];
j--;
}
A[j + 1] = v;
cout << "\t\t ";
trace(A, N);
}
}
</pre>
外层循环i从1开始自增，在每次循环开始，将A[i]的值临时保存在临时变量v中，内部循环是从已排序部分找出比v大的元素并让它们顺序后移一个位置。这里让j从i-1开始向前自减，同时将比v大的元素从A[j]移动到A[j+1]，一旦j等于-1或者当前A[j]小于等于v则结束循环，并将v插入到当前j+1的位置。
结果：
插入排序.png
稳定性：在排序中只将比v大的元素向后平移，不相邻元素不会直接交换换位置，因此该算法是稳定排序算法。
复杂度：这里需要估算每个i循环中A[j]元素向后移动的次数，最坏情况下，每个i循环都需要执行i次移动，总共需要1+2+...+N-1=N(N-1)/2次移动，即复杂度为O(N2)。
PS：对于插入排序，输入数据的顺序能大幅影响它的复杂度，上面说的它的复杂度为O(N2)也仅仅指输入排序为降序排列的情况，如果输入数据为升序排列，那么A[j]从头到尾都不需要移动，只需经历N-1次比较便可执行完毕，因此插入排序的优势在于能快速处理相对有序的数据。

选择排序：从需要排序的数据中选择最小的值和第一个交换，再从剩下的部分选取最小的值和第二个进行交换，循环执行下去，最后完成数据的排序。
思路：

选择排序.jpg
<pre>
//选择排序算法
int selectionSort(int A[], int N){
int i, j, t, minj, sw = 0;
for ( i = 0; i < N-1; i++ )
{
minj = i;
for( j = i+1; j < N; j++ )
{
if (A[j] < A[minj]) minj = j;
}
t = A[i]; A[i] = A[minj]; A[minj] = t;
if( i != minj ) sw++;
}
return sw;
}
</pre>
在每一轮i的循环中，通过j自增来遍历A[i]到A[N-1]，从而确定minj，确定minj后，让起始元素A[i]与最小值元素A[minj]进行交换。
结果：
选择排序.png
稳定性：由于选择排序会直接交换两个不相邻的元素，所以属于不稳定的排序算法。
复杂度：假设数据总数为N，那么无论在任何情况下，都需要进行(N-1)+(N-2)+...+1=N(N-1)/2次比较运算，用于搜索未排序部分的最小值。因此算法的复杂度为O(N2)。

总结：冒泡排序法与选择排序相比，一个从局部入手减少逆序元素，一个放眼大局逐个选择最小值，两者思路不同，但是它们都有着“通过i次外层循环，从数据中顺序求出i个最小值”的相同特征。相对地，插入排序是通过i次外层循环，直接将原数组的i个元素重新排序。另外冒泡排序和选择排序不依赖数据，即比较运算次数（算法负责度）不受输入数据影响，而插入算法在执行时依赖数据，处理某些数据时具有很高的效率。