IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓ 		图片批量下载器
↓批量下载图片,美女图库↓ 		图片自动播放器
↓图片自动播放器↓ 		一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> 常用的排序算法（C语言） -> 正文阅读

[数据结构与算法]常用的排序算法（C语言）

冒泡排序 Bubble Sort

基本思想：交换排序，两两比较相邻记录的关键字，如果反序则交换，知道没有反序的记录为止。

(对相邻的元素进行两两比较，顺序相反则进行交换)

原始版：

#include <stdio.h>

void BubbleSort(int a[], int n)
{
    for(int i=0; i<n; ++i)
    {
        for(int j= n-2; j>=i; --j)
        {
            if(a[j] > a[j+1])
                swap(a[j], a[j+1]);
        }
    }
}

int main()
{
    int a[] = {50, 10, 90, 30, 70, 40, 80, 60, 20};
    //int a[] = {4, 10, 3, 5, 1, 2};
    int n = sizeof(a)/sizeof(a[0]);
    BubbleSort(a, n);
    for(int i=0; i<n; ++i)
        printf("%d\n",a[i]);
    return 0;
}

改进版：

#include <stdio.h>

void BubbleSort2(int a[], int n)
{
    bool flag = true;
    for(int i=0; i<n && flag; ++i)
    {
        flag = false;
        for(int j= n-2; j>=i; --j)
        {
            if(a[j] > a[j+1])
            {
                swap(a[j], a[j+1]);
                flag = true;
            }
        }
    }
}

int main()
{
    int a[] = {50, 10, 90, 30, 70, 40, 80, 60, 20};
    //int a[] = {4, 10, 3, 5, 1, 2};
    int n = sizeof(a)/sizeof(a[0]);
    BubbleSort2(a, n);
    for(int i=0; i<n; ++i)
        printf("%d\n",a[i]);
    return 0;
}
比较次数数据交换时间复杂度
最好情况n-10O(n)
最坏情况n(n-1)/2n(n-1)/2O(n^2)

简单选择排序 Simple Selection Sort

通过n-i次关键字之间的比较，在n-i+1个记录中选出关键字最小的记录，并和第i个记录交换之

#include <stdio.h>
void SelectionSort(int a[], int n)
{
    int min;
    for(int i=0; i<n; ++i)
    {
         min = i;
         for(int j=i+1; j<n; ++j)
         {
             if(a[min] > a[j])
                min = j;
         }
         if(min != i)
            swap(a[i],a[min]);
    }
}

int main()
{
    int a[] = {50, 10, 90, 30, 70, 40, 80, 60, 20};
    //int a[] = {4, 10, 3, 5, 1, 2};
    int n = sizeof(a)/sizeof(a[0]);
    SelectionSort(a, n);
    for(int i=0; i<n; ++i)
        printf("%d\n",a[i]);
    return 0;
}
比较次数数据交换时间复杂度
最好情况n(n-1)/20O(n^2)
最坏情况n(n-1)/2n-1O(n^2)

直接插入排序 Straight Insertion Sort

将一个记录插入到已经排序好的有序表中，从而得到一个新的、记录数增1的有序表

#include <stdio.h>
void InsertSort(int a[], int n)
{
    int tmp, j;
    for(int i=1; i<n; ++i)
    {
        tmp = a[i];
        for(j=i-1; j>=0 && a[j]>tmp; --j)
        {
            a[j+1] = a[j];
        }
        a[j+1] = tmp;
    }
}

int main()
{
    int a[] = {50, 10, 90, 30, 70, 40, 80, 60, 20};
    //int a[] = {4, 10, 3, 5, 1, 2};
    int n = sizeof(a)/sizeof(a[0]);
    InsertSort(a, n);
    for(int i=0; i<n; ++i)
        printf("%d\n",a[i]);
    return 0;
}
比较次数数据交换时间复杂度
最好情况n-10O(n)
最坏情况(n+2)(n-1)/2(n+4)(n-1)/2O(n^2)
平均情况(n^2)/4(n^2)/4O(n^2)

希尔排序 Shell Sort

希尔排序实际上是一种特殊的插入排序
将相距某个“增量”的记录组成一个子序列，保证在子序列内分别进行直接插入排序后得到的结果是基本有序而不是局部有序

#include <stdio.h>
void ShellSort(int a[], int n)
{
    int increment = n;
    int j;
    do
    {
        increment = increment/3+1;
        for(int i=increment; i<n; ++i)
        {
            int tmp = a[i];
            for(j=i-increment; j>=0 && a[j]>tmp; j-=increment)
            {
                a[j+increment] = a[j];
            }
            a[j+increment] = tmp;
        }
    }
    while(increment>1);
}

int main()
{
    int a[] = {50, 10, 90, 30, 70, 40, 80, 60, 20};
    //int a[] = {4, 10, 3, 5, 1, 2};
    int n = sizeof(a)/sizeof(a[0]);
    ShellSort(a, n);
    for(int i=0; i<n; ++i)
        printf("%d\n",a[i]);
    return 0;
}

