1. Toy模板网首页
  2. > Toy博客

数据结构与算法之排序（更新中。。。）

9月前 作者：笑着的程序员 分类：Toy博客 阅读(33) 违法举报

这篇具有很好参考价值的文章主要介绍了数据结构与算法之排序（更新中。。。）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

数据结构与算法之排序（经典排序算法）

1、冒泡排序

代码分析：

这段代码实现了冒泡排序算法，其时间复杂度为 O ( n 2 ) O(n^2) O(n2)。冒泡排序是一种简单的排序算法，它重复地遍历要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。遍历数列的工作是重复地进行直到没有再需要交换的元素，也就是说该数列已经排序完成。

在这段代码中，bubbleSort函数中的外层循环执行了n次，内层循环执行了n-1次，因此总的时间复杂度为 O ( n 2 ) O(n^2) O(n2)。虽然冒泡排序的时间复杂度较高，但是它实现简单，对于小规模的数据排序效果还是不错的。

代码解读：

这段代码实现了冒泡排序算法。冒泡排序是一种简单的排序算法，它重复地遍历要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。遍历数列的工作是重复地进行直到没有再需要交换的元素，也就是说该数列已经排序完成。

在这段代码中，swap函数实现了两个元素的交换，bubble函数实现了一次冒泡排序，bubbleSort函数则是对整个数组进行冒泡排序。其中，bubble函数返回一个布尔值，表示是否进行了交换操作，如果没有进行交换操作，说明数组已经排好序了，可以直接退出循环。

在main函数中，首先输出了原始数组，然后调用bubbleSort函数对数组进行排序，最后输出排序后的数组。可以看到，排序后的数组是按照从小到大的顺序排列的。

值得注意的是，这段代码中使用了模板类，可以对不同类型的数组进行排序。同时，使用了STL中的foreach函数，可以方便地对数组进行遍历输出。

#include <iostream>
#include <algorithm>

template<class T>
void swap (T& a, T& b)
{
    T temp = a;
    a = b;
    b = temp;
}

template<class T>
bool bubble (T a[], int n)
{
    bool swapped = false;
    for (int i = 0; i < n - 1; ++i)
    {
        if (a[i] > a[i+1])//如果数组已经是排序的话，则排序就终止了
        {
            swap(a[i], a[i+1]);
            swapped = true;
        }
    }
    return swapped;
}

template<class T>
void bubbleSort(T a[], int n)
{
    for (int i = n; i > 1 && bubble(a, i); --i); //最后只剩一个数字就是排好序的，故到a>1即可
}
void Show(const int& v)
{
    std::cout << v << " ";
}

int main()
{
    int arr[]{ 6, 5, 8, 4, 3, 1 };
    for (auto x : arr)
        std::cout << x << " ";
    //std::for_each(arr, arr + sizeof(arr) / sizeof(int), Show);
    std::cout << "\n";
    bubbleSort(arr, sizeof(arr) / sizeof(int));
    std::for_each(arr, arr + sizeof(arr) / sizeof(int), Show);
    std::cout << std::endl;
    return 0;
}

2、桶排序

#include<iterator>
#include<iostream>
#include<vector>
using std::vector;

/*****************
桶排序：将值为i的元素放入i号桶，最后依次把桶里的元素倒出来。
桶排序序思路：
1. 设置一个定量的数组当作空桶子。
2. 寻访序列，并且把项目一个一个放到对应的桶子去。
3. 对每个不是空的桶子进行排序。
4. 从不是空的桶子里把项目再放回原来的序列中。
假设数据分布在[0，100)之间，每个桶内部用链表表示，在数据入桶的同时插入排序，然后把各个桶中的数据合并。
*****************/


const int BUCKET_NUM = 10;

struct ListNode{
    explicit ListNode(int i=0):mData(i),mNext(NULL){}
    ListNode* mNext;
    int mData;
};

ListNode* insert(ListNode* head,int val){
    ListNode dummyNode;
    ListNode *newNode = new ListNode(val);
    ListNode *pre,*curr;
    dummyNode.mNext = head;
    pre = &dummyNode;
    curr = head;
    while(NULL!=curr && curr->mData<=val){
        pre = curr;
        curr = curr->mNext;
    }
    newNode->mNext = curr;
    pre->mNext = newNode;
    return dummyNode.mNext;
}


ListNode* Merge(ListNode *head1,ListNode *head2){
    ListNode dummyNode;
    ListNode *dummy = &dummyNode;
    while(NULL!=head1 && NULL!=head2){
        if(head1->mData <= head2->mData){
            dummy->mNext = head1;
            head1 = head1->mNext;
        }else{
            dummy->mNext = head2;
            head2 = head2->mNext;
        }
        dummy = dummy->mNext;
    }
    if(NULL!=head1) dummy->mNext = head1;
    if(NULL!=head2) dummy->mNext = head2;

    return dummyNode.mNext;
}

void BucketSort(int n,int arr[]){
    vector<ListNode*> buckets(BUCKET_NUM,(ListNode*)(0));
    for(int i=0;i<n;++i){
        int index = arr[i]/BUCKET_NUM;
        ListNode *head = buckets.at(index);
        buckets.at(index) = insert(head,arr[i]);
    }
    ListNode *head = buckets.at(0);
    for(int i=1;i<BUCKET_NUM;++i){
        head = Merge(head,buckets.at(i));
    }
    for(int i=0;i<n;++i){
        arr[i] = head->mData;
        std::cout << arr[i] << " ";
        head = head->mNext;
    }
    std::cout << std::endl;
}


int main()
{
    int a[] = {56, 89, 24, 6, 18, 5, 1, 99, 63};
    BucketSort(sizeof(a)/sizeof(int), a);
    return 0;
}

3、插入排序

#include <iostream>
#include <algorithm>
template<class T>
void insert(T a[], int n, const T& x)
{
    int i;
    for (i = n - 1; i >= 0 && x < a[i]; --i)
        a[i + 1] = a[i];
    a[i + 1] = x;//因为退出for循环之后i已经减了1
}

template<class T>
void insertionSort(T a[], int n)
{
    for (int i = 1; i < n; ++i)
    {
        T t = a[i];
        insert(a, i, t);//依次插入到恰好比下一个数字小的地方
    }
}

void Show(const int& v)
{
    std::cout << v << " ";
}

int main()
{
    int arr[]{ 6, 5, 8, 4, 3, 1 };
    for (auto x : arr)
        std::cout << x << " ";
    //std::for_each(arr, arr + sizeof(arr) / sizeof(int), Show);
    std::cout << "\n";
    insertionSort(arr, sizeof(arr) / sizeof(int));
    std::for_each(arr, arr + sizeof(arr) / sizeof(int), Show);
    std::cout << std::endl;
    return 0;
}

4、归并排序

递归版：

//完整代码

#include <iostream>

using namespace std;

template<typename T>
void merge_sort_recursive(T arr[], T reg[], int start, int end) {
    if (start >= end)
        return;
    int len = end - start, mid = (len >> 1) + start;
    int start1 = start, end1 = mid;
    int start2 = mid + 1, end2 = end;
    merge_sort_recursive(arr, reg, start1, end1);
    merge_sort_recursive(arr, reg, start2, end2);
    int k = start;
    while (start1 <= end1 && start2 <= end2)
        reg[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];
    while (start1 <= end1)
        reg[k++] = arr[start1++];
    while (start2 <= end2)
        reg[k++] = arr[start2++];
    for (k = start; k <= end; k++)
        arr[k] = reg[k];
}
//整數或浮點數皆可使用,若要使用物件(class)時必須設定"小於"(<)的運算子功能
template<typename T>
void merge_sort(T arr[], const int len) {
    T *reg = new T[len];
    merge_sort_recursive(arr, reg, 0, len - 1);
    delete[] reg;
}
void showAges(const int& age)
{
    std::cout << age << '\t';
}
void Test1()
{
    int ages[] = { 10, 9, 45, 30, 28, 90, 38, 30, 30, 45, 45 };
    merge_sort(ages, sizeof(ages) / sizeof(int));
    std::cout << "The sorted ages is:\n";
    for (auto x : ages)
        showAges(x);
    //    std::cout << x << '\t';

}
int main()
{
    Test1();
    return 0;
}

迭代版：

//完整代码

#include <iostream>

using namespace std;

/*****************
    迭代版
*****************/
//整數或浮點數皆可使用,若要使用物件(class)時必須設定"小於"(<)的運算子功能
template<typename T>
void merge_sort(T arr[], int len) {
    T* a = arr;
    T* b = new T[len];
    for (int seg = 1; seg < len; seg += seg) {
        for (int start = 0; start < len; start += seg + seg) {
            int low = start, mid = min(start + seg, len), high = min(start + seg + seg, len);
            int k = low;
            int start1 = low, end1 = mid;
            int start2 = mid, end2 = high;
            while (start1 < end1 && start2 < end2)
                b[k++] = a[start1] < a[start2] ? a[start1++] : a[start2++];
            while (start1 < end1)
                b[k++] = a[start1++];
            while (start2 < end2)
                b[k++] = a[start2++];
        }
        T* temp = a;
        a = b;
        b = temp;
    }
    if (a != arr) {
        for (int i = 0; i < len; i++)
            b[i] = a[i];
        b = a;
    }
    delete[] b;
}

void showAges(const int& age)
{
    std::cout << age << '\t';
}
void Test1()
{
    int ages[] = { 10, 9, 45, 30, 28, 90, 38, 30, 30, 45, 45 };
    merge_sort(ages, sizeof(ages) / sizeof(int));
    std::cout << "The sorted ages is:\n";
    for (auto x : ages)
        showAges(x);
    //    std::cout << x << '\t';

}
int main()
{
    Test1();
    return 0;
}

5、快速排序

#include <iostream>
#include <algorithm>
#include <exception>
#include <cstdlib>
#include <ctime>//time
template<class T>
void swap(T* a, T* b)//注意用指针构造交换函数时，交换的是指针指向的值
{
    T temp = *a;
    *a = *b;
    *b = temp;
}
int RandomInRange(int st, int en)
{
    srand(unsigned(time(0)));//把当前时间作为随机数种子
    return st + rand() % (en - st + 1);
}
int Partition(int data[], int length, int start, int end)
{
    if (data == nullptr || length <= 0 || start < 0 || end >= length)
    {
        throw "Invalid Parameters";
    }
    int index = RandomInRange(start, end);
    swap(&data[index], &data[end]);
    int small = start - 1;
    for (index = start; index < end; ++index)
    {
        if (data[index] < data[end])//当条件不成立时index增加，small不变
        {
            ++small;
            if (small != index)
                swap(&data[index], &data[small]);
        }
    }
    ++small;
    swap(&data[small], &data[end]);
    return small;//返回的结果是左边比data[end]小，右边比data[end]大的数
}

void QuickSort(int data[], int length, int start, int end)
{
    if (start == end)
        return;
//**********************************这部分是判断数组是否已经按升序排好序，排好的话就直接终止，这样就防止出现最糟糕的情况
    bool sorted = true;   //《剑指offer》p81
    for (int i = start; i < end; ++i)
    {
        if (data[i] > data[i + 1])//如果数组已经是排序的话，则排序就终止了
        {
            sorted = false;
        }
    }
    if (sorted)
        return;
//****************************************************************************************
    int index = Partition(data, length, start, end);
    if (index > start)
        QuickSort(data, length, start, index - 1);
    if (index < end)
        QuickSort(data, length, index + 1, end);
}

void Show(const int& v)
{
    std::cout << v << " ";
}

int main()
{
    int arr[]{ 6, 5, 8, 4, 3, 1 };
    for (auto x : arr)
        std::cout << x << " ";
    //std::for_each(arr, arr + sizeof(arr) / sizeof(int), Show);
    std::cout << "\n";
    QuickSort(arr, sizeof(arr) / sizeof(int), 0, sizeof(arr) / sizeof(int) - 1);
    std::for_each(arr, arr + sizeof(arr) / sizeof(int), Show);
    return 0;
}

6、选择排序

#include <iostream>
#include <algorithm>
template<class T>
void swap (T& a, T& b)
{
    T temp = a;
    a = b;
    b = temp;
}
template<class T>
void selectionSort(T a[], int n)
{
    bool sorted = false;
    for (int size = n; !sorted && (size > 1); size--)
    {
        int indexOfMax = 0;
        sorted = true;
        for (int i = 1; i < size; ++i)
        {
            if (a[indexOfMax] <= a[i])
                indexOfMax = i;
            else
                sorted = false;//无序的
        }
        swap (a[indexOfMax], a[size - 1]);//如果是无序的，则每次循环将最大值放在最后一位
    }
}


void Show(const int& v)
{
    std::cout << v << " ";
}

int main()
{
    int arr[]{ 6, 5, 8, 4, 3, 1 };
    for (auto x : arr)
        std::cout << x << " ";
    //std::for_each(arr, arr + sizeof(arr) / sizeof(int), Show);
    std::cout << "\n";
    selectionSort(arr, sizeof(arr) / sizeof(int));
    std::for_each(arr, arr + sizeof(arr) / sizeof(int), Show);
    return 0;
}

桶排序的一个示例（《剑指offer》中的一个问题）

后面会补充剑指offer相关的内容文章来源地址https://www.toymoban.com/news/detail-446414.html

#include <iostream>
#include <exception>

void SortAges(int ages[], int length)
{
	if (ages == nullptr || length <= 0)
		return;
	const int oldestAge = 99;
	int timesOfAge[oldestAge + 1];
	for (int i = 0; i < oldestAge; ++i)
		timesOfAge[i] = 0;
	for (int i = 0; i < length; ++i)
	{
		int age = ages[i];
		if (age < 0 || age > oldestAge)
			throw new std::exception("age out og range");
		++timesOfAge[age];
	}
	int index = 0;
	for (int i = 0; i <= oldestAge; ++i)
	{
		for (int j = 0; j < timesOfAge[i]; ++j)
		{
			ages[index] = i;
			++index;
		}
	}
}
void showAges(const int& age)
{
	std::cout << age << '\t';
}
void Test1()
{
	int ages[] = { 10, 9, 45, 30, 28, 90, 38, 30, 30, 45, 45 };
	SortAges(ages, sizeof(ages) / sizeof(int));
	std::cout << "The sorted ages is:\n";
	for (auto x : ages)
		showAges(x); 
	//	std::cout << x << '\t';
	
}
int main()
{
	Test1();
	return 0;
}

到了这里，关于数据结构与算法之排序（更新中。。。）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 数据结构和算法笔记4：排序算法-归并排序

    数据结构和算法笔记4：排序算法-归并排序

    归并排序算法完全遵循分治模式。直观上其操作如下： 分解：分解待排序的n个元素的序列成各具n/2个元素的两个子序列。 解决：使用归并排序递归地排序两个子序列。 合并：合并两个已排序的子序列以产生已排序的答案。 我们直接来看例子理解算法的过程，下面是要排序

    2024年01月21日
    浏览(62)
  • 【数据结构与算法】十大经典排序算法-插入排序

    【数据结构与算法】十大经典排序算法-插入排序

    🌟 个人博客： www.hellocode.top 🏰 Java知识导航： Java-Navigate 🔥 CSDN： HelloCode. 🌞 知乎 ：HelloCode 🌴 掘金 ：HelloCode ⚡如有问题，欢迎指正，一起学习~~ 插入排序（Insertion Sort）是一种简单直观的排序算法，其基本思想是将一个记录插入到已排好序的有序序列中，直到所有记录

    2024年02月13日
    浏览(80)
  • 【数据结构与算法】十大经典排序算法-快速排序

    【数据结构与算法】十大经典排序算法-快速排序

    🌟 个人博客： www.hellocode.top 🏰 Java知识导航： Java-Navigate 🔥 CSDN： HelloCode. 🌞 知乎 ：HelloCode 🌴 掘金 ：HelloCode ⚡如有问题，欢迎指正，一起学习~~ 快速排序（Quick Sort）是一种高效的排序算法，是对冒泡排序的优化。它采用分治法（Divide and Conquer）的思想，将待排序序列

    2024年02月13日
    浏览(62)
  • 数据结构——排序算法之快速排序

    数据结构——排序算法之快速排序

        个人主页： 日刷百题 系列专栏 ： 〖C/C++小游戏〗 〖Linux〗 〖数据结构〗   〖C语言〗 🌎 欢迎各位 → 点赞 👍+ 收藏 ⭐️+ 留言 📝  ​ ​ 快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法。 基本思想： 任取待排序元素序列中 的某元素作为基准值，按照

    2024年01月21日
    浏览(57)

  • 【数据结构与算法】排序算法（选择排序，冒泡排序，插入排序，希尔排序）

    基本概念这了就不浪费时间解释了，这四种都是很简单的排序方式，本专栏后续文章会出归并排序，计数排序，快速排序，堆排序，桶排序等排序算法，今天这篇文章中给出选择排序，冒泡排序，插入排序和希尔排序的实现； 如果发现文章中有错误，还请大家指出来，我会非

    2024年02月15日
    浏览(81)
  • 数据结构与算法-排序算法

    数据结构与算法-排序算法

    递归将整个函数的调用过程 调用过程 如何在CSDN博客中插入公式和各种符号 类似二叉树的后续遍历 递归行为和递归行为时间复杂度的估算 master 公式 : T ( n ) = a × T ( n b ) + O ( n d ) T(n) = a times T (frac{n}{b}) + O(n^d) T ( n ) = a × T ( b n ​ ) + O ( n d ) T ( n ) T(n) T ( n ) : 母问题的规模

    2024年02月15日
    浏览(51)
  • 算法 数据结构 递归插入排序 java插入排序 递归求解插入排序算法 如何用递归写插入排序 插入排序动图 插入排序优化 数据结构（十）

    算法 数据结构 递归插入排序 java插入排序 递归求解插入排序算法 如何用递归写插入排序 插入排序动图 插入排序优化 数据结构（十）

    1. 插入排序（insertion-sort）：                                           是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入     算法稳定性:                  

    2024年02月09日
    浏览(53)

  • 数据结构算法练习 插入排序 冒泡排序

    插入排序 代码如下  package main import \\\"fmt\\\" func main() {     a := []int{4, 5, 6, 1, 3, 2}         b := insert(a)     for i := 0; i len(b); i++ {         fmt.Println(b[i])     } } func insert(a []int) []int {     if len(a) = 1 {                   如果数组长度小于等于1 不用排序直接返回          retur

    2024年02月08日
    浏览(55)
  • 数据结构与算法—插入排序&选择排序

    数据结构与算法—插入排序&选择排序

    目录 一、排序的概念 二、插入排序   1、直接插入排序  特性总结： 2、希尔排序 特性总结：  三、选择排序 1、直接选择排序  特性总结： 2、堆排序—排升序(建大堆) 向下调整函数 堆排序函数 特性总结： 代码完整版：   头文件  函数文件  测试文件 排序 ：所谓排序，

    2024年01月20日
    浏览(62)
  • 数据结构与算法：插入排序&希尔排序

    数据结构与算法：插入排序&希尔排序

    假设现在你有一个有序的数组，你要把一个数据插入到数组中，保证插入后依然有序，要怎么做？ 对于人来说，这个问题就像是在整理扑克牌，瞄一眼就知道应该插入什么位置。但是对于程序来说，就需要一一对比，直到找到一个位置 左边比它大，右边比它小 ，就算找到了

    2024年01月17日
    浏览(55)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包