桶排序问题——非对比排序-白红宇

桶排序问题——非对比排序

阅读量：6995 次

发布时间：2019-06-27

本文共 1216 字，大约阅读时间需要 4 分钟。

题目描述：　　

　　不使用比较排序，实现一个数组排序

　　时间复杂度O(N)，额外空间复杂度O(N)

解题思路：

　　使用桶排序思维，申请一个额外数组，叫桶，用来记录数字出现的次数，然后输出即可，但桶排序一般适用于0-9的元素数字排序，因为此时桶只需申请0-9的空间，若array元素为999，则桶的空间至少得申请0-999，那样就不适用。

　　扩展：使用map来实现桶，那么就可以实现任何数组桶排序功能

代码实现：

1 #pragma once 2  3 #include 
     
       4 #include 
       5  6 using namespace std; 7  8 //使用桶数组 9 void Test01(const int array[], int N)10 {11     int TT[10] = { 0 };12     for (int i = 0; i < N; ++i)13         TT[array[i]]++;14     for (int i = 0; i < 10; ++i)15         for (int j = 0; j < TT[i]; ++j)16             cout << i << "  ";17 18     cout << endl << "*******************" << endl;19 }20 21 22 //使用map23 void Test02(const int array[], int N)24 {25     map
       
        M;26     for (int i = 0; i < N; ++i)27         M[array[i]]++;28 29     for (auto ptr = M.cbegin(); ptr != M.cend(); ++ptr)30         for (int j = 0; j < ptr->second; ++j)31             cout << ptr->first << "  ";32     cout << endl << "*******************" << endl;33 34 35 36 }37 38 void NoSort()39 {40     int arr[] = { 9,1,4,8,5,6,7,1,2,5,4,9,0,6 };41     Test01(arr, sizeof(arr) / sizeof(arr[0]));42     Test02(arr, sizeof(arr) / sizeof(arr[0]));43 44 }

转载于:https://www.cnblogs.com/zzw1024/p/10987856.html

你可能感兴趣的文章