时间复杂度O(n^(3/2))

归并排序 Merging Sort

最好、最坏与平均时间复杂度：O(nlogn)
空间复杂度：O(n+logn)
稳定的排序
递归方法：

#include <stdio.h>
#define MAX 100

void Merge(int tmp[], int des[], int low, int mid, int high)
{
    int i = low, j = mid + 1, k = low;
    while((i<=mid) && (j<=high))
    {
        if(tmp[i]<tmp[j])
            des[k++] = tmp[i++];
        else
            des[k++] = tmp[j++];
    }
    while(i <= mid)
    {
        des[k++] = tmp[i++];
    }
    while(j <= high)
    {
        des[k++] = tmp[j++];
    }
}

void MSort(int src[], int des[], int low, int high)
{
    if(low == high)
        des[low] = src[low];
    else
    {
        int tmp[MAX];
        int mid = (low + high)/2;
        MSort(src, tmp, low, mid);
        MSort(src, tmp, mid+1, high);
        Merge(tmp, des, low, mid, high);

    }
}

void MergeSort(int a[], int len)
{
        MSort(a, a, 0, len-1);//下标
}

int main()
{
    int a[] = {50, 10, 90, 30, 70, 40, 80, 60, 20};
    //int a[] = {4, 10, 3, 5, 1, 2};
    int len = sizeof(a)/sizeof(*a);
    MergeSort(a, len);
    for(int i=0; i<len; ++i)
        printf("%d\n",a[i]);
    return 0;
}

堆排序 Heap Sort

堆排序是一种选择排序，整体主要由构建初始堆+交换堆顶元素和末尾元素并重建堆两部分组成。其中构建初始堆经推导复杂度为O(n)，在交换并重建堆的过程中，需交换n-1次，而重建堆的过程中，根据完全二叉树的性质，[log2(n-1),log2(n-2)…1]逐步递减，近似为nlogn。所以堆排序时间复杂度一般认为就是O(nlogn)级。
堆排序

代码一

#include <stdio.h>

void swap(int arr[], int i, int j)
{
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}

void heapify(int tree[] , int n, int i) //堆化，堆调整
{
    if(i >= n)
        return;
    int c1 = 2*i + 1;
    int c2 = 2*i + 2;
    int max = i;
    if(c1 < n && tree[c1] > tree[max])
        max = c1;
    if(c2 < n && tree[c2] > tree[max])
        max = c2;
    if(max != i)
    {
        swap(tree, max, i);
        heapify(tree, n, max);
    }
}

void build_heap(int tree[], int n) //建立堆
{
    int last_node = n - 1;
    int first = (last_node - 1)/2;
    for(int i=first; i>=0; --i)
        heapify(tree, n, i);
}

void HeapSort(int tree[], int n) //堆排序
{
    build_heap(tree, n);
    for(int i=n-1; i>=0; --i)
    {
        swap(tree, i, 0);
        heapify(tree, i, 0);
    }
}

int main()
{
    int tree[] = {50, 10, 90, 30, 70, 40, 80, 60, 20};
    //int tree[] = {4, 10, 3, 5, 1, 2};
    int n = sizeof(tree)/sizeof(*tree);
    HeapSort(tree, n);
    for(int i=0; i<n; ++i)
        printf("%d\n",tree[i]);
    return 0;
}

运行时间主要是消耗在初始构建堆和在重建堆时的反复筛选上。
对于每个非终端节点，最多进行两次比较和互换操作，构建堆的时间复杂度O(n)
重建堆的时间复杂度O(nlogn)
最好、最坏和平均时间复杂度：O(nlogn)
不稳定

代码二

#include <stdio.h>

void swap(int arr[], int i, int j)
{
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}

void HeapAdjust(int tree[], int index, int len)
{
    int tmp = tree[index];
    for (int j = 2*index + 1; j < len; j = 2*j + 1) {
        if (j + 1 < len && tree[j] < tree[j + 1])
            ++j;
        
        if (tmp > tree[j])
            break;

        tree[index] = tree[j];
        index = j;
    }
    tree[index] = tmp;
}

void HeapSort(int tree[], int len)
{
    //首先构建初始堆，每个元素的值大于其左右子树
    for (int i = len/2 -1; i >= 0 ;--i)
        HeapAdjust(tree, i, len);
    
    /* 之后将堆顶元素（即最大元素）与末尾元素交换 */
    /* 排除末尾元素，让剩下的元素重新构造堆 */
    for (int i = len -1; i > 0; --i) {
        swap(tree, 0 , i);
        HeapAdjust(tree, 0, i);
    }
}

