605开发组算法周周练（二）

算法周周练，一天一天努力，一点一点积累

期限：3天；题目：1道；类型：基础、排序算法
1、完成三种排序算法：冒泡排序、选择排序、插入排序
2、研究并理解透各个算法特点                    

1、冒泡排序

算法思想：两两比较待排序的数据，如果反序则交换，直到没有反序的记录为止。原则把小的数交换到最前面。

void bubbleSort(vector<int> &A){
    for(int i=0;i<A.size();i++){
        for(int j=i+1;j<A.size();j++){
            if(A[i]>A[j])
                swap(A[i],A[j]);
         }
    }
}

2、选择排序

算法思想：每次在n-i+1(i=1,2,…,n-1) 个记录中选取关键字最小的记录作为有序序列的第i个记录，即从剩余数据中依次选择最小的。

void quickSort(vector<int> &A){
    for(int i=0;i<A.size();i++){
        //默认当前i位置最小
        int k=i;
        //依次遍历i之后的数据，将最小的记录到k
        for(int j=i+1;j<A.size();j++){
            if(A[j]<A[k])
                k=j;
        }
        //如果最小的是A[i]不用变，若不是则将最小的交换到A[i]
        if(k!=i){
            swap(A[i],A[k]);
        }
    }
}

3、插入排序

算法思想：每次从待插入组中取出一个元素，与有序组的元素进行比较，并找到合适的位置，将该元素插到有序组当中。

//插入排序 
//将一个记录插入到已经排好序的有序表。
void insertionSort(vector<int> &A) {
    if(A.size()==0)
        return;	
    //从1开始：假设A[0]已放好。
    for(int i=1;i<A.size();i++){
        //A[i]与前面有序数列的最大一个比较，若小于则插入，若大于则继续下一个数 
        if(A[i]<A[i-1]){
            int temp=A[i];//记录A[i]
            int j=i;
            //后移 
            while(j>0&&temp<A[j-1]){
                A[j]=A[j-1];
                j--;
            }
            //插入 
            A[j]=temp;
        }
    }
}