当前位置:编程学习 > C/C++ >>

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

没有加什么模板之类的,全用的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

补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,