1.冒泡排序(Bubble Sort)
时间复杂度为O(n^2),是一个稳定的排序算法，可以用一个flag判断，每一趟都进行检测，一旦有一趟a[j]<a[j+1]都成立，那么可以说已经完成排序，最好情况下O(n).
代码实现
//main.cpp
int main(){
int arr[] = { 1, 34, 11, 2, 6, 7, 3, 93, 1, 24, 5, 67, 23, 4, 2, 3, 1, 7, 8, 4, 2, 10 };
int len=sizeof(arr)/4;
bubble_sort(&arr[0],len);//或者下面的方式也可以
//bubble_sort(arr,len);
for (int i = 0; i < len; i++)
cout << arr[i]<<" ";
cout << endl;
return 0;
}
/////////////////////////////////////////////////////////////////////////////////////
//bubble_sort.cpp
void bubble_sort(int * arr,int len){
//int len = sizeof(arr) / 4;
//在这里使用sizeof，计算的将是一个指针的长度，而不是一个数组的长度
for (int i = 0; i < len - 1; i++){
for (int j = i+1; j < len; j++){
if (arr[i]>arr[j]){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
}
2.选择排序（Selection Sort）
是一个十分均衡的算法，最好最坏都是O(n^2)的复杂度，是一个不稳定算法。无法直接判断最好的情况。每次都选择最小的元素，和“第一个”元素交换位置。然后第一个元素下标加1，下一个元素吧变成第一个元素
代码实现
void selection_sort(int *arr, int len){
int min_index = 0, min_num;
if (len>0) min_num = arr[0];
for (int i = 0; i < len - 1; i++){
min_index =i;
min_num = arr[i];
for (int j = i + 1; j < len; j++){//选择最小值，记录下标和值
if (arr[j] < min_num){
min_index = j;
min_num = arr[j];
}
}
int tmp = arr[i]; //交换最小值到第一位
arr[i] = arr[min_index];
arr[min_index] = tmp;
}
}
3.插入排序（Insertion Sort）
平均复杂度为O(n^2)，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。对于大小为N的数组，当检索到第k位时(0=<k<N)，0~k-1位都已经是排好序的。
代码实现
void insertion_sort(int *arr, int len){
int current,index;
for (int i = 1; i < len; i++){
index = i - 1;
current = arr[i];
while (index >=0){
if (arr[index] <= current) //已排好序的最大数与当前要插入的数比较
break;
else {
arr[index + 1] = arr[index];
index--;
}
}
arr[index + 1] = current;
}
}
