投稿
  1. 高性能架构探索首页
  2. C/C++

内排序

admin • • C/C++ • 阅读 137

各种内排序的性能

内排序

直接插入排序

基本思路

内排序

示例代码

#include <bits/stdc++.h>
#define LL long long
#define Pi acos(-1.0)
#define INF 2147483646
#define eps 1e-9
#define MS 100009
#define mss 17
using namespace std;
// Notice the data size
// Notice the input and output 

int len = 9;
int p[10];

void input(){
    for(int i=0;i<len;i++) scanf("%d",&p[i]);
} 

void InsertSort(){
    for(int i=1;i<len;i++){
        if(p[i]<p[i-1]){ // 该点数据 比 有序区的最后一个数据即最大的数据 大 
            int t = p[i]; // 记录该点数据 
            int j = i; // 记录该点下标 
            do{ // 有序区元素一一右移直到找到合适位置 
                p[j] = p[j-1];
                j--;
            } while(j>0&&t<p[j-1]);
            p[j] = t; // 放入记录的数据 
        }
    }
}

void output(){
    for(int i=0;i<len;i++) printf("%d ",p[i]);
}

int main() {
    input();
    InsertSort();
    output();

    return 0; 
}

/*
input:
5 6 4 9 8 1 3 2 7
6 5 4 9 8 7 3 2 1 

output:
1 2 3 4 5 6 7 8 9
*/

折半插入排序

基本思路

内排序

示例代码

#include <bits/stdc++.h>
#define LL long long
#define Pi acos(-1.0)
#define INF 2147483646
#define eps 1e-9
#define MS 100009
#define mss 17
using namespace std;
// Notice the data size
// Notice the input and output 

int len = 9;
int p[10];

void input(){
    for(int i=0;i<len;i++) scanf("%d",&p[i]);
} 

void BinInsertSort(){
    for(int i=1;i<len;i++){
        if(p[i]<p[i-1]){ // 该点数据 比 有序区的最后一个数据即最大的数据 大 
            int t = p[i]; 
            int l = 0 ,r = i-1;
            while(l<=r){ // 二分查找插入点 
                int mi = (l+r)/2;
                if(t>=p[mi]) l = mi+1;
                else r = mi-1;
            }
            for(int j=i;j>r;j--) p[j] = p[j-1]; //  插入点后数据后移 
            p[r+1] = t;
        }
    }
}

void output(){
    for(int i=0;i<len;i++) printf("%d ",p[i]);
}

int main() {
    input();
    BinInsertSort();
    output();

    return 0; 
}

/*
input:
5 6 4 9 8 1 3 2 7
6 5 4 9 8 7 3 2 1

output:
1 2 3 4 5 6 7 8 9
*/

希尔排序

基本思路

内排序

示例代码

#include <bits/stdc++.h>
#define LL long long
#define Pi acos(-1.0)
#define INF 2147483646
#define eps 1e-9
#define MS 100009
#define mss 17
using namespace std;
// Notice the data size
// Notice the input and output 

int len = 9;
int p[10];

void input(){
    for(int i=0;i<len;i++) scanf("%d",&p[i]);
}

void ShellSort(){
    int d = len/2;
    while(d>=1){
        // 对相邻 d 位置的元素组直接插入排序 
        for(int i=d;i<len;i++){
            int t = p[i];
            int j = i-d;
            while(j>=0&&t<p[j]){
                p[j+d] = p[j];
                j -= d;
            }
            p[j+d] = t;
        }
        d/=2;
    }
}

void output(){
    for(int i=0;i<len;i++) printf("%d ",p[i]);
}

int main() {
    input();
    ShellSort();
    output();

    return 0; 
}

/*
input:
5 6 4 9 8 1 3 2 7
6 5 4 9 8 7 3 2 1

output:
1 2 3 4 5 6 7 8 9
*/

冒泡排序

基本思路

内排序

示例代码

#include <bits/stdc++.h>
#define LL long long
#define Pi acos(-1.0)
#define INF 2147483646
#define eps 1e-9
#define MS 100009
#define mss 17
using namespace std;
// Notice the data size
// Notice the input and output 

int len = 9;
int p[10];

void input(){
    for(int i=0;i<len;i++) scanf("%d",&p[i]);
}

