程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> 各類排序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[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

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved