STL练习2 实现插入排序，箱子排序和基数排序

使用list实现了排序的中比较简单的插入排序，箱子排序和基数排序，其中，箱子排序和基树排序只能用于数的排序，所以限制还是蛮大的，箱子排序在实际使用中基本上不使用，箱子排序是基数排序的基础，基数排序有MSD和LSD，MSD也就是从最高位开始向最低位排序，LSD也就是从最低位向最高位排序。

下面附上我的实现代码：

//============================================================================
// Name        : STLPractice2.cpp
// Author      : 陈洪波
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
#include <list>

using namespace std;

void selecrSort(int test[],int size);

void bulletSort(int test[],int size);

void radixSort(int test[],int size,int wei);
/**
 * 实现插入排序，箱子排序和基数排序
 */
int main() {
    int test[]= {2,1,4,3};

    //selecrSort(test,4);

//  for(int i = 0;i < 4;i++){
//      cout << test[i] << " ";
//  }

    //bulletSort(test,4);


    radixSort(test,4,1);

    for(int m = 0;m < 4;m++){
            cout << test[m] << "    ";
    }
        cout << endl;
    return 0;
}


/**
 * 插入排序
 * 假定数组的第一个元素是排好序的，则从第二个元素开始
 * 与前面的元素进行排序，这样就可以实现排序了
 * 例如： 2 1 4 3
 * 假设第一个元素2已经排好序了
 * 则从第二个元素1开始，向前找，2大于1
 * 则将2向后移动，最后将1插入到2的位置
 * 就变成了 1 2 4 3
 * 4比2大，则就保持4所在的位置
 * 3比4小，则4后移，比2大，则3放在4的位置
 * 这样排序就完成了
 * 1 2 3 4
 */
void selecrSort(int test[],int size){
    if(size == 1)
            return;

        int i = 1;
        for(i = 1;i < size;i++){

            if(test[i-1] > test[i]){
                int temp = test[i];

                int j = i-1;
                while(j>=0 && test[j] >= temp){
                    test[j+1] = test[j];

                    j--;
                }

                test[j+1] = temp;
            }
        }
}



//获取数组中的最大元素
int Max(int test[],int size){
    int i = 0;
    int max = test[0];
    for(i = 1;i < size;i++){
        if(test[i] > max)
            max = test[i];
    }

    return max;
}

//获取数组中的最小元素
int Min(int test[],int size){
    int i = 0;
    int min = test[0];

    for(i = 1;i < size;i++){
        if(test[i] < min)
            min = test[i];
    }

    return min;
}

/**
 * 箱子排序
 * 箱子排序就是相当于桶排序，将每一个不一样大小
 * 的数放入到代表不同数字的桶中，最后再将桶中的元素顺序输出
 */
void bulletSort(int test[],int size){

    int max = Max(test,size);
    int min = Min(test,size);

    //暂时使用List
    list<int> *lists = new list<int>[max-min+1]();

    int i = 0;
    for(i = 0;i < size;i++){
        lists[test[i]-min].push_back(test[i]);
    }

    //输出
    for(i = 0;i < max-min+1;i++){
        list<int>::iterator it = lists[i].begin();

        cout << *it << " ";
    }
}

/**
 * 基树排序（有MSD和LSD）
 * 现在先实现最简单的基数排序，就是对数字只有从小到大排序，没有类别之分
 * 基数排序的思想就是：
 * 先对个位数字进行排序，排序完成之后，统计成堆
 * 接着对上面排好序的十位数字进行排序，排序完成之后，再进行对
 * 排好序的百位数字排序，一次类推
 */
void radixSort(int test[],int size,int wei){
    int i = 0;
    int m = 0;

    for(m = 1;m <= wei;m++){
        //还是采用list作为桶
        list<int> *lists = new list<int>[10];

        for(i = 0;i < size;i++){
            int temp = test[i];

            int loc = 1;
            int tt = 1;
            for(tt = 1;tt < m;tt++){
                loc *= 10;
            }

            lists[(temp/loc%10)].push_back(test[i]);
        }

        int j = 0;
        for(i = 0;i < 10;i++){

            if(lists[i].size() != 0){
                list<int>::iterator it = lists[i].begin();

                while(it != lists[i].end()){
                    test[j] = *it;
                    it++;
                    j++;
                }
            }

        }
    }
}


/**
 * 用于对a和b交换
 */
void swap(int &a,int &b){
    int temp = a;
    a = b;
    b = temp;
}

<script type="text/javascript"> $(function () { $('pre.prettyprint code').each(function () { var lines = $(this).text().split('\n').length; var $numbering = $('<ul/>').addClass('pre-numbering').hide(); $(this).addClass('has-numbering').parent().append($numbering); for (i = 1; i <= lines; i++) { $numbering.append($('<li/>').text(i)); }; $numbering.fadeIn(1700); }); }); </script>

版权声明：本文为博主原创文章，未经博主允许不得转载。