void BubbleSort(){
    int exchange; 
    for(int i=0;i<len-1;i++){
        exchange = 0; // 记录是否有交换记录 
        for(int j=len-1;j>i;j--){ // 将无序区最小的值交换到有序区的顶端 
            if(p[j]<p[j-1]){
                exchange = 1;
                int t = p[j];
                p[j] = p[j-1];
                p[j-1] = t;
            }
        }
        // 若无交换记录 则此时无序区已有序 
        if(exchange == 0) return;
    }
}

void output(){
    for(int i=0;i<len;i++) printf("%d ",p[i]);
}

int main() {
    input();
    BubbleSort();
    output();

    return 0; 
}

/*
input:
5 6 4 9 8 1 3 2 7
6 5 4 9 8 7 3 2 1

output:
1 2 3 4 5 6 7 8 9
*/

快速排序

基本思路

内排序

示例代码

#include <bits/stdc++.h>
#define LL long long
#define Pi acos(-1.0)
#define INF 2147483646
#define eps 1e-9
#define MS 100009
#define mss 17
using namespace std;
// Notice the data size
// Notice the input and output 

int len = 9;
int p[10];

void input(){
    for(int i=0;i<len;i++) scanf("%d",&p[i]);
}

// 左闭右也闭 
void QuickSort(int s,int e){
    if(s>=e) return;
    int i = s ,j = e;
    // 一次划分 
    int t = p[i];
    while(i<j){
        while(j>i&&p[j]>=t) j--;
        p[i] = p[j];
        while(i<j&&p[i]<=t) i++;
        p[j] = p[i];
    }
    p[i] = t;
    // 左右递归 
    QuickSort(s,i-1);
    QuickSort(i+1,e);
}

void output(){
    for(int i=0;i<len;i++) printf("%d ",p[i]);
}

int main() {
    input();
    QuickSort(0,len-1);
    output();

    return 0; 
}

/*
input:
5 6 4 9 8 1 3 2 7
6 5 4 9 8 7 3 2 1

output:
1 2 3 4 5 6 7 8 9
*/

简单选择排序

基本思路

内排序

示例代码

#include <bits/stdc++.h>
#define LL long long
#define Pi acos(-1.0)
#define INF 2147483646
#define eps 1e-9
#define MS 100009
#define mss 17
using namespace std;
// Notice the data size
// Notice the input and output 

int len = 9;
int p[10];

void input(){
    for(int i=0;i<len;i++) scanf("%d",&p[i]);
}

void SelectSort(){
    for(int i=0;i<len-1;i++){
        int k = i;
        for(int j=i+1;j<len;j++){ // 得到区间 i ~ len-1 的最小值下标 
            if(p[j]<p[k]) k = j;
        }
        if(i!=k){ // 交换 
            int t = p[k];
            p[k] = p[i];
            p[i] = t;
        }
    }
}

void output(){
    for(int i=0;i<len;i++) printf("%d ",p[i]);
}

int main() {
    input();
    SelectSort();
    output();

    return 0; 
}

/*
input:
5 6 4 9 8 1 3 2 7
6 5 4 9 8 7 3 2 1

output:
1 2 3 4 5 6 7 8 9
*/

堆排序

基本思路

内排序

示例代码

#include <bits/stdc++.h>
#define LL long long
#define Pi acos(-1.0)
#define INF 2147483646
#define eps 1e-9
#define MS 100009
#define mss 17
using namespace std;
// Notice the data size
// Notice the input and output 

int len = 9;
int p[11];

void input(){
    for(int i=1;i<=len;i++) scanf("%d",&p[i]);
}

void sift(int low,int high){ // 调整堆 
    int i = low ,j = 2*i;
    int t = p[i];
    while(j<=high){
        if(j<high&&p[j+1]>p[j]) j++; // j 指向大孩子 
        if(p[j]>t){ // 父亲小 
            p[i] = p[j];
            i = j;
            j = 2*i;
        }
        else break;
    }
    p[i] = t;
}

void HeapSort(){
    for(int i=len/2;i>=1;i--){ // 初始化堆 
        sift(i,len);
    }
    for(int i=len;i>=2;i--){ // 将最大堆顶元素置于数组后边 
        int t = p[1];
        p[1] = p[i];
        p[i] = t;
        sift(1,i-1); // 调整 
    }
}

void output(){
    for(int i=1;i<=len;i++) printf("%d ",p[i]);
}

int main() {
    input(); // 用数组表示二叉树 
    HeapSort();
    output();

    return 0; 
}

/*
input:
5 6 4 9 8 1 3 2 7
6 5 4 9 8 7 3 2 1

output:
1 2 3 4 5 6 7 8 9
*/

二路归并排序

基本思路

内排序

内排序

啊 这图好啊

示例代码

#include <bits/stdc++.h>
#define LL long long
#define Pi acos(-1.0)
#define INF 2147483646
#define eps 1e-9
#define MS 100009
#define mss 17
using namespace std;
// Notice the data size
// Notice the input and output 

int len = 9;
int p[10];

void input(){
    for(int i=0;i<len;i++) scanf("%d",&p[i]);
}

void Merge(int low,int mid,int high){ // 相邻两个有序子序列归并成一个 
    int i = low ,j = mid+1 ,k = 0; // i ,j 分别为 1 ,2 段下标 
    int *r;
    r = (int*)malloc((high-low+1)*sizeof(int));
    while(i<=mid&&j<=high){
        if(p[i]<p[j]) r[k++] = p[i++];
        else r[k++] = p[j++];
    }
    while(i<=mid) r[k++] = p[i++];
    while(j<=high) r[k++] = p[j++];
    for(i=low,k=0;i<=high;i++,k++)
        p[i] = r[k];
    free(r);
}

void MergeSort(int l,int r){ // 左闭右闭 
    if(l>=r) return;
    int mid = (l+r)/2;
    MergeSort(l,mid);
    MergeSort(mid+1,r);
    Merge(l,mid,r);
}

void output(){
    for(int i=0;i<len;i++) printf("%d ",p[i]);
}

int main() {
    input();
    MergeSort(0,len-1);
    output();

    return 0; 
}

/*
input:
5 6 4 9 8 1 3 2 7
6 5 4 9 8 7 3 2 1

output:
1 2 3 4 5 6 7 8 9
*/

基数排序

基本思路

内排序
内排序
内排序

嘛... 是桶没错了

示例代码

#include <bits/stdc++.h>
#define LL long long
#define Pi acos(-1.0)
#define INF 2147483646
#define eps 1e-9
#define MS 100009
#define mss 17
using namespace std;
// Notice the data size
// Notice the input and output

const int maxn = 8; // 待排序的元素个数 
const int maxw = 3; // 位数最大值 236为 3，1233为 4 
const int maxj = 10; // 进制最大值 10进制则为 10 ，16进制为 16

struct node{
    char val[maxw]; // 用字符串存储数据 
    node *next; 
}*p,*head[maxj],*tail[maxj];

void input(){ // 带头结点尾插法建表 
    node *t,*r;
    p = (node*)malloc(sizeof(node)); // 创建头节点 
    r = p; // 始终指向尾节点 ，开始时指向头节点 
    for(int i=0;i<maxn;i++){
        t = (node*)malloc(sizeof(node)); // 创建数据节点 
        scanf("%s",t->val); // 输入数据 
        r->next = t; // 将 数据节点 t 插在 r 之后 
        r = t; // r 指向尾节点 
    }
    r->next = NULL; // 尾节点 指向 NULL 
}

void RadixSort(){
    p = p->next; // 指向头节点下一个带有数据的指针 
    node *tt;
    for(int i=maxw-1;i>=0;i--){ // 从最低位开始 
        for(int j=0;j<maxj;j++) // 初始化各个链队首尾指针 
            head[j] = tail[j] = NULL;
        while(p!=NULL){
            char k = p->val[i] - '0'; // 找到第 k个链队 
            if(head[k]==NULL){
                head[k] = p;
                tail[k] = p;
            }
            else{
                tail[k]->next = p;
                tail[k] = tail[k]->next;
            }
            p = p->next;
        }
        p = NULL;
        for(int j=0;j<maxj;j++){ // 对每个链表进行串联 
            if(head[j]!=NULL){
                if(p==NULL){
                    p = head[j];
                    tt = tail[j];
                }
                else{
                    tt->next = head[j];
                    tt = tail[j];
                }
            }
        }
        tt->next = NULL;
    } 
}

void output(){
    while(p!=NULL){
        printf("%s ",p->val);
        p = p->next;
    }
}

int main() {
    input();
    RadixSort();
    output();

    return 0; 
}

/*
input:
369 367 167 239 237 138 230 139

output:
138 139 167 230 237 239 367 369

*/

原文链接: https://www.cnblogs.com/Tecode/p/13266366.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;

也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬

    内排序

原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/363810

非原创文章文中已经注明原地址，如有侵权，联系删除

关注公众号【高性能架构探索】，第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处！

赞 (0)
adminadmin
0 0
上一篇 2023年3月2日 下午3:13
下一篇 2023年3月2日 下午3:14

相关推荐