排序算法

发表于 更新于 分类于 Waline： 阅读次数： 
1
2
3
4
5
6
7
8
9
10
11
//冒泡 每次会确定一个数字的最终位置
void sort_bubble(int *a){
    int i,j;
    for(i=n-1;i>0;i--){
        for(j=0;j<i;j++){
            if(a[j]>a[j+1]){//改成<变成递减
                swap(a[j],a[j+1]);
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
//选择排序 一次循环找到一个当前未排序序列的最大（最小）值，放到队列首位（或末尾）
void sort_select(int *a){
    int i,j,min_pos;
    for(i=0;i<n-1;i++){
        min_pos=i;
        for(j=i+1;j<n;j++){//找未排序序列最小值
            if(a[min_pos]>a[j]){
                min_pos=j;
            }
        }
        swap(a[i],a[min_pos]);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//插入排序，类比打扑克洗牌，注意把未排序数字插入合适位置
void sort_insert(int *a){
    int i,j,k,insert_val;
    for(i=1;i<n;i++){
        for(j=0;j<i;j++){
            if(a[i]<a[j]){
                insert_val=a[i];
                for(k=i-1;k>=j;k--){//元素后移
                    a[k+1]=a[k];
                }
                a[j]=insert_val;
                break;
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//快速排序 以一个数为锚点分为两部分，递归到每组一个元素
int partition(int *a,int left,int right){//以该部分数组最后一个数为锚点
    int i,k=left;
    for(i=left;i<right;i++){
        if(a[i]<a[right]){
            swap(a[k],a[i]);
            k++;
        }
    }
    swap(a[right],a[k]);
    return k;
}
int sort_quick(int *a,int left,int right){
    int pivot;
    if(left<right){
        pivot=partition(a,left,right);
        sort_quick(a,left,pivot-1);
        sort_quick(a,pivot,right);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//堆排
void heap_max(int *a,int start,int end){
    int dad=start;
    int son=2*dad+1;
    while(son<end){
        if(son+1<end&&a[son]<a[son+1]) son++;
        if(a[dad]<a[son]){
            swap(a[dad],a[son]);
            dad=son;
            son=dad*2+1;
        }
    }
}
void arr_heap(int *a){
    int i;
    for(i=n/2-1;i>0;i--){
        heap_max(a,i,n);
    }
    swap(a[0],a[n-1]);//把最大值放到最后
    for(i=N-1;i>1;i--){//由于除了根节点，其他节点都没有改变，所以只需要对根节点进行一个排序即可
        heap_max(a,0,i);
        swap(a[0],a[i-1]);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
//二分查找 查找序列必须是有序序列
//upper_bound,lower_bound c++基本用以上两个函数即可
int bsearch(int *a,int low,int high,int target){
    while(low<=high){
        int mid=(low+high)/2;
        if(a[mid]>target){
            high=mid-1;
        }else if(a[mid]<target){
            low=mid+1;
        }else return mid;
    }
    return -1;//未找到
}