STL練習2 實作插入排序，箱子排序和基數排序

版權聲明：您好，轉載請留下本人部落格的位址，謝謝 https://blog.csdn.net/hongbochen1223/article/details/45367779

使用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;
}