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

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

下面附上我的实现代码:

;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};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);<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++){<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;}

奢侈地享受旅不问人,行随己意的潇洒。

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

相关文章:

你感兴趣的文章:

标签云: