简单排序
简单排序
0x00 基础知识
1这里所谓的内部排序是指，所有的待排序元素能够都装入内存，所有排序是一次性在内存完成的
外部排序则内存内只能一次排序部分数据
2基于比较的排序，也就是要能够比较大小
0x01 冒泡排序和插入排序的代码实现
#include <stdio.h>
int buble_sort(int * data,int size){
int i,j;
int cnt=0;
int flag;
for(i=0;i<size-1;i++){
flag=0;
for(j=0;j<size-1-i;j++){
if(data[j]>data[j+1]){
int temp=data[j];
data[j]=data[j+1];
data[j+1]=temp;
flag=1;
cnt++;
}
}
if(!flag){
break;
}
}
return cnt;
}
int insert_sort(int* data,int size){
int i,j;
int cnt=0;
for(i=1;i<size;i++){
int temp=data[i];
for(j=i;j>0&&temp<data[j-1];j--){
data[j]=data[j-1];
cnt++;
}
data[j]=temp;
}
return cnt;
}
void print_data(int* data,int size){
int i=0;
for(i=0;i<size;i++){
printf("%d ",data[i]);
}
printf("\n");
}
int main(){
int data[]={34,8,64,51,32,21};
printf("%d\n",insert_sort(data,6));
print_data(data,6);
return 0;
}
冒泡排序：从前往后不断比较相邻的两个元素，如果前大后小，就要交换。一次前述操作可以使最大的元素到最后面，那么我们多次进行这样的操作，一共进行n次，那么时间复杂度为O(n^2)。性能优化：注意到，第一次从前往后交换后，最大的已经到末尾，因此第二次从前往后交换，不用考虑最后一个，也就是检查的序列由0->n-1变成了0->n-2,不断减小。另外如果一开始给定的序列就是有序的，那么还是一遍一遍检查交换是很蠢的，因此用一个变量来保存每次检查后交换的次数，如果一次也没交换，那么说明已经有序，就退出循环。因此冒泡排序时间复杂度最好O(N) 最差O(n^2）
插入排序：将序列分为待排序部分和已经排序部分，每次从待排序部分选一个元素，与已排序部分比较，从最后最大的比较起，如果比它大，就插在最后，如果比他小，就往前比较，最终插在前面，注意的是插在前面在数组里表现为元素往后挪。
0x02 时间复杂度下界分析
插入排序和冒泡排序的最好时间复杂度效率都是由逆序对数量决定的，由于这两种排血算法都只能交换相邻的元素，因此一次只能消除一个逆序对，所以，要提高排序效率，每次要消除更多逆序对
