各类排序C++实现(冒泡,选择,插入,快排,归并,堆排)

来源:岁月联盟 编辑:exp 时间:2012-07-06

没有加什么模板之类的,全用的int型,下标有的从0开始有的从1开始
1.插入
[cpp] 
#include <iostream> 
#include <cstdio> 
#define N 1005 
using namespace std; 
int n, a[N]; 
void InsertSort(int a[], int n) //下标从0开始 

    int i, j, temp; 
    for(i = 1; i < n; i++) 
    { 
        temp = a[i]; 
        for(j = i; j > 0 && temp < a[j - 1]; j--) a[j] = a[j - 1]; 
        a[j] = temp; 
    } 

int main() 

    int i; 
    scanf("%d", &n); 
    for(i = 0; i < n; i++) scanf("%d", &a[i]); 
    InsertSort(a, n); 
    for(i = 0; i < n; i++) printf("%d/n", a[i]); 
    return 0; 


2.选择

[cpp] 
#include <iostream> 
using namespace std; 
int a[105]; 
//下标从1开始 
void SelectSort(int a[], int n) 

    int i, j, pos; 
    for(i = 1; i < n; i++) 
    { 
        pos = i; 
        for(j = i; j <= n; j++) 
        { 
            if(a[j] < a[pos]) 
            pos = j; 
        } 
        int temp = a[pos]; 
        a[pos] = a[i]; 
        a[i] = temp; 
    } 

int main() 

    int n, i; 
    cin >> n; 
    for(i = 1; i <= n; i++) cin >> a[i]; 
    SelectSort(a, n); 
    for(i = 1; i <= n; i++) 
    cout << a[i] << " "; 
    cout << endl; 
    return 0; 


3.冒泡
[cpp] 
#include <iostream> 
using namespace std; 
int a[105]; 
//下标从1开始 
void BubbleSort(int a[], int n) 

    int i, j; 
    for(i = 1; i < n; i++) 
    { 
        for(j = 1; j <= n - i; j++) 
        { 
            if(a[j] > a[j + 1]) 
            { 
                int temp = a[j + 1]; 
                a[j + 1] = a[j]; 
                a[j] = temp; 
            } 
        } 
    } 

int main() 

    int n, i; 
    cin >> n; 
    for(i = 1; i <= n; i++) 
        cin >> a[i]; 
    BubbleSort(a, n); 
    for(i = 1; i <= n; i++) 
    cout << a[i] << " "; 
    cout << endl; 
    return 0; 


4.快排
[cpp] 
#include <iostream> 
using namespace std; 
int n; 
int a[105]; 
//下标从0开始 
int partition(int a[], int low, int high) 
{//快速排序中的一趟 
    int key;//作为枢轴来使用 
    key = a[low]; 
    while(low < high) 
    { 
        while(low < high && a[high] >= key) 
        --high; 
        a[low] = a[high]; 
        while(low < high && a[low] <= key) 
        ++low; 
        a[high] = a[low]; 
    } 
    a[low] = key; 
    return low; 

void qsort(int a[], int low, int high) 
{//快速排序的递归形式 
    int loc; 
    if(low < high) 
    { 
        loc = partition(a, low, high);//一趟排序结果的调用 
        qsort(a, low, loc - 1); 
        qsort(a, loc + 1, high); 
    } 

int main() 

    int i; 
    cin >> n; 
    for(i = 0; i < n; i++) cin >> a[i]; 
    qsort(a, 0, n - 1); 
    for(i = 0; i < n; i++) cout << a[i] << " "; 
    cout << endl; 
    return 0; 


5.归并
[cpp] 
#include <iostream> 
#define N 105 
using namespace std; 
int n; 
int a[N], t[N]; 
/* 归并 */ 
//下标从0开始 
void Merge(int a[], int l, int m, int r) 

    /* p指向输出区间 */ 
    int p = 0; 
    /* i、j指向2个输入区间 */ 
    int i = l, j = m + 1; 
    /* 2个输入区间都不为空时 */ 
    while(i <= m && j <= r) 
    {/* 取关键字小的记录转移至输出区间 */ 
        if (a[i] > a[j]) 
            t[p++] = a[j++]; 
        else 
            t[p++] = a[i++]; 
    } 
    /* 将非空的输入区间转移至输出区间 */ 
    while(i <= m) t[p++] = a[i++]; 
    while(j <= r) t[p++] = a[j++]; 
    /* 归并完成后将结果复制到原输入数组 */ 
    for (i = 0; i < p; i++) 
        a[l + i] = t[i]; 

 
/* 归并排序 */ 
void MergeSort(int a[], int l, int r) 

    int m; 
    if (l < r) 
    {/* 将长度为n的输入序列分成两个长度为n/2的子序列 */ 
        m = (l + r) / 2; 
        /* 对两个子序列分别进行归并排序 */ 
        MergeSort(a, l, m); 
        MergeSort(a, m + 1, r); 
        /* 将2个排好的子序列合并成最终有序序列 */ 
        Merge(a, l, m, r); 
    } 

int main() 

    int i; 
    cin >> n; 
    for(i = 0; i < n; i++) cin >> a[i]; 
    MergeSort(a, 0, n - 1); 
    for(i = 0; i < n; i++) cout << a[i] << " "; 
    cout << endl; 
    return 0; 


6.堆排
[cpp] 
#include <iostream> 
using namespace std; 
int n; 
int a[105]; 
//下标从1开始 
void HeapAdjust(int A[], int a, int z)  

    int i, j; 
    for(i = a, j = 2 * i; j <= z; i = j, j = 2 * i) 
    { //i为父,j为子 
        if(j < z && A[j + 1] > A[j]) j++;   //大顶堆,沿大孩子方向下行 
        if(A[i] < A[j]) 
            swap(A[i], A[j]); 
        else break; 
    } 

void HeapSort(int A[], int n) 

    int i; 
    for(i = n / 2; i >= 1; i--) //从倒数第一个非叶子结点,自下而上堆化 
        HeapAdjust(A, i, n); 
    for(i = n; i > 1; i--) 
    { //交换A[1]与最后元素A[i](i=n, ..., 1), 再堆化 
        swap(A[1], A[i]); 
        HeapAdjust(A, 1, i - 1); 
    } 

int main() 

    int i; 
    cin >> n; 
    for(i = 1; i <= n; i++) 
    cin >> a[i]; 
    HeapSort(a, n); 
    for(i = 1; i <= n; i++) cout << a[i] << " "; 
    cout << endl; 
    return 0; 

作者:sdj222555

下一篇:hdu 1003 Max Sum