int main()
{
    //int tree[] = {50, 10, 90, 30, 70, 40, 80, 60, 20};
    int tree[] = {4, 10, 3, 5, 1, 2};
    int len = sizeof(tree)/sizeof(tree[0]);
    HeapSort(tree, len);
    for (int i=0; i < len; ++i)
        printf("%d\n", tree[i]);
    return 0;
}

快速牌序 Quick Sort

冒泡排序的升级，交换排序。
基本思想：通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键子均比另一部分记录的关键字小，则可分别对这两部分记录进行排序，以达到整个序列有序的目的。

代码一

#include <stdio.h>

int partition(int a[], int low, int high)
{
    int key = a[low];
    while(low<high)
    {
        while(low<high && a[high]>=key)
            --high;
        swap(a[high], a[low]);
        while(low<high && a[low]<=key)
            ++low;
        swap(a[high], a[low]);
    }
    return low;
}

void QSort(int a[], int low, int high)
{
    int pivot;
    if(low < high)
    {
        pivot = partition(a, low, high);
        QSort(a, low, pivot-1);
        QSort(a, pivot+1, high);
    }
}

void QuickSort(int a[], int n)
{
    QSort(a, 0, n-1);
}

int main()
{
    int a[] = {50, 10, 90, 50, 70, 40, 80, 60, 20};
    //int a[] = {4, 10, 3, 5, 1, 2};
    int n = sizeof(a)/sizeof(a[0]);
    QuickSort(a, n);
    for(int i=0; i<n; ++i)
        printf("%d\n",a[i]);
    return 0;
}

改进版

#include <stdio.h>

int partition(int a[], int low, int high)
{
    // 三数取中
    int m = (high - low)/2 + low;
    if(a[low] > a[high])
        swap(a[low], a[high]);
    if(a[m]> a[high])
        swap(a[m], a[high]);
    if(a[m] > a[low])
        swap(a[m], a[low]);
    int key = a[low];
    int tmp = key;
    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] = tmp;
    return low;
}

void QSort(int a[], int low, int high)
{
    int pivot;
    if(low<high)
    {
        pivot = partition(a, low, high);
        QSort(a, low, pivot-1);
        QSort(a, pivot+1, high);
    }
}

void QuickSort(int a[], int n)
{
    QSort(a, 0, n-1);
}

int main()
{
    int a[] = {50, 10, 90, 50, 70, 40, 80, 60, 20};
    //int a[] = {4, 10, 3, 5, 1, 2};
    int n = sizeof(a)/sizeof(a[0]);
    QuickSort(a, n);
    for(int i=0; i<n; ++i)
        printf("%d\n",a[i]);
    return 0;
}

链表排序

单链表的归并排序：时间复杂度O(nlogn)，空间复杂度O(1)
利用归并排序：

#include <bits/stdc++.h>
using namespace std;

struct ListNode
{
    int val;
    ListNode* next;
    ListNode(int x):val(x),next(NULL){}
};

ListNode* MergeList(ListNode* headA, ListNode* headB)
{
    ListNode *newhead = new ListNode(0);
    ListNode *tail = newhead;
    while(headA != NULL && headB != NULL)
    {
        if(headA->val < headB->val)
        {
            tail->next = headA;
            tail = headA;
            headA = headA->next;
        }
        else
        {
            tail->next = headB;
            tail = headB;
            headB = headB->next;
        }
    }
    while(headA != NULL)
    {
        tail->next = headA;
        tail = headA;
        headA = headA->next;
    }
    while(headB != NULL)
    {
        tail->next = headB;
        tail = headB;
        headB = headB->next;
    }
    ListNode* rehead = newhead->next;
    delete newhead;
    return rehead;
}

ListNode* MsortList(ListNode* head)
{
    if(head == NULL || head->next == NULL)
        return head;

    ListNode *slow = head;
    ListNode *fast = head->next;
    
    while(fast != NULL && fast->next != NULL) //找到中间节点，再分半
    {
        slow = slow->next;
        fast = fast->next->next;
    }
    
    ListNode *h2 = slow->next;
    slow->next = NULL;
    ListNode *p1 = MsortList(head); //递归
    ListNode *p2 = MsortList(h2);   //递归
    return MergeList(p1, p2);
}

int main()
{
    ListNode *head = new ListNode(4);
    head->next = new ListNode(2);
    head->next->next = new ListNode(1);
    head->next->next->next = new ListNode(3);
    head->next->next->next->next = new ListNode(6);
    head->next->next->next->next->next = new ListNode(5);
    head = MsortList(head);
    while(head != NULL)
    {
        cout<<head->val<<endl;
        head = head->next;
    }
    return 0;
}
  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用：海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题＜有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2021-08-28 09:36:03  更:2021-08-28 09:37:26 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年12日历 -2024/12/29 8:32:27-

图片自动播放器
↓图片自动播放器↓ 		TxT小说阅读器
↓语音阅读,小说下载,古典文学↓ 		一键清除垃圾
↓轻轻一点,清除系统垃圾↓ 		图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码
数据统计