2. 交换排序
?
2.1 冒泡排序
什么是冒泡排序？
冒泡排序（Bubble Sort）也是一种简单直观的排序算法。
它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
代码实现如下:
void BubbleSort(int *a,int length){
int i,j;
int flag=1; //判断是否进行循环
for(i=0;i<length-1&&flag==1;i++){
for(j=0;j<length-1-i;j++){
flag=0;
if(a[j]>a[j+1]){
flag=1;
int temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}
}
}但由于冒泡排序的时间复杂度过高，所有引申出了一种新型的排序 -- 快速排序（QuickSort）。
这个名字就能彰显出其速率之快.
那这种排序是如何实现的？
代码如下:
//快速排序
int Partition(int*a,int left,int right){
int temp=a[left];//left下标作为基准数
while(left<right){
while(left<right&&a[right]>temp){
right--;
}
if(left<right){
a[left]=a[right];
}
while(left<right&&a[left]<temp){
left++;
}
if(left<right){
a[right]=a[left];
}
}
a[right]=temp;
return right;
}
void QuickSort(int*a,int left,int right){
if(left<right){
int pivot=Partition(a,left,right);
QuickSort(a,left,pivot-1);
QuickSort(a,pivot+1,right);
}
}我们首先选择一个作为基准数，然后遍历整个数组（除了基准数），将小于基准数的放在它的左边，大于基准数的放在它的右边。
然后将基准数的左边和右边右看成一个数组，重复上述操作，直到每个数组只剩一个元素。
让我再水一期
