对三种经典排序的个人笔记
一、插入排序
void insertionSort(int A[], int N){
int i, j, v;
for (i = 1; i < N; i ++){
v = A[i];
j = i - 1;
while (j >= 0 && A[j] > v){
A[j + 1] = A[j]; //将大数后移一位,A[i]位置换值
j --; //判断下一个数否依旧大于v
}
A[j + 1] = v; //将最后截止移动的数替换为v,即已经将A[i]代表的数值插入到前面
}
}
算法复杂度为 O(N) ~ O(N ^ 2)
具有稳定性(A[j] > v 改为 A[j] >= v 即失去稳定性)
二、带有flag的冒泡排序(优化版)
void bubbleSort(int A[], int N){
int flag = 1; //flag的介入是对原算法的一种优化,使排序中途完成后便终止
for (int i = 0; flag; i ++){
flag = 0;
for (int j = N - 1; j >= i + 1; j --){
if (A[j] < A[j - 1]){
swap(A[j], A[j - 1]); //交换相邻元素
flag = 1; //如果未执行此if语句,则下次外循环flag为0,即终止循环
}
}
}
}
算法复杂度为 O(1) ~ O(N ^ 2),O(1)即为原始排序即正确的状态
具有稳定性(A[j] < A[j - 1] 改为 A[j] <= A[j - 1] 即失去稳定性)
三、选择排序
void selectionSort(int A[], int N){
int i, j, t, minj;
for (i = 0; i < N - 1; i ++){
minj = i;
for (j = i + 1; j < N; j ++){
if (A[j] < A[minj]) minj = j; //找出最小值所对应的下标
}
swap(A[j], A[minj]); //交换下标数组元素
}
}
算法复杂度为 O(N ^ 2)
不具有稳定性(如2b, 2c, 1a 预计交换后:1a, 2b, 2c 实际交换后: 1a, 2c, 